Prolog路径回溯将永久运行，具体取决于网格大小 [英] Prolog path backtracking runs forever depending on grid size

问题描述

我已经编写了一些代码在Prolog中进行回溯，该代码生成了从初始路径(Agent)到达Gold单元的所有可能路径. getAllPaths的输入是映射大小NxN.当我使用6x6地图运行它时，它可以完美地工作并打印所有可能的路径，但是当我输入任何地图大小> = 7时，它会打印第一个路径并在需要使用;的下一个可能解决方案时卡在那里.这是我的代码:

I've written some code to do backtracking in Prolog that generates all the possible paths to reach the Gold cell from the initial one (Agent). The input of getAllPaths is the map size NxN. When I run it with a 6x6 map it works perfectly and prints all the possible paths, but when I input any map size >= 7 it prints the first path and gets stuck there when I require the next possible solution with ;. Here is my code:

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，并且我可能会收到一些警告或错误，但它什么也不显示.有任何线索吗?

First I thought it would be for some depth recursion limits, but it's so strange because the map size is only incremented from 36 to 49, and I would probably get some warning or error, but it displays nothing. Any clue?

推荐答案

此代码提高了性能. 我认为将搜索和结果打印混合在一起是一个不好的设计.

This code improve the performance. I think it's a bad design to mix the search and the printing of the result.

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

这篇关于Prolog路径回溯将永久运行，具体取决于网格大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！