Обратный путь пролога выполняется вечно в зависимости от размера сетки

Я написал некоторый код для обратного отслеживания в Прологе, который генерирует все возможные пути для достижения золотой ячейки от начальной (агент). Ввод 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, и я, вероятно, получу какое-то предупреждение или ошибку, но ничего не отображается. Любая подсказка?

Источник

2 ответа

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

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|...] .
Источник

Вот мой вариант.

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

Это исключает использование assertz / 1, поэтому повторный запрос не добавляет нескольких фактов, меняет member / 2 на memerchk/2 для повышения эффективности, строит путь при обратном отслеживании, чтобы избежать добавления / 3, и добавляет сокращение для удаления повторяющихся ответов.

Поскольку результат возвращается на верхний уровень, добавлен счетчик / 2, чтобы показать счет вместо списка.

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

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

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

?- count(6,N).
N = 910480
Источник
Другие вопросы по тегам