3

私は再帰を持っています：

list_to_set([],[]).

list_to_set([A|X],[A|Y]):-
   list_to_set(X,Y),
    \+member(A,Y).

list_to_set([A|X],Y):-
   list_to_set(X,Y),
   member(A,Y).

要素のリストをセットに変換します。たとえば、[1,1,2,3] -> [1,2,3]。クエリを入力するとlist_to_set([1,1,2,3],X).、結果はX = (1,2,3)であり、セットを見つけることの複雑さは ですO(n)。;これで、他に考えられる答えがないことを確認するために、alternative を入力できます。明らかに何もなく、スクリプトは を返しfalseます。私の質問は、その 2 回目のスクリプト実行の計算上の複雑さはどのくらいですか? またその理由は?

4

1 に答える 1

5

あなたのプログラムでは、最悪の場合、最初の答えを見つけることは指数関数的です。そして、それは最良の場合二次です。

これは、指数関数的に多くの推論を行う具体的なクエリです。

?- length(L,N),maplist(=(a),L),time(once(list_to_set(L,S))).
...
% 1,310,714 inferences, 0.180 CPU in 0.180 seconds (100% CPU, 7288089 Lips)
L = [a, a, a, a, a, a, a, a, a|...],
N = 18,
S = [a] ;
% 2,621,434 inferences, 0.337 CPU in 0.337 seconds (100% CPU, 7789752 Lips)
L = [a, a, a, a, a, a, a, a, a|...],
N = 19,
S = [a] ...

通常Goal, false、最初の答えだけを見つけるために複雑さを判断するよりも、（プログラムが本質的に純粋なPrologプログラムである場合）の複雑さを判断する方が簡単です。その理由は、前者は節の正確な順序とは無関係であるためです。ただし、どちらも目標の順序によって異なります。

下限の正当性については、この回答を参照してください。

編集：おそらく最も興味深い観察はこれです：この問題を修正したい場合、つまり実行される推論の数を減らしたい場合は、障害スライスの表示部分の何かを変更する必要があります。

于 2013-01-24T16:09:52.003 に答える