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

您可以使用库（聚合）：

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/ retract/ 。forall我假设point(P)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

使用二维四叉树http://en.wikipedia.org/wiki/Quadtree

于 2012-08-29T23:07:40.710 回答