Распространение состояния при бактрекинге в Прологе
Предположим, у меня есть простая программа на Прологе, которая ищет в определенном пространстве состояний:
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)
чтобы получить это. Обратите внимание, что блок управления определяется для каждого модуля.