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

Question

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

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

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

1

prolog logic-programming sicstus-prolog

Источник

user760091 20 май '12 в 22:32

3 ответа

Другие вопросы по тегам prolog logic-programming sicstus-prolog

user849891 25 май '12 в 07:01 2012-05-25 07:01 · Answer 1 · 2012-05-25 07:01

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

user634629 21 май '12 в 20:56 2012-05-21 20:56 · Answer 2 · 2012-05-21 20:56

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

1

Источник

user634629 21 май '12 в 20:56

user1000818 21 май '12 в 06:15 2012-05-21 06:15 · Answer 3 · 2012-05-21 06:15

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