2

私はPrologの初心者ですが、Prologについて質問したいと思います。

私のプログラムは、非決定論的有限状態オートマトンに基づいています。

開始状態はS0で、最終状態はS3です。

図は

ここに画像の説明を入力してください

したがって、文字列がある場合は、次の[a,a,b,b,c,c]ようになります。

start(s0).
edge(a, s0, s0).
edge(a, s0, s1).
edge(b, s1, s1).
edge(b, s1, s2).
edge(c, s2, s2).
edge(c, s2, s3).
final(s3).

（文字列のリストがある）accepts(Ls)場合の述語がありますLs

accepts(Ls) :- start(A), goesTo(Ls, A, B), final(B).

NFAが状態Siから状態Sjに移行し、その間に状態Skがあると仮定すると、goesTo述語は次のように定義されます。

goesTo(Ls, Si, Sj) :- edge (L, Si, Sk), goesTo(Ls, Sk, Sj).

しかし、クエリ（からまでaccepts(Ls)の範囲の文字列の任意のリスト）を実行すると、チュートリアルの質問は、ほぼ確実に無限の検索に入り、スタックオーバーフローが発生することを示しています。ac

ただし、クエリが無限検索になり、スタックオーバーフローが発生する理由がわかりません。理由を教えていただければ、本当に素晴らしいです！

（編集:)正確な見積もりは次のとおりです。

「典型的なPrologユーザーは、自分のgoesToルールが、クエリaccepts（X）が上記のNFAによって受け入れられる連続した文字列を生成するようなものになることを期待するかもしれません。ほぼ確実に、特定のNFAの上記のプレゼンテーションを考えると、Prologシステムは無限の検索に入り、スタックオーバーフローが発生します。なぜそうなのかを説明してください（この問題を回避するには、どうやって回避したかを説明してください）。」

4

3 に答える 3

2

これは、NFA の定義です。

start(s0). 
edge(a, s0, s0). 
edge(a, s0, s1). 
edge(b, s1, s1). 
edge(b, s1, s2).
edge(c, s2, s2). 
edge(c, s2, s3).
final(s3).

それによる受け入れをテストする可能性のある入力文字列には関係ありません。各行の末尾にあるドットに注意してください。これらは、NFA を定義する Prolog 述語です。

具体的な入力文字列でyouraccepts/1を実行 すると、有限再帰が発生します。ここでの検索スペースは有限であり、完全にインスタンス化された有限の長さの文字列で呼び出した場合、確実に使い果たされます。accepts/1

ここで、可能なすべてのパスの受け入れ可能な文字列を生成しようとすると、無限の数の受け入れ可能な文字列があるため、無限の再帰が発生します。

a,b,c
a,a,b,c
a,a,a,b,c
a,a,a,a,b,c
.....

このオートマトンで受け入れられるすべての文字列です。

あなたの述語定義はすべて最後のドットBTWを欠いています。そして、それgoesToはまったく正しくありません。次のように変更する必要があります。

goesTo([], S, S).
goesTo([L1|Ls], S1, Sn) :- edge(L1, S1, S2), goesTo(Ls, S2, Sn).
accepts(Ls) :- start(A), goesTo(Ls, A, B), final(B).

また、述語名と左括弧の間にスペースを入れてはならないことに注意してください。

そのため、OPは質問を明確にしました。それは、

可能なすべての許容可能な文字列を生成しようとすると、ほぼ確実に非生産的なループに陥るのはなぜですか?

試行する新しいノードの生成が最初から再開されるため、呼び出しはaccepts(X)実際に無限再帰に入ります。したがって、内部的に、無限に成長するas の文字列が試行されます。

a
a,a
a,a,a
a,a,a,a
....

がデータベースのedge(a,s0,s0)最初の事実であり、への呼び出しが述語定義内の最初の位置にあるという理由だけです。また、Prolog の検索戦略は左から右です。edgeedge/3goesTo/3

次のように目標を再配置することで、完全に非生産的な動作 (Prolog が無限ループにハングアップするだけ) から生産的な動作に移行できます。

start(s0). 
edge(a, s0, s1). 
edge(b, s1, s2).
edge(c, s2, s3).
edge(a, s0, s0). 
edge(b, s1, s1). 
edge(c, s2, s2). 
final(s3).

今、

12 ?- accepts(X).

X = [a, b, c] ;
X = [a, b, c, c] ;
X = [a, b, c, c, c] ;
X = [a, b, c, c, c, c] ;
X = [a, b, c, c, c, c, c] ;
X = [a, b, c, c, c, c, c, c] ;
X = [a, b, c, c, c, c, c, c, c]

残念ながら、世代が に偏っていることがわかりcます。どうすれば「公平」にできるか……それはまた別の質問にしましょう。

于 2012-10-05T13:49:07.320 に答える
1

Prolog で採用されている検索戦略のため、プログラムはループします。これは、深さ優先戦略を使用してソリューション空間を探索するクエリを解決しようとします。これは空間効率は良いですが不完全です。

グラフ内のこれらのループのために、解空間があなたのケースでは無限であることは明らかです。初期状態から最終状態まで無限の経路があります。

反復的な深化は、パスを列挙するためのより簡単な方法である必要があり、Prolog で簡単に実装できます。別の可能性は、幅優先検索を実装することです。

于 2012-10-05T16:49:43.583 に答える
1

他の人が述べたようにループだからです。

ps 課題は今週の木曜日まで延長されたので、慌てる必要はありません [まだ] そしてええ、私はあなたが何の課題をしているか知っています

于 2012-10-07T05:55:43.030 に答える