algorithm - Prologプログラムの複雑さ？

Question

Prologでは、問題はバックトラッキングを使用して解決されます。これは、命令型（C、PHP、Pythonなど）ではなく、宣言型のパラダイムです。この種の言語では、複雑さの観点から考える価値がありますか？

この質問で誰かが指摘したように、問題を考える自然な方法はO（N ^ 2）のようです。

Answer 1

他の言語と同じように、Prolog プログラムの複雑さを確実に分析できます。あなたがリンクした特定の問題は、O(n^2) かもしれません。しかし、すべての Prolog プログラムがこの複雑さを持つわけではありません。たとえば、SAT ソルバーは Prolog で簡単に作成でき、その問題は NP-Complete です。

Answer 2

それは完全に問題に依存します。

たとえば、私が知る限り、数値のリストの合計は O(N) です。

sum([],0).
sum(List,Total) :-
   sum(List,0,Total).

sum([],Total,Total).
sum([Head|Rest],Accumulator,Total) :-
    SoFar is Head + Accumulator,
    sum(Rest,SoFar,Total).

唯一のアクションは加算 ("is") と再帰呼び出しで、どちらもそれぞれ 1 の価値があります。どちらもリスト内のアイテムごとに ~ 1 回実行されるため、合計アクションは ~ 2N、つまり O(N) になるはずです。

Answer 3

プロローグ言語であろうと命令型言語であろうと、あらゆる言語の複雑さを分析することが重要です。ただし、プロローグ プログラムを高速化するためのヒントをいくつか提供できます。

1. Always 常にプログラムを末尾再帰にするようにします。これにより、プログラムがスタック不足にならないようになります。
2. これ以上の答えが必要ないことがわかっているプログラムでは、cut and fail を使用してみてください。
3. アキュムレータを使用してみてください。
4. CLPFD を確認してください。検索スペースを大幅に削減し、プログラムを高速化するのに役立ちます。基本的に、プログラムがバックトラックしてそれらの選択を調査する時間を浪費する前に、悪い選択を排除します。
5. 常に最良の結果のルールを最初に記述します。(これは実際には問題によって異なりますが、通常は最良のケースのルールが最初に適用されます)。