Как выбрать кратчайший путь из выбора в Прологе

Question

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

nodeLink(1,2,4).
nodeLink(1,3,10).
nodeLink(1,5,2).

nodeLink(2,1,4).
nodeLink(2,5,1).
nodeLink(2,4,6).
nodeLink(2,6,1).

nodeLink(3,1,10).
nodeLink(3,5,2).
nodeLink(3,4,1).

nodeLink(4,3,1).
nodeLink(4,5,8).
nodeLink(4,2,6).

nodeLink(5,1,2).
nodeLink(5,2,1).
nodeLink(5,3,2).
nodeLink(5,4,8).

nodeLink(6,2,1).


path([B | BRest], B, [B | BRest], Length, Length).
path([A | ARest], B, Path, CurrentLength, Length) :-
    nodeLink(A, C, X),
    \+member(C, [A | ARest]),
    NewLength is CurrentLength + X,

    path([C, A | ARest], B, Path, NewLength, Length).

all_paths(Start, End) :-
    path([Start], End, Path, 0, Length),
    reverse(Path, RevPath),
    write('Path: '),
    printPath(RevPath),
    write(' with a cost of '),
    writeln(Length),
    fail.

printPath([]).
printPath([X]) :-
    !,
    write(X).
printPath([X|Xrest]) :-
    write(X),
    write(', '),
    printPath(Xrest).

Например:

?- all_paths(6,3).

Распечатывает:

Path: 6, 2, 1, 3 with a cost of 15
Path: 6, 2, 1, 5, 3 with a cost of 9
Path: 6, 2, 1, 5, 4, 3 with a cost of 16
Path: 6, 2, 5, 1, 3 with a cost of 14
Path: 6, 2, 5, 3 with a cost of 4
Path: 6, 2, 5, 4, 3 with a cost of 11
Path: 6, 2, 4, 3 with a cost of 8
Path: 6, 2, 4, 5, 1, 3 with a cost of 27
Path: 6, 2, 4, 5, 3 with a cost of 17
false.

Как бы я go выбрал «кратчайший» путь для данной пары узлов? Спасибо

Answer 1

Как правило, в Prolog вы не хотели бы использовать write и отказ, вызванный l oop, чтобы показать все решения. Канонический подход заключается в том, чтобы иметь предикат, который успешно выполняется для каждого решения (как это делает ваш предикат path/5), а затем использовать findall/3 или bagof/3 или setof/3, чтобы собрать все решения в списке. setof/3 имеет преимущество удаления дубликатов и упорядочения результирующей коллекции.

Вот поиск по стеку потока на [пролог] направленном графе кратчайшего пути . Это много раз освещалось на этом сайте, я не хотел просто выбирать один из них. Я не видел того, который использует setof/3, поэтому вот решение, использующее этот подход.

Я буду использовать ваше существующее определение path/5. Поскольку коллекция путей уникальна по своему дизайну, использование setof/3 будет небольшим улучшением по сравнению с использованием findall/3, за которым следует msort/2, что вы найдете по крайней мере в одном из связанных решений. Идея здесь состоит в том, чтобы создать список решений вида Cost-Path, которые упорядочены по Cost. Затем вам нужно выбрать самую низкую стоимость из списка, который является первым элементом, так как они заказаны.

shortest_path(Start, End, ShortestPath, ShortestLength) :-
    setof(Length-Path, path([Start], End, Path, 0, Length), [ShortestLength-ShortestPath|_]).

Если вы хотите сделать хорошую распечатку вашего списка, вы можете использовать maplist :

print_path(Cost-Path) :-
    write('Path: '),
    write(Path),
    write(' with a cost of '),
    write(Cost), nl.

print_paths(CostPaths) :-
    maplist(print_path, CostPaths).

Где CostPaths - результат выполнения setof/3, указанного выше.