2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Алгоритм Беллмана-Мура
Сообщение29.06.2017, 09:46 


05/05/17
35
Здравствуйте, расскажите, пожалуйста, по-этапно, как с помощью алгоритма Беллмана-Мура найти кратчайший путь в ор.графе,
С чего начать и как закончить?
Ну или дайте ссылку на учебник, где он подробно разбирается.

 Профиль  
                  
 
 Re: Алгоритм Беллмана-Мура
Сообщение29.06.2017, 20:06 
Заслуженный участник


11/05/08
32166
Это довольно лобовой алгоритм. Основан на двух достаточно очевидных соображениях.

Во-первых, в оптимальном маршруте нет повторяющихся вершин (ну или как минимум их можно избежать -- это зависит от того, допускаются или нет нулевые и отрицательные веса рёбер; для краткости будем считать, что не допускаются и тем самым повторяющиеся вершины просто невозможны).

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

Алгоритм основан на построении матрицы кратчайших расстояний между исходной вершиной (для определённости считаем, что первой) и всеми остальными. Каждому столбцу матрицы отвечает одна из остальных вершин. В строке с номером $k$ хранятся минимальные расстояния до этих вершин, за которые можно добраться в них из первой за не более чем $k$ шагов (т.е. рёбер).

Первая строчка -- это просто длины рёбер, по которым можно перейти в данную строку из первой (минимальные из возможных, естественно, если перейти можно по нескольким рёбрам). И бесконечность, если таких рёбер нет. Как формализовывать бесконечность -- вопрос сугубо технический; в Матлабе, скажем -- тупо как бесконечность.

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

Алгоритм останавливается, когда следующая строка совпадёт с предыдущей.

Теперь как восстановить собственно оптимальные маршруты (запоминать эти цепочки на прямом ходе алгоритма сильно неудобно). Информации, хранящейся в построенной матрице, для этого вполне достаточно. Восстановление производится в обратном порядке, начиная с целевой вершины и заканчивая первой. Смотрим все рёбра, входящие в целевую вершину из остальных. Прибавляем для каждой из последних её кратчайшее расстояние до первой к длине соединяющего эти две вершины ребра. Когда сумма совпадёт с кратчайшим расстоянием от первой до целевой -- всё, предыдущая вершина маршрута найдена. Далее аналогично, с заменой целевой вершины на найденную перед этим предыдущую. (Естественно, для целевых вершин, у которых в последней/предпоследней строке стоит конечное число -- в противном случае соединяющего с первой маршрута просто не существует.)

 Профиль  
                  
 
 Re: Алгоритм Беллмана-Мура
Сообщение29.06.2017, 20:25 


05/05/17
35
Похоже, разобрался. Спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group