Как вернуться к плате NxN в Прологе?

Question

В настоящее время я должен сделать что-то вроде реализации Wumpus World в SWI Prolog и указать все возможные пути на доске размером NxN , я сделал несколько уроков по прологу, но не могу понять, как решитьэта конкретная задача в прологе.Я пытаюсь найти все возможные пути для моего агента к золоту и ничего больше.Он должен начинаться с начальной позиции (X0, Y0) .

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

:- dynamic getAllPathsRec/2, agent/2, visited/2, visited/2.

gold(5,5).

worldSize(10).

agent(1,1).

getAllPaths :-
    getAllPathsRec(1,1).

getAllPathsRec(X,Y) :-
    format(X), format(Y), format('~n'),
    gold(X1,Y1),
    \+visited(X,Y),
    assert(visited(X,Y)),
    (X = X1, Y = Y1) -> print('Found GOLD');
    move(_,X,Y).

move(right, X, Y) :-
    X1 is X + 1,
    X1 > 0 , X1 < 11,
    getAllPathsRec(X1,Y).
move(left, X, Y) :-
    X1 is X - 1,
    X1 > 0 , X1 < 11,
    getAllPathsRec(X1,Y).
move(up, X, Y) :-
    Y1 is Y + 1,
    Y1 > 0 , Y1 < 11,
    getAllPathsRec(X,Y1).
move(down, X, Y) :-
    Y1 is Y - 1,
    Y1 > 0 , Y1 < 11,
    getAllPathsRec(X,Y1).

Я ожидаю найти золото любым возможным способом, в идеале печатая каждый путьалгоритм взял.Заранее спасибо.

Answer 1

РЕДАКТИРОВАТЬ:

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

---

Будьте осторожны с предикатом assert/1, так как он постоянно добавляет факт в базу знаний, и он не отменяется при использовании других комбинаций,так что вы не сможете дважды посетить одну и ту же ячейку.

Вместо этого я подошел к ней с дополнительным параметром V (означает посещенный), в который можно добавить элемент, обработанный вкаждый шаг исследования.Также я сохранил выбранные направления на каждом шаге в списке L, чтобы распечатать его, когда цель будет найдена.

Оператор or ; позволяет не продолжать исследовать один и тот же путь, как только цель найдена, ивозвращается, чтобы продолжить пробовать другие комбинации.

---

Примечания:

• Если вы сталкиваетесь с любым вариантом использования, где вы можете использовать assert/1, будьте осторожны, потому что устарело .

• Переменная _ не нужна в функции перемещения, так как вы можете просто добавить 4 разные "реализации" и простодобавьте четыре направления.

• В качестве совета используйте факты или знания (такие как размер мира, позиция цели и позиция игрока) в качестве переменных и не программируйте их жестко.Будет проще отлаживать и пробовать разные параметры.

---

Здесь у вас есть рабочий код и пример вывода:

:- dynamic 
    getAllPathsRec/2,
    agent/2,
    visited/2.

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

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

getAllPathsRec(X, Y, V, L) :-
    hashPos(X, Y, H), \+member(H, V), append(V, [H], VP),
    ((gold(X, Y), print(L)) ; move(X, Y, VP, L)).

% Hash H from h(X, Y)
hashPos(X, Y, H) :- H is (X*100 + Y).

% 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.
[r,r,r,r,u,l,l,l,l,u,r,r]
true ;
[r,r,r,r,u,l,l,l,l,u,r,u,l,u,r,r,r,r,d,l,l,d]
true ;
[r,r,r,r,u,l,l,l,l,u,r,u,l,u,r,r,r,r,d,l,d,l]
true ;
[r,r,r,r,u,l,l,l,l,u,r,u,l,u,r,r,r,r,d,d,l,l]
true ;
[r,r,r,r,u,l,l,l,l,u,r,u,l,u,r,r,r,r,d,d,l,u,l,d]
true ;
[r,r,r,r,u,l,l,l,l,u,r,u,l,u,r,r,r,d,l,d]
true ;
[r,r,r,r,u,l,l,l,l,u,r,u,l,u,r,r,r,d,r,d,l,l]
true ;
[r,r,r,r,u,l,l,l,l,u,r,u,l,u,r,r,r,d,d,l]
...