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

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

0 голосов
/ 18 февраля 2019

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

0 голосов
/ 18 февраля 2019

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

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 to 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
0 голосов
/ 18 февраля 2019

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

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