prolog - prolog 最小値検索クエリ

Question

次の形式の事実がある場合：

person(name,age).

最年少の人を見つけるクエリを作成するにはどうすればよいですか?

再帰を使用してみましたが、無限ループに陥り続けました。これまでに行ったすべての読み取りから、! を使用する必要があることがわかりました。カットオペレーター。どんな助けでも大歓迎です。

Answer 1

もちろん、カット演算子を使用する必要はありません。そのソリューションがどのようなものになるか想像するのは難しいです。

最も簡単なことは、次のようなクエリを作成することです。

youngest(person(Name,Age)) :-
  person(Name, Age),
  \+ (person(Name2,Age2), Name2 \= Name, Age2 < Age).

残念ながら、これはあまり効率的ではありません。1 人につき 1 回データベースを検索する必要があり、O(N^2) のパフォーマンスにつながるからです。しかし、なぜそれが機能するのかは明らかです。

より迅速な解決策は、 を使用することsetof/3です。

youngest(person(Name, Age)) :-
  setof(Age-Name, person(Name,Age), [Age-Name|_]).

setof/3がリストをソートし、これが機能するために最も若い人が結果リストの先頭に移動するという事実に依存しています。パフォーマンスは向上しますが、すべてが明確に読み取れるわけではありません。

この種の問題を SWI で解決するために使用できる標準ライブラリがありますが、SWI を使用しているかどうかはわかりませんし、私自身も使用していませんが、調べてみてください。それは集計と呼ばれます。

もう 1 つのアプローチは、データベースを直接実体化しfindall/3、それを行うためだけに記述された述語を使用して最小値を直接見つけることです。そのような解決策は、おそらく次のようになります。

youngest(Person) :-
  findall(person(Name,Age), person(Name,Age), [P1|Rest]),
  youngest(P1, Rest, Person).

youngest(Person, [], Person).
youngest(person(Name, Age), [person(N2,A2)|Rest], Person) :-
  Age < A2 -> youngest(person(Name, Age), Rest, Person)
            ; youngest(person(N2, A2),    Rest, Person).

ただし、おそらく最高のパフォーマンスが得られるとはいえ、これは大変な作業のように思えます (線形時間である必要があります)。

Answer 2

ダニエル（+1）による（非常に完全な）回答に追加するだけです：ライブラリ（集約）はそのような検索を行うことができます-そしてもっと：

youngest(Person) :-
    aggregate(min(Age,Pers), person(Pers,Age), min(_, Person)).

Prolog はデータベースに類似しており、この言語には集約演算子が欠けているため、勉強する価値があると思います。