Алгоритм решения задачи о кратчайшем пути

1. По заранее заданной сети выписывается матрица расстояний между всеми узлами сети. Если дуга, соединяющая узлы, отсутствует (отсутствует путь, ведущий из Алгоритм решения задачи о кратчайшем пути - student2.ru -го пункта в Алгоритм решения задачи о кратчайшем пути - student2.ru -й), то в матрице расстояний ставится знак запрета данного пути.

2. Пусть Алгоритм решения задачи о кратчайшем пути - student2.ru - сумма длин дуг, образующих цепь, ведущую из узла 1 в узел Алгоритм решения задачи о кратчайшем пути - student2.ru . Положим Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru , если Алгоритм решения задачи о кратчайшем пути - student2.ru . При условии, что Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru соединены дугой, величина Алгоритм решения задачи о кратчайшем пути - student2.ru определяется как Алгоритм решения задачи о кратчайшем пути - student2.ru . Процесс начинается с Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru .

3. Определяется кратчайший путь. Проверяется выполнение неравенства Алгоритм решения задачи о кратчайшем пути - student2.ru , при этом выделяют те элементы матрицы, для которых данное неравенство выполняется как равенство. Если для Алгоритм решения задачи о кратчайшем пути - student2.ru Алгоритм решения задачи о кратчайшем пути - student2.ru , то между узлами не существует более короткого пути. Переход к п.5.

4. . Если Алгоритм решения задачи о кратчайшем пути - student2.ru , для которых Алгоритм решения задачи о кратчайшем пути - student2.ru , вычисляются новые значения Алгоритм решения задачи о кратчайшем пути - student2.ru , используя формулу Алгоритм решения задачи о кратчайшем пути - student2.ru . Меняются Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru для Алгоритм решения задачи о кратчайшем пути - student2.ru на Алгоритм решения задачи о кратчайшем пути - student2.ru . Повторяется п.2 с новыми значениями Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru .

5. Полученные Алгоритм решения задачи о кратчайшем пути - student2.ru определяют кратчайшее расстояние между узлами 1 и Алгоритм решения задачи о кратчайшем пути - student2.ru . По выделенным элементам матрицы выписывается кратчайший путь.

Пример. Рассмотримсеть

Алгоритм решения задачи о кратчайшем пути - student2.ru

Сеть содержит циклы, возникающие из-за возможности двустороннего движения. Если дуга ориентирована, (т.е. движение одностороннее), расстояние в другом направлении полагается равным ¥.

Занесем данные в матрицу расстояний, где строка Алгоритм решения задачи о кратчайшем пути - student2.ru (столбец Алгоритм решения задачи о кратчайшем пути - student2.ru ) представляет узел Алгоритм решения задачи о кратчайшем пути - student2.ru (узел Алгоритм решения задачи о кратчайшем пути - student2.ru ).

i j Алгоритм решения задачи о кратчайшем пути - student2.ru
     
     
  ¥    
     
¥      
   
       
Алгоритм решения задачи о кратчайшем пути - student2.ru j  

Исходные величины Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru определяются следующим образом. Пусть Алгоритм решения задачи о кратчайшем пути - student2.ru . При использовании формулы

Алгоритм решения задачи о кратчайшем пути - student2.ru Алгоритм решения задачи о кратчайшем пути - student2.ru

осуществляется последовательное обращение к величинам Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru по мере того, как они становятся доступными.

Алгоритм решения задачи о кратчайшем пути - student2.ru

При переходе к шагу 2 проводится проверка условия оптимальности путем сравнения Алгоритм решения задачи о кратчайшем пути - student2.ru с Алгоритм решения задачи о кратчайшем пути - student2.ru . При этом выделяются те элементы, для которых Алгоритм решения задачи о кратчайшем пути - student2.ru = Алгоритм решения задачи о кратчайшем пути - student2.ru .

i j Алгоритм решения задачи о кратчайшем пути - student2.ru
  2 11    
  3   5 1  
  ¥    
     
¥      
    10
       
Алгоритм решения задачи о кратчайшем пути - student2.ru  


В процессе реализации алгоритма обнаруживается, что условие оптимальности первый раз нарушается при Алгоритм решения задачи о кратчайшем пути - student2.ru для Алгоритм решения задачи о кратчайшем пути - student2.ru и 5. Величины Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru меняются следующим образом:

Алгоритм решения задачи о кратчайшем пути - student2.ru

После этого повторяется шаг 2 с измененными значениями Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru

i j Алгоритм решения задачи о кратчайшем пути - student2.ru
  2      
  3   5 1    
  ¥      
      (8)
¥       9 (4)
  5 1   10  
         
Алгоритм решения задачи о кратчайшем пути - student2.ru    
      (8) (4)        

Из последней таблицы видно, что в новых изменениях нет необходимости, и поэтому последние измененные величины Алгоритм решения задачи о кратчайшем пути - student2.ru дают длину кратчайшего пути от 1 до Алгоритм решения задачи о кратчайшем пути - student2.ru . Кратчайшее расстояние между узлами 1 и 7 равно Алгоритм решения задачи о кратчайшем пути - student2.ru (=13).

Найдем участки кратчайшего пути между узлами 1 и 7. Определение участков пути должно начинаться с узла 7. Из столбца 7 видно, что равенство выполняется (подчеркнутый элемент) при Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru , т.е. либо узел 5, либо узел 6 соединены с 7 (альтернативные решения). Аналогичные исследования для 5 и 6 узлов дадут Алгоритм решения задачи о кратчайшем пути - student2.ru и Алгоритм решения задачи о кратчайшем пути - student2.ru . Будем продолжать эту процедуру до тех пор, пока не вернемся в первый узел.

Таким образом, кратчайший путь имеет вид:

 
  Алгоритм решения задачи о кратчайшем пути - student2.ru

УПРАЖНЕНИЯ

Задача 1. Для местного аэропорта приобретается дополнительный автокар. Через три года планируется установка механизированной погрузочной системы, после чего автокары станут ненужными. Тем не менее может оказаться выгодным заменить автокар через год или два года или даже осуществить две замены (через год и через два года ). В следующей таблице приведены полные расходы (с учетом стоимости эксплуатации и выручкой от продажи), связанные с покупкой автокара в конце года i и его продажей в конце года j .

Год покупки (i) Год продажи (j)
0
 
   

Необходимо минимизировать расходы.

Сформулировать задачу как задачу выбора кратчайшего пути. Решить полученную задачу.

Задача 2. Адам Козлевич ежедневно ездит на работу на автомобиле. Закончив в свое время полный курс по теории исследования операций, он легко определил самый короткий путь от дома до работы. К сожалению, данный маршрут усиленно патрулируется нарядами полиции, и автомобиль Козлевича часто останавливают за превышение скорости (как ему кажется, не обоснованно). Таким образом, самый короткий путь оказался не самым быстрым. Поэтому А. Козлевич планирует разработать новый маршрут, на котором он имел бы самую высокую вероятность не быть остановленным полицией. Схема сети дорог, по которой Козлевич может добраться от дома до работы, показана на рисунке.

Алгоритм решения задачи о кратчайшем пути - student2.ru

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

Наши рекомендации