Как найти кратчайший путь в прологе с весовым графиком

Question

У меня есть этот код:

link(a,b,4). 
link(a,c,2). 
link(b,g,5). 
link(c,g,6). 
link(c,d,5). 
link(d,g,3). 

path(S,D,TDist):- 
    link(S,D,TDist). 
path(S,D,TDist):- 
    link(S,X,TD1), path(X,D,TD2), TDist=TD1+TD2. 

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

Answer 1

Я думаю, что есть проблемы с вашим кодом:

• TDist=TD1+TD2 не вычисляет сумму, вместо этого используйте /2, по крайней мере, когда возвращается путь.

• Он будет зацикливаться, если график содержит циклы, но предполагая, что данные на самом деле являются DAG, мы можем игнорировать к настоящему времени.

• Мы не можем сказать, каким будет реальный путь, просто его значение.

В любом случае, библиотека (агрегат) может использоваться для поиска кратчайшего пути. Например

?- aggregate(min(D), path(a,g,D), D).
D = 8.

Или, поскольку у gnu-prolog нет библиотеки (агрегата), возьмите первый элемент, вычисленный с помощью setof/3:

?- setof(D, path(a,g,D), [Min|Rest]).
Min = 8,
Rest = [9, 10].