Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23
Download 1.85 Mb. Pdf ko'rish
|
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев
|
5.4.1. В
ОЛНОВОЙ АЛГОРИТМ Волновой алгоритм поиска кратчайшего пути впервые был предложен Э.Ф. Муром в 1959 году. Относится к классу алгоритмов поиска в ширину и используется при компьютерной разводке соединительных проводников на поверхности электронных микросхем. Рассмотрим его для случая поиска кратчайшего пути между вершинами s и t невзвешенного графа. Алгоритм использует два списка OldFront и NewFront, представ- ляющих предыдущий и последующий «фронт волны», а также целую пере- менную T – текущее время. Отсчет времени ведется от нуля. Последователь- ность шагов алгоритма такова: 1) каждой вершине v i приписывается целое число T(v i ), которое будем называть волновой меткой; начальное значение волно- вой метки для всех вершин полагается равным −1; 6 / 23 168 2) в список OldFront заносится вершина s, а список New- Front первоначально считается пустым. Для вершины s устанавливается значение числовой метки, равное 0; 3) для каждой из вершин, входящих в OldFront, просматрива- ются инцидентные ей вершины u j , и если они имеют волновые метки, равные -1, то они заменяются на T + 1 с добавлением соответствующих вершин в список NewFront; 4) если список NewFront пуст, то алгоритм завершается с результатом «нет решения»; 5) если одна из вершин списка NewFront совпадает с конечной вершиной t, то это означает, что найден кратчайший путь меж- ду s и t с T + 1 промежуточными ребрами, и алгоритм заверша- ется с результатом «решение найдено»; 6) если алгоритм не завершен, то содержимое списка NewFront переносится в список OldFront, список NewFront снова по- лагается пустым, значение переменной T увеличивается на 1 и выполняется переход на шаг 4. Примечание Имеется различие в выполнении шага 3 для неоринтированных и ориентированных графов: для первых учитываются все инцидентные им вершины, а для вторых только вершины, в которые ведут дуги, исходящие из данной вершины. На самом деле волновой алгоритм в общем случае определяет множе- ство путей одинаковой и наименьшей длины между двумя заданными вер- шинами. Восстановить один из них можно следующим образом. Начинаем просмотр с вершины t и ищем среди ее соседей любую вершину с волновой меткой, на единицу меньшей, чем у вершины t. Среди соседей последней – вершину с меткой на два меньшей, чем у t, и далее вплоть до вершины s. Восстановление пути будет происходить быстрее, если на шаге 3 сохранять метку вершины, из которой «волна» пришла в данную вершину. Работа вол- нового алгоритма иллюстрируется рисунком 5.10. S T 0 1 1 1 2 2 2 3 Рис. 5.10. Разметка графа после выполнения волнового алгоритма 7 / 23 |
