Как вычислить звезду A * с пользовательской эвристикой в ​​сети x?

Question

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

Я пытаюсь использовать networkx с функцией a_star_path_length. Вот что я уже пробовал:

def distance(a,b):
    return ( nx.dijkstra_path_length(G,a,b, 'day') + len(nx.dijkstra_path(G, a, b)) )

nx.astar_path_length(G, 'A', 'F', heuristic=distance, weight='day')

Предположим, что веса для каждого ребра в графе с шестью узлами следующие:

A,B --> 1 day
B,C --> 1 day
C,D --> 1 day
D,F --> 1 day
A,E --> 4 day
E,F --> 1 day

На каждый посещенный узел мне нужно потратить 1 день.

Следовательно, кратчайший путь между городом А и городом F следующий: A -> E -> F

результат должен быть (4 + 1) + (1 + 1) = 7.

Путь A-B-C-D-F может иметь кратчайшее расстояние. Но из-за ряда транзитов они уже не являются кратчайшими.

Я попробовал свою функцию с функцией a_star, но алгоритм все еще предпочитает маршрут A-B-C-D-F, а не A-E-F.

Пожалуйста, помогите.

Answer 1

Проблема в том, что вы пытаетесь изменить эвристику, а не фактический вес графика. Алгоритм A * на самом деле возвращает путь наименьшего веса точно так же, как алгоритм Джикстры, он просто может сделать это намного быстрее, чем Джикстра, так как он не выполняет случайный поиск в ширину, но имеет эвристику, которая поможет ему правильное направление на графике. Важно отметить, что он все еще находит путь наименьшего веса, независимо от того, что такое эвристика †.

Способ решения этой проблемы заключается в том, чтобы включить весовой номер для транзита. Я считаю, что это должно равняться добавлению 1 (или как вы хотите весить прыжок) к каждому весу на вашем графике.

† Обычно я считаю, что есть исключение для некоторых эвристических свойств.