Prolog に、特定の状態空間を検索する単純なプログラムがあるとします。
search(State, State) :-
is_solution(State).
search(State, Solution) :-
generate(State, NewState),
search(NewState, Solution).
そして、私はそれを知っています:
generate(State, NewState)
NewState
与えられたものに対して少なくとも 1 つを生成している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]
グローバルメモリとして機能する新しい句を動的に作成するために
使用する必要があるようです。