Распространение состояния при бактрекинге в Прологе

Предположим, у меня есть простая программа на Прологе, которая ищет в определенном пространстве состояний:

search(State, State) :-
    is_solution(State).

search(State, Solution) :-
    generate(State, NewState),
    search(NewState, Solution).

И я знаю, что:

  • generate(State, NewState) производит по крайней мере один NewState для любого данного State
  • все пространство состояний конечно

Я хочу изменить search Предикат, чтобы убедиться, что всегда удается проверить в конечное время. Поэтому я пишу что-то вроде:

search(State, Solution) :-
    empty_memory(EmptyMem),
    add(State, EmptyMem, Memory),
    search(State, Memory, Solution).

search(State, _, State) :-
    is_solution(State).

search(State, Memory, Solution) :-
    generate(State, NewState),
    \+ exist(NewState, Memory),
    add(NewState, Memory, NewMemory),
    search(NewState, NewMemory, Solution).

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

Есть ли способ распространять состояние во время возврата без потери какой-либо вычисленной информации? Я хочу иметь целое дерево поиска с O(space_size) узлами. Является ли это возможным?

РЕДАКТИРОВАТЬ: Кажется, что я должен использовать assert/[1,2] для того, чтобы динамически создавать новые предложения, которые будут служить в качестве глобальной памяти.

3 ответа

Вместо того, чтобы использовать assertпочему бы не генерировать все возможные состояния с findall(N, generate(S,N),ALL), Это исключит необходимость обратного отслеживания и расшифрует дерево пространства поиска, которое затем можно будет пройти по предварительному заказу при передаче состояний, посещенных до сих пор, в качестве дополнительного аргумента.

Наиболее чистым решением, вероятно, будет использование компилятора Prolog, который поддерживает табулирование, например B-Prolog, Ciao, XSB или YAP. В этом случае вы просто объявите предикат generate/2 как tabled.

В SICStus Prolog вы можете использовать классную доску для хранения информации между задними дорожками: см. Примитивы классной доски в руководстве. использование bb_put(Key, Value) хранить что-то на доске, и bb_get(Key, Value) чтобы получить это. Обратите внимание, что блок управления определяется для каждого модуля.

Другие вопросы по тегам