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