Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Как работает метод ДП




Доверь свою работу кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

ДП предлагает конструировать оптимальный путь по частям - представить задачу как многошаговую. Разместим условно все входы на одной вертикальной прямой, все узлы, которые встречаются первыми на пути от входов к выходам, - на другой прямой. Также поступим со второй и другими группами узлов и, наконец, с выходами. Получим схему лабиринта.

Построение оптимального пути можно начинать с 1-го или 4-го шага, но предпочтительнее с 4-го - обратная прогонка. Будем искать оптимальное решение для каждого из узлов, в котором можем оказаться перед 4-м шагом (это узлы 8,9 и 10). Фиксируем узел 8 и из четырех значений времени перехода из него к выходам выбираем наименьшее. Соответствующий переход может принадлежать оптимальному пути. Узлу 8 приписываем этот переход и найденное минимальное время, которое обозначим как t8. Аналогично поступаем, фиксируя узел 9, а затем 10. В результате получим t9 и t10 соответственно и переходы, на которых достигаются эти минимальные значения времени. Тем самым завершается первый этап построения оптимального пути.

Теперь полагаем, что осталось совершить 3-й и 4-й переходы. Фиксируем узел 4 и определяем минимальный путь из него к выходам. Достаточно сравнить только три: 1)время на переходе 4-8 плюс t8; 2)время на переходе 4-9 плюс t9; 3)время на переходе 4-10 плюс t10. Минимальное значение приписываем узлу 4 (t4) и выделяем жирной линией соответствующий переход на третьем шаге. Принципиальная особенность ДП: оптимальный переход на шаге 3 определялся не как самый короткий среди переходов этого шага, а как такой, который обеспечивает минимум времени от данного узла к выходу. Точно так же находим решения для узлов 5, 6 и 7. Опираясь на них, можно переходить к третьему этапу построения оптимального пути, охватывающему 2, 3 и 4-й шаги. Рассуждения аналогичны вышеприведенным. Последний, четвертый, этап охватывает все шаги. Найдя решение для 1-го шага, мы тем самым завершаем построение оптимальных путей. Двигаясь по полученному решению от входа к выходу, то есть в прямом направлении, последовательно находим переходы, составляющие оптимальный путь.







Дата добавления: 2015-04-19; просмотров: 476. Нарушение авторских прав; Мы поможем в написании вашей работы!

Studopedia.info - Студопедия - 2014-2022 год . (0.016 сек.) русская версия | украинская версия