3

ピタゴラストリプルのXとYで終了することになっている上限変数Nを使用するこのコードがあります。ただし、上限に達したときにのみフリーズします。カットを使用してバックトラックを停止する方法がわかりませんでした。コードは次のとおりです。

is_int(0).
is_int(X) :- is_int(Y), X is Y+1.
minus(S,S,0).
minus(S,D1,D2) :- S>0, S1 is S-1, minus(S1,D1,D3), D2 is D3+1.

pythag(X,Y,Z,N) :- int_triple(X,Y,Z,N), Z*Z =:= X*X + Y*Y.

int_triple(X,Y,Z,N) :- is_int(S), minus(S,X,S1), X>0, X<N,
                                  minus(S1,Y,Z), Y>0, Y<N.

たとえば、と呼ばれます

?- pythag(X,Y,Z,20).
4

2 に答える 2

6

まず、ソリューションをテストしましょう。

？-ピタゴラス（X、Y、Z、20）。
X = 4、
Y = 3、
Z = 5;
X = 3、
Y = 4、
Z = 5;
X = 8、
Y = 6、
Z = 10;
X = 6、
Y = 8、
Z = 10;
X = 12、
Y = 5、
Z = 13;
X = 5、
Y = 12、
Z = 13;
X = 12、
Y = 9、
Z = 15;
X = 9、
Y = 12、
Z = 15;
X = 15、
Y = 8、
Z = 17;
X = 8、
Y = 15、
Z = 17;
X = 16、
Y = 12、
Z = 20;
X = 12、
Y = 16、
Z =20..。

私には完璧に見えます！すべての答えは正しい解決策です！...この最後の解決策まで。その後、プログラムがループします。

問題を特定する前に、しばらくお待ちください。そのループを見つけるためだけに12（つまり、12）の回答を通過するのはかなり辛抱強くなければなりません。この方法は、より大きなケースでも機能すると思いますか？諦める前にいくつの答えを見ても構わないと思いますか？問題を見つけるためのより簡単な方法はありませんか？

ここに興味深い観察が1つあります。見つかった答えは（ほとんど）プログラムのループとは何の関係もありません。つまり、答えを見ると、（この場合のように）ループの実際の原因についての手がかりが得られません。だから、すべての答えをオフにして、関連する部分に集中してみませんか？実際、これは次のように実行できます。

？-pythag（X、Y、Z、20）、false。
**ループ**

これで、目標のためにすべての回答が削除されましたfalse。残っているのは、最終的な結果です。つまり、終了、非終了、または何らかのエラーです。他には何もありません。これにより、終了についての観察が少し容易になります。画面上をスクロールする目がくらむような答えはもうありません。これは一般的に問題を解決しないことに注意してください。結局のところ、私たちはどれくらい待つつもりですか？1秒？1メートル？

非終了の実際の理由は、関連する障害スライスを調べることで最もよく理解できます。これはプログラムの断片であり、その非終了はプログラム全体の非終了を意味します。詳細については、この回答を参照してください。クエリに関連するプログラムの失敗スライスは次のpythag(X,Y,Z,20), falseとおりです。

ピタゴラス（X、Y、Z、N）：-
   int_triple（X、Y、Z、N）、false、
    Z * Z =：= X * X + Y*Y。

int_triple（X、Y、Z、N）：-
   is_int（S）、false、
    minus（S、X、S1）、X> 0、X <N、
    minus（S1、Y、Z）、Y> 0、Y<N。

is_int（0）：-false。
is_int（X）：-
   is_int（Y）、false、
   XはY+1です。

プログラムには多くのものが残っていないことに注意してください。たとえば、実際の方程式はなくなりました（これは多かれ少なかれ論理的な部分です...）。それでも、このフラグメントは関連しています。そして、そのフラグメント内で何かを変更しない限り、問題は解決しません！これは、このような純粋な単調プログラムで保証されています...

これが私の好ましい解決策です：それはlength/2、Prologプロローグbetween/3の2つの頻繁にサポートされる述語を使用します。

pythag2（X、Y、Z、N）：-
   長さ（_、N）、
   between（1、N、X）、
   between（1、N、Y）、
   between（1、N、Z）、
   Z * Z =：= X * X + Y*Y。
于 2012-05-09T13:22:16.780 に答える
3

私は最近、ピタゴラストリプルを見つけるためのPrologソリューションについても考えていました。少し違うコードを思いついた。次の関数があると仮定します。

isqrt(a) = floor(sqrt(a))

次に、xとyを列挙し、x * x + y*yがいくつかのzの2乗であるかどうかを確認するだけで十分です。つまり、以下をチェックします。

h = x*x+y*y, z = isqrt(h), z*z = h ?

関数isqrtは、bisectionを介して実装できます。対称性の破れの場合、xの後にyを列挙できます。N = 99と仮定すると、結果のコードは次のようになります。

% between(+Integer, +Integer, -Integer)
between(Lo, Hi, _) :-
   Lo > Hi, !, fail.
between(Lo, _, Lo).
between(Lo, Hi, X) :-
   Lo2 is Lo+1, between(Lo2, Hi, X).

% bisect(+Integer, +Integer, +Integer, -Integer)
bisect(Lo, Hi, X, Y) :-
    Lo+1 < Hi, !,
    M is (Lo+Hi) // 2,
    S is M*M,
    (S > X -> bisect(Lo, M, X, Y);
     S < X -> bisect(M, Hi, X, Y);
     M = Y).
bisect(Lo, _, _, Lo).

% pythago(-List)
pythago(X) :-
   X = [A,B,C],
   between(1, 99, A),
   between(A, 99, B),
   H is A*A+B*B,
   bisect(0, H, H, C),
   C =< 99, H =:= C*C.

そのようなピタゴラスの三重項が50個あるはずです。SloanのA046083も参照してください。

?- findall(-, pythago(_), L), length(L, N).
N = 52.

次のCLP（FD）ソリューションとクロスチェックすることをお勧めします。

:- use_module(library(clpfd)).

% pythago3(-List)
pythago3(X) :-
   X = [A,B,C],
   X ins 1..99,
   A*A+B*B #= C*C,
   A #=< B,
   label(X).

それは同じ数の解決策を与えます：

?- findall(-, pythago3(_), L), length(L, N).
N = 50.
于 2013-08-31T21:06:01.080 に答える