使用列表列表的最短路径

Question

[好，所以我最近一直在尝试自学Prolog，并且很难把头放在清单列表中两个（定义的）元素之间寻找“最短路径”。它可能不是表示网格或找到最短路径的最有效方法，但我想尝试这种方法。

例如：

[[x,x,x,x,x,x,x],
 [x,1,o,o,o,o,x],
 [x,-,-,-,o,-,x],
 [x,-,-,o,o,-,x],
 [x,o,o,o,o,2,x],
 [x,o,-,-,o,o,x],
 [x,x,x,x,x,x,x]]

我可以做出的一些假设（给出或基于寻找路径之前的检查）：

• 网格为正方形
• 他们将始终存在从1到2的路径
• '1'可以穿过'-'（墙壁）或'x'（边界）以外的任何东西

目标是让“ 1”找到通往“ 2”的最短路径。

在以下情况下：

[[x,x,x,x,x,x,x],
 [x,o,o,1,o,o,x],
 [x,-,o,o,o,-,x],
 [x,-,o,-,o,-,x],
 [x,o,o,2,o,o,x],
 [x,o,-,-,-,o,x],
 [x,x,x,x,x,x,x]]

注意，有两个“最短路径”：

[d,l,d,d,r]

和

[d,r,d,d,l]

在Prolog中，我正在尝试制作函数（如果这是适当的名称）：

shortestPath(Grid,Path)

我制作了一个查找元素'1'和'2'的函数，并验证了网格是否有效，但是我什至无法开始构建从'寻找最短路径的函数。 1'至'2'。

鉴于已定义的网格，我希望Path的输出为最短路径。或者，给定已定义的网格和已定义的路径，我想检查它是否确实是最短的路径。

非常感谢您的帮助！如果我错过了任何事情或不清楚，请告诉我！

Answer 1

未优化的解决方案

shortestPath(G, S) :-
    findall(L-P, (findPath(G,P), length(P,L)), All),
    keysort(All, [_-S|_]).

findPath(G, Path) :-
    pos(G, (Rs,Cs), 1),
    findPath(G, [(Rs,Cs)], [], Path).

findPath(G, [Act|Rest], Trail, Path) :-
    move(Act,Next,Move),
    pos(G, Next, Elem),
    (   Elem == 2
    ->  reverse([Move|Trail], Path)
    ;   Elem == o
    ->  \+ memberchk(Next, Rest),
        findPath(G, [Next,Act|Rest], [Move|Trail], Path)
    ).

move((R,C), (R1,C1), M) :-
    R1 is R-1, C1 is C  , M = u;
    R1 is R  , C1 is C-1, M = l;
    R1 is R+1, C1 is C  , M = d;
    R1 is R  , C1 is C+1, M = r.

pos(G, (R,C), E) :- nth1(R, G, Row), nth1(C, Row, E).

grid(1,
[[x,x,x,x,x,x,x],
 [x,1,o,o,o,o,x],
 [x,-,-,-,o,-,x],
 [x,-,-,o,o,-,x],
 [x,o,o,o,o,2,x],
 [x,o,-,-,o,o,x],
 [x,x,x,x,x,x,x]]).

grid(2,
[[x,x,x,x,x,x,x],
 [x,o,o,1,o,o,x],
 [x,-,o,o,o,-,x],
 [x,-,o,-,o,-,x],
 [x,o,o,2,o,o,x],
 [x,o,-,-,-,o,x],
 [x,x,x,x,x,x,x]]).