如何将最小距离返回到某个点？

Question

我想解决一个问题，我有一个坐标列表，并希望得到最接近点。

例如： 我得到了坐标[[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线失败。我做错了什么？有没有更好的方法来做到这一点？

Answer 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). 

Answer 2

使用四叉树的2D http://en.wikipedia.org/wiki/Quadtree

Answer 3

你可以使用库（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(_)), 
... 

我没有评论你的代码，但现在有一个提示：这些代码真的很糟糕，真的没用。承认全部/ 2次成功，你期望什么结果？

无论如何，因为Lower它已经从上面的语句（Lower is min(D0, D1)）实例化，因此距离/ 3将失败，其中D不匹配。

Answer 4

随着SWI-Prolog的，你也可以使用一个functionnal风格：

:- 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).