1

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]グローバルメモリとして機能する新しい句を動的に作成するために 使用する必要があるようです。

4

3 に答える 3

1

を使用する代わりに、assert可能なすべての状態を で生成してみませんかfindall(N, generate(S,N),ALL)。これにより、バックトラックの必要がなくなり、検索空間ツリーが説明されます。これにより、追加の引数として訪問済みの状態を渡しながら、事前に走査することができます。

于 2012-05-25T07:01:35.153 に答える
1

最もクリーンなソリューションは、B-Prolog、Ciao、XSB、または YAP などのテーブルをサポートする Prolog コンパイラを使用することです。この場合、generate/2 述語を tableed として宣言するだけです。

于 2012-05-21T20:56:47.287 に答える
1

SICStus Prolog では、黒板を使用してバックトラック全体に情報を保存できます。マニュアルのBlackboard Primitivesを参照してください。bb_put(Key, Value)黒板に何かを保管したりbb_get(Key, Value)、取り出したりするために使用します。ブロックボードはモジュールごとに定義されることに注意してください。

于 2012-05-21T06:15:38.667 に答える