Задача о путешествиях icon

Задача о путешествиях




Скачати 44.81 Kb.
НазваЗадача о путешествиях
Дата24.06.2012
Розмір44.81 Kb.
ТипЗадача

ЗАДАЧА О ПУТЕШЕСТВИЯХ

В качестве дальнейшего примера приложения этих идей рассмотрим следующую задачу о путешествиях, которая воз­никает в самых разнообразных прикладных вопросах.

Предположим, что имеются N городов, занумерованных индексом

i=1,2, ..., N в некотором порядке, и задан ряд чисел ,где —время, потребное на путешествие из i-го города в j-й.

Начав с первого города, мы хотим провести путь в N-й, который потребует минимального времени. Мы можем идти прямо или заходить по пути в любой другой город.

В тех случаях, когда между некоторыми городами не име­ется никакой

связи, мы будем считать соответствующее ,бесконечным или, при использовании цифровых вычислительных машин, очень большим положительным числом.

Если N велико, то любое решение путем простого перебора невозможно. Попытаемся решить задачу с помощью метода функциональных уравнений. Рассмотрим общую задачу об определении минимального времени, потребного для пере­хода из i-го города в N-й. Пусть — время, потребное для путешествия из i-го в N-й город при использовании оптимальной политики.

Тогда те же самые доводы, которые мы использовали при рассмотрении предшествующей траекторией задачи, приве­дут к соотношению



Легко можно показать, что эта система уравнений имеет единственное решение, а следовательно, что решение этого ряда задач эквивалентно решению исходной задачи.

^ ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ

Уравнение (б.32) обладает особенностью, которая ранее не встречалась; именно здесь неизвестная функция появ­ляется и в левой и в правой частях уравнения. Следовательно, мы не имеем готовой итерационной схемы для его решения.

Необходимо использовать какой-либо метод последо­вательных приближений. Мы могли бы, например, положить





Это приводит к монотонной сходимости снизу. С другой стороны, мы можем мыслить в терминах политик. Рассмотрим сначала те пути, которые ведут прямо из i в N, за­тем те, в которых делается одна остановка, и т. д. Это приводит к следующей схеме:





при которой осуществляется монотонная сходимость сверху, причем за конечное число шагов.

Метод (6.33) оценивает наилучший путь длины k, начи­нающийся от города i. Однако уравнения имеют то свой­ство, что N является стоком, и если путь достигает N менее чем за k шагов, то там можно остановиться. Для любого другого города путь не может оборваться ранее k шагов.

Следовательно, когда k становится большим, все пути стремятся прийти в город N, а минимизация гарантирует, что они сделают это наилучшим образом.

В методе (6. 34) считается, что каждый город достижим на каждой итерации, но потребное время не обязательно является оптимальным. Последовательные приближения схо­дятся к наилучшему пути.

Этот пример иллюстрирует различие между итерациями в пространстве функций и в пространстве политик (пове­дений), рассмотренное в П. дает при каждой итерации оптимальное решение задачи, отлича­ющейся от исходной. Метод (1), прежде чем осуществит­ся сходимость, дает неоптимальное решение исходной задачи. Оба метода пригодны для ручного или машинного счета при умеренных значениях N, т.е. N< 100, и для машинного счета для N порядка нескольких тысяч. 26, n-Й ПО КРАТКОСТИ ПУТЬ

Иногда бывает интересно определить не только кратчай­ший путь, но и второй по краткости, третий по краткости и т.п. Тем самым мы сможем оценить, насколько важно ис­пользовать наикратчайший путь по сравнению, скажем, с деся­тым по краткости. Для того чтобы проиллюстрировать ме­тод, введем последовательность величин Vi, равных времени, потребному на переход от i к N, (6.35) при использовании второго по краткости пути,

i=1, 2,…, N-1,

Для получения соотношений для vt заметим, что если первая остановка на пути из i в N делается в j, то продол­жение движения из j в N должно происходить ' либо по пути, который минимизирует время путешествия от j к N, либо по пути, который является вторым по краткости для перехода из у в N. Пусть - есть абсолютный минимум (i=1, 2,..., N), - есть вторая по малости величина .

Тогда мы имеем уравнение




a определены. Аналогичные, но несколько более громоздкие уравнения можно вывести для n-го по краткости пути.

Схожі:

Задача о путешествиях iconЗадача прогноз задача ефект ставка -1 задача ефект ставка -2 задача опт портфель графіки
По акціях корпорацій виплачується дивіденд 5 г о на одну акцію. Продажна ціна акцій на фондовій біржі становила 100 г о
Задача о путешествиях iconПлоская задача теории упругости
Плоская задача включает в себя плоскую деформацию и обобщенное плоское напряженное состояние
Задача о путешествиях iconЗадача №2, 11 клас
Задача №2, 11 клас. Нехай маса мавпи m, а момент інерції барабана I. Коли мавпа рухається разом з барабаном, механічну енергію системи...
Задача о путешествиях icon2 Двойственная задача линейного программирования Двойственная задача
Между прямой и двойственной задачами существуют тесная взаимосвязь. Фактически оптимальное решение одной из задач непосредственно...
Задача о путешествиях icon2 Двойственная задача линейного программирования Двойственная задача
Между прямой и двойственной задачами существует тесная взаимосвязь. Фактически оптимальное решение одной из задач непосредственно...
Задача о путешествиях icon3. Транспортна задача лінійного програмування Формулювання задачі
Транспортна задача представляє собою задачу лп, котру можно вирішувати симплекс-методом. Але специфічна структура умов задачі дозволяє...
Задача о путешествиях icon3. Транспортна задача лінійного програмування Формолювання задачі
Транспортна задача представляє собою задачу лп, котру можно вирішувати симплекс-методом. Але специфічна структура умов задачі дозволяє...
Задача о путешествиях icon2. Двоїста задача лінійного програмування Тема Транспортна задача
Операція, основні поняття І якості. Прямі та зворотні задачі. Управління операцією, оцінка якості. Математичні моделі операцій. Допустимі...
Задача о путешествиях icon7. Стаціонарний розподіл тепла у платівці. (Задача Діріхлє у прямокутнику для рівняння Лапласа)
Задача. Встановити стаціонарний розподіл температури у квадратній платівці, якщо дві бічні сторони платівки теплоізольовані, на третій...
Задача о путешествиях iconТема Поняття, предмет, принципи трудового права України Задача 1
Задача Фірма «Орізон» уклала договір з будівельним кооперативом «Фасад» на будівництво складських приміщень. У складі будівельної...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи