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

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

0 голосов
/ 10 ноября 2018

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

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.

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

1 Ответ

0 голосов
/ 10 ноября 2018

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

  • 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].
...