Алгоритм D*
Алгоритм D*(Дейкстры)-позволяет нам задавать приоритеты исследования путей. Вместо равномерного исследования всех возможных путей, он отдает предпочтение путям с наиболее низкой "стоимостью".
Создавая, проекты, связанные с перемещением, программируемого объекта, мы часто сталкиваемся с проблемой поиска кратчайшего пути из одной точки в другую. В этой статье мы подробно рассмотрим Алгоритм поиска кратчайшего пути известного как Алгоритм D* так же известный, как Алгоритм Дейкстры.
Для начала попробуем разобраться в принципе работы алгоритма:
Обратим свое внимании на представленный граф. Предположим, что вершины на нем-это населенные пункты, а ребра-это дороги с указанной стоимостью проезда. Как становится понятно, нам необходимо добраться из одной точки в другую за минимальную стоимость. Т. е. найти наиболее оптимальный путь из А в В.
Здесь нам понадобится структура данных, известная как "Куча", которая будет реализовывать приоритетную очередь.
Напишем алгоритм на языке Python.
Сам граф будет состоять из списка смежностей, в которых элементы теперь являются картежами, где на первом месте указана стоимость проезда к вершине, на втором сама вершина.
И так, в алгоритме D* на ряду с приоритетной очередью, мы создадим словарь, чтобы следить за общей стоимостью движения с начальной вершины, а в цикле будем вынимать вершину из очереди с минимальной ценой, затем для всех смежных вершин будем рассчитывать новую цену перемещения от текущей вершины, и если новой вершины не окажется в словаре стоимости пути до нее или новая цена будет ниже, чем уже имеется, то занесем эту вершину в очередь и обновим стоимость пути до нее, и запишем, что пришли к этой вершине из текущей.
def dijkstra(start, goal, graph):
queue = []
heappush(queue, (0, start))
cost_visited = {start: None}
visited = {start: None}
while queue:
cur_cost, cur_node = heappop(queue)
if cur_node == qoal:
break
next_nodes = graph[cur_node]
for next_node in next_nodes:
neigh_cost, neigh_node = next_node
new_cost = cost_visited[cur_node] + neigh_cost
if neigh_node not in cost_visited or new_cost < cost_visited[neigh_node]:
heappush(queue, (new_cost, neigh_node))
cost_visited[neigh_mode] = new_cost
visited[neigh_node] = cur_node
return visited
не забываем добавить восстановление пути:
Применив алгоритм, мы видим самый "дешевый" путь в нашем графе:
