1

我已经编写了一些代码来在 Prolog 中进行回溯，它生成从初始单元（代理）到达黄金单元的所有可能路径。getAllPaths 的输入是地图大小 NxN。当我使用 6x6 地图运行它时，它可以完美运行并打印所有可能的路径，但是当我输入任何地图大小 >= 7 时，它会打印第一条路径并在我需要下一个可能的解决方案时卡在那里;。这是我的代码：

gold(3, 3).
agent(1, 1).

getAllPaths(MS) :-
    agent(X, Y),
    assertz(worldSize(MS)),
    getAllPathsRec(X, Y, [], []).

% Positions, Visited list, and Path list
getAllPathsRec(X, Y, V, L) :-
    \+member((X, Y), V), append(V, [(X, Y)], VP),
    ((gold(X, Y), print(L)) ; move(X, Y, VP, L)).

% Left
move(X, Y, V, L) :-
    XP is X - 1, XP > 0,
    append(L, [l], LP),
    getAllPathsRec(XP, Y, V, LP).

% Right
move(X, Y, V, L) :-
    XP is X + 1, worldSize(MS), XP =< MS,
    append(L, [r], LP),
    getAllPathsRec(XP, Y, V, LP).

% Up
move(X, Y, V, L) :-
    YP is Y + 1, worldSize(MS), YP =< MS,
    append(L, [u], LP),
    getAllPathsRec(X, YP, V, LP).

% Down
move(X, Y, V, L) :-
    YP is Y - 1, YP > 0,
    append(L, [d], LP),
    getAllPathsRec(X, YP, V, LP).

输出：

?- getAllPaths(6).
[r,r,r,r,r,u,l,l,l,l,l,u,r,r]
true ;
[r,r,r,r,r,u,l,l,l,l,l,u,r,u,l,u,r,r,r,r,r,d,l,l,l,d]
true ;
[r,r,r,r,r,u,l,l,l,l,l,u,r,u,l,u,r,r,r,r,r,d,l,l,d,l]
true ;
[...]
?- getAllPaths(7).
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r]
true ;
% It gets stuck here forever...

首先，我认为这将是一些深度递归限制，但这很奇怪，因为地图大小仅从 36 增加到 49，我可能会收到一些警告或错误，但它什么也没显示。有什么线索吗？

4

2 回答 2

1

此代码提高了性能。我认为混合搜索和打印结果是一个糟糕的设计。

gold(3, 3).
agent(1, 1).

getAllPaths(MS, L) :-
    agent(X, Y),
    retractall(worldSize(_)),
    assertz(worldSize(MS)),
    getAllPathsRec(X, Y, [], [], L).


% Positions, Visited list, and Path list
getAllPathsRec(X, Y, _V, L, NL) :-
    gold(X, Y),
    reverse(L, NL).


% Positions, Visited list, and Path list
getAllPathsRec(X, Y, V, CL, L) :-
    \+member((X, Y), V),

    % useless 
    % append(V, [(X, Y)], VP),

    move(X, Y, CL, NX, NY, NL),

    % No need to use append to build the list of visited nodes
    getAllPathsRec(NX, NY, [(X,Y) | V], NL, L).

% Left
move(X, Y, L, NX, Y, [l|L]) :-
    X > 1 ,NX is X - 1.

% Right
move(X, Y, L, NX, Y, [r|L]) :-
    worldSize(MS), X < MS,NX is X + 1.

% Up
move(X, Y, L, X, NY, [u|L]) :-
    worldSize(MS), Y < MS, NY is Y + 1.

% Down
move(X, Y, L, X, NY, [d|L]) :-
    Y > 1, NY is Y - 1.

我得到：

?- getAllPaths(7, V), writeln(V).
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,l]
V = [r, r, r, r, r, r, u, l, l|...] ;
 [r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,l,d]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,u,l,l,l,d,r,r,d]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,u,l,l,u,l,d,d,r,r,d]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,u,l,l,u,r,r,r,r,r,u,l,l,l,l,l,l,d,d,d,r,r,d]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,u,l,l,u,r,r,r,r,u,l,l,l,l,l,d,d,d,r,r,d]
V = [r, r, r, r, r, r, u, l, l|...] ;
[r,r,r,r,r,r,u,l,l,l,l,l,l,u,r,r,r,r,r,r,u,l,l,l,u,l,l,u,r,r,r,r,d,r,u,u,l,l,l,l,l,l,d,d,d,r,r,d]
V = [r, r, r, r, r, r, u, l, l|...] .
于 2019-02-18T17:41:01.683 回答
1

这是我的变化。

getAllPaths_01(MS, R) :-
    agent(X, Y),
    getAllPathsRec_01(MS, X, Y, [], R).

getAllPathsRec_01(_MS, X, Y, _V, []) :-
  gold(X,Y), !.

% Positions, Visited list, and Path list
getAllPathsRec_01(MS, X, Y, V, R) :-
    \+ memberchk((X, Y), V),
    move_01(MS, X, Y, [(X, Y)|V], R).

% Left
move_01(MS, X, Y, V, [l|R]) :-
    XP is X - 1, XP > 0,
    getAllPathsRec_01(MS, XP, Y, V, R).

% Right
move_01(MS, X, Y, V, [r|R]) :-
    XP is X + 1, XP =< MS,
    getAllPathsRec_01(MS, XP, Y, V, R).

% Up
move_01(MS, X, Y, V, [u|R]) :-
    YP is Y + 1, YP =< MS,
    getAllPathsRec_01(MS, X, YP, V, R).

% Down
move_01(MS, X, Y, V, [d|R]) :-
    YP is Y - 1, YP > 0,
    getAllPathsRec_01(MS, X, YP, V, R).

count(S,N) :-
  bagof(L,getAllPaths_01(S,L),Ls),
  length(Ls,N).

这删除了 ​​use assertz/1以便重新运行查询不会添加多个事实，将member/2更改为memerchk/2以提高效率，在回溯时构建路径以避免append/3，并添加一个剪切以删除重复的答案。

由于结果返回到顶层，添加 count/2 以显示计数而不是列表。

?- count(3,N).
N = 12.

?- count(4,N).
N = 132.

?- count(5,N).
N = 6762.

?- count(6,N).
N = 910480
于 2019-02-18T18:01:54.597 回答