Алгоритмы поиска путей. Йена.(Динамическое программирование) Алгоритм для поиска альтернативных кратчайших путей в графе
Используется алгоритм Дейкстры для нахождения 1 кратчайшего пути(обозначу его №1 - для нас)
Берется начальная точка из этого пути и удаляется ребро, которое ведет к следующей точка, чтобы алгоритм дейкстры не пошел по №1 кратчайшему пути
Использую алгоритм дейкстры, и добавляю новый кратчайший путь в список с путями кандидатами, для будущей финальной выборки
Далее беру следующую точку, к которой удаляли ребро.
Удаляю предыдущую точку и ребро к ней, чтобы алгоритм дейкстры не пошел через точки первого пути, а также удаляю ребро к следующей точки из пути №1
Использую алгоритм дейкстры, и добавляю новый кратчайший путь в список с путями кандидатами, для будущей финальной выборки
И так далее продолжаю удалять предыдущий путь и следующее ребро из №1 кратчайшего пути
Далее из списка кандидатов выбираю самый короткий путь и добавляю его(№2) к №1 кратчайшему пути
На данный момент у нас есть 2 пути, теперь мы также берем начальную точку, но теперь убираем те финальные пути 2 пути, также как и в процессе нахождения 2 ребра, то есть убираем ребро ведущее к 1, так как и в №1 и в №2 есть эта точка
Потом также продолжаем до того момента, когда у нас появится 2 пути по которым мы уже проходили
Теперь мы убираем 2 ребра , чтобы не идти ни по №1 ни по №2 и используем алгоритм Дейкстры -) находим новый путь, добавляем его к новым кандидатам
В конечном итоге продолжаем так делать пока не найдем нужное нам количество альтернативных путей
Алгоритмы поиска путей. А*.(Эвристический алгоритм)
Программа использует алгоритм А*, который пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. При выборе вершины он учитывает весь пройденный до неё путь.
В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение, после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых вершин графа — множеством частных решений, — которое размещается в очереди с приоритетом. Приоритет пути определяется по значению. Алгоритм продолжает свою работу до тех пор, пока значение целевой вершины не окажется меньшим, чем любое значение в очереди, либо пока всё дерево не будет просмотрено. Из множества решений выбирается решение с наименьшей стоимостью.