2

座標のリストがあり、ポイントに最も近いものを取得したいという問題を解決しようとしています。

例: 座標 [[1,2],[3,4],[10,3]] を取得し、原点 [0,0] に最も近い点を取得したいと考えています。[1,2] この例では。

私はこれを書きました：

list_min([H|T], Min):-
   list_min(T, H, Min).

list_min([], H, H).

list_min([L|Ls], Min0, Min) :-
    point(P),
    distance(Min0,P,D0),
    distance(L,P,D1),
    Lower is min(D0, D1),
    assert(candidate(Min0)),
    assert(candidate(L)),
    forall(candidate(X),distance(X,P,Lower)),
    retractall(candidate(_)),
    list_min(Ls, X, Min).

distance(A,B,D):-
    A = [A1,A2],
    B = [B1,B2],
    Y is B2 - A2,
    X is B1 - A1,
    D is sqrt(X*X + Y*Y).

ただし、forall行では常に失敗するようです。私が間違っているのは何ですか？これを行うためのより良い方法はありますか？

4

4 に答える 4

2

library（ aggregate ）を使用できます：

distance_min(L, MinXY) :-
    distance_min(L, 0, 0, MinXY).
distance_min(L, X0, Y0, MinXY) :-
    aggregate(min(D, [X,Y]),
              (member([X,Y], L), D is sqrt((X-X0)^2+(Y-Y0)^2)),
              MinXY).

テスト：

?- distance_min([[1,2],[3,4],[10,3]], R).
R = min(2.23606797749979, [1, 2]).

編集

....
assert(candidate(Min0)),
assert(candidate(L)),
forall(candidate(X),distance(X,P,Lower)),
retractall(candidate(_)),
...

私はあなたのコードにコメントしませんでしたが、ここにヒントがあります：これらの行は本当に悪いスタイルで、本当に役に立たないです。forall / 2の成功を認めて、あなたはどのような結果を期待しますか？

とにかく、forall / 2はLower上記のステートメント（Lower is min(D0, D1)）からすでにインスタンス化されているため失敗します。したがって、distance/3はD一致しない場合は失敗します。

于 2012-08-29T23:49:51.130 に答える
2

SWI-Prolog では、機能的なスタイルも使用できます。

:- use_module(library(lambda)).


point([0,0]). % The reference point

% Entry point predicate
% First parameter : a list of points
% Second parameter (result) : the point closest to the reference point
list_min([H|Tail], Min) :-
  point(Reference),
  distance(H, Reference, D),

  foldl(\X^Y^Z^(distance(X, Reference, DX),
                Y = [Cur_D, _Cur_P],
                (   DX < Cur_D
                ->  Z = [DX, X]
                ;   Z = Y)),
    Tail, [D, H], Min).


distance(A,B,D):- % copy-pasted from your version
  A = [A1,A2],
  B = [B1,B2],
  Y is B2 - A2,
  X is B1 - A1,
  D is sqrt(X*X + Y*Y).
于 2012-08-30T22:46:31.003 に答える
1

私は提案されたライブラリまたはクアッドツリーなしで解決策を提案します、私は基本的なプロローグにとどまります（私はSWIで書きます）。

私があなたの問題を正しく理解していれば、実際には//の必要はありませassertん。Pは、距離を計算するための一意に定義された参照点であると仮定しますが、少し奇妙です（一意であることを確認するために、パラメーターとして使用します）。retractforallpoint(P)

point([0,0]). % The reference point

% Entry point predicate
% First parameter : a list of points
% Second parameter (result) : the point closest to the reference point
list_min([H|Tail], Min) :-
  point(Reference),
  distance(H, Reference, D),
  list_min(Tail, H, D, Min).

% First parameter : the list remaining to consider
% Second parameter : the closest point, at this point of the computation
% Third parameter : the corresponding (minimum) distance, at this point of the computation
% Fourth parameter : the result (one point, to be bound at the end of computation)
list_min([], CurrentMin, _, CurrentMin). % Stop condition : list processed
list_min([Candidate|Tail], CurrentMin, CurrentDist, Min) :-
  point(Reference),
  distance(Candidate, Reference, CandidateDist),
  (
   % if the new candidate is not better, keep the current candidate
   CurrentDist < CandidateDist ->
   list_min(Tail, CurrentMin, CurrentDist, Min)
  ;
   % if the new candidate is better, take it as the current candidate
   list_min(Tail, Candidate, CandidateDist, Min) 
   ).

distance(A,B,D):- % copy-pasted from your version
  A = [A1,A2],
  B = [B1,B2],
  Y is B2 - A2,
  X is B1 - A1,
  D is sqrt(X*X + Y*Y).
于 2012-08-30T13:20:51.783 に答える
0

2D に四分木を使用http://en.wikipedia.org/wiki/Quadtree

于 2012-08-29T23:07:40.710 に答える