Abstände zwischen Vektoren in einer Liste im Prolog enthalten

Question

Ich bin ganz neu in Prolog und ich versuche, ein Prädikat

distance_all(List, List_of_distances). 

, dessen Eingang eine Liste der Liste cointaining Vektor coohordinates zu schreiben:

INPUT = [1,2,3], [2,3,4], [1,7,3], [1,6,3]]

und geben Sie eine Liste aus, die den gesamten Abstand zwischen den einzelnen Punkten enthält andere.

Ich habe es so gemacht, aber (tut mir leid den schlechten Pseudo-Code). Ich weiß wirklich nicht, wie man in Prolog damit umgeht!

1. Abstand (Punkt1, point2) = D_1-2

   Abstand (Punkt1, point3) = D_1-3

   bis Distanz (point1, last_point) = D_1-last

   Abstand (point2, point3) = D_2-3

   Abstand (point2, Point4) = D_2-4

   d istance (point2, last_point) = D_2 letzte am so weiter ...

so dass der Ausgang ist wie

OUTPUT = [D_1-2, D_1-3, ....., D_1-zuletzt, D_2-3, D_2-4, ..... D_2-zuletzt ...].

Ich habe bereits implementiert ein Prädikat

Abstand (Vektor1, Vector2, D).

wobei D der euklidische Abstand zwischen Vektor1 und Vector2 (in 2D, 3D oder was auch immer)

---

Eine andere Frage

Was passiert, wenn ich die ursprünglichen Vektoren erinnern wollen, dass der Mindestabstand entstanden?

zum Beispiel

- distance_all ([[1,1], [1,2], [6,3], [8,2]], Lo). Lo = [1,0, 5,385164807134504, 7,0710678118654755, 5,0990195135927845, 7,0, 2,23606797749979]

der Mindestabstand beträgt 1,0 ... Aber zwischen Wich Vektoren? A B

Answer 1

Was

distance_all_h(_, [], [], []). 

distance_all_h(_, [], [Hn | Tn], Lo) :- 
    distance_all_h(Hn, Tn, Tn, Lo). 

distance_all_h(V, [Hi | Ti], Ln, [Ho | Lo]) :- 
    distance(V, Hi, Ho), 
    distance_all_h(V, Ti, Ln, Lo). 

distance_all([], []). 

distance_all([Hi | Ti], Lo) :- 
    distance_all_h(Hi, Ti, Ti, Lo). 

können sagen, waren A und B

brauche ich auf diejenigen ein weiteres Prädikat zu benutzen?

Wenn die Eingabeliste leer ist, ist die Ausgabeliste leer.

Ansonsten ist die Idee ist es, eine Helfer-Klausel erstellen (distance_all_h/3), die

1) der Kopf der Eingabeliste

2) dem Ende der Eingabeliste erhalten (to calcolate die Abstände mit der Kopf)

3) der Schwanz der Eingabeliste wieder (mit folgendem Kopf neu zu starten, wenn das zweite Argument verbraucht wird)

4) die Ausgabeliste

--- EDIT ---

Was passiert, wenn ich die ursprünglichen Vektoren erinnern mag, dass der Mindestabstand entstanden?

Modifizierte Lösung den Mindestabstand (dritten Parameter in distance_all) und eine Liste von Paaren von Vektor zurückzugeben, die auf minimalen Abstand (vierte Parameter)

Nimm in Zahl entsprechen, die mehr Paare von Vektor entsprechen, können der gleiche Mindestabstand.

% 1000000000 is intended as a number bigger than every distance 
distance_all_h(_, [], [], [], 1000000000, []). 

distance_all_h(_, [], [Hn | Tn], Lo, Md, ABl) :- 
    distance_all_h(Hn, Tn, Tn, Lo, Md, ABl). 

distance_all_h(V, [Hi | Ti], Ln, [Ho | Lo], Ho, [[V, Hi]]) :- 
    distance(V, Hi, Ho), 
    distance_all_h(V, Ti, Ln, Lo, Dd, _), 
    Ho < Dd. 

distance_all_h(V, [Hi | Ti], Ln, [Ho | Lo], Dd, ABl) :- 
    distance(V, Hi, Ho), 
    distance_all_h(V, Ti, Ln, Lo, Dd, ABl), 
    Ho > Dd. 

distance_all_h(V, [Hi | Ti], Ln, [Ho | Lo], Ho, [[V, Hi] | ABt]) :- 
    distance(V, Hi, Ho), 
    distance_all_h(V, Ti, Ln, Lo, Ho, ABt). 

distance_all([], [], 0, []). 

distance_all([Hi | Ti], Lo, Md, ABl) :- 
    distance_all_h(Hi, Ti, Ti, Lo, Md, ABl). 

Answer 2

Sie könnten schreiben:

distance_all(Input_list,Output_list):- 
     findall(L,combinations(Input_list,L),List), 
     find_distances(List,Output_list). 

combinations([],[]). 
combinations(Lin,[Vector1,Vector2]):-choose(Vector1,Lin,L),choose(Vector2,L,_). 

choose(H,[H|T],T). 
choose(H1,[_|T],T1):-choose(H1,T,T1). 

find_distances([],[]). 
find_distances([[Vector1,Vector2]|T],[D|T1]):- 
     distance(Vector1,Vector2,D), 
     find_distances(T,T1). 

UPDATE

für die zweite Frage könnte man ändern:

find_distances([],[]). 
find_distances([[Vector1,Vector2]|T],[D-[Vector1,Vector2]|T1]):- 
      distance(Vector1,Vector2,D), 
      find_distances(T,T1). 

Anstatt also die Liste der Entfernungen zurückzugeben, wird es codiert, so dass jedes Element in der Form von: D-[Vector-n,Vector-m]

0 sein wird

distance_all(Input_list,Output_list):- 
     findall(L,combinations(Input_list,L),List), 
     find_distances(List,L1), 
     keysort(L1,L2), 
     find_distances2(L2,Output_list). 

Keysort die Liste sortieren, so dass das erste Element min d hat und Sie es durch Zugabe von oben zum Beispiel nehmen:

Um min Entfernung Verwendung keysort/2 zu finden L1=[Dmin-[Vector1,Vector2]|_]. L1

seit der Liste erklärte das Formular oben, um die Ausgabeliste Ihrer ersten Frage zu bekommen Sie einfach nur Abstände in der Ausgabeliste durch Schreiben halten können:

find_distances([],[]). 
find_distances([D-[Vector1,Vector2]|T],[D|T1]):-find_distances(T,T1). 

Answer 3

wenn Ihr Prolog Bibliothek (aggregate), und es Ihnen nichts ausmacht über Effizienz, die Sie tun können

distance_min(List, MinDist,P1,P2) :- 
    aggregate(min(D,(X,Y)), R^(select(X,List,R),member(Y,R), distance(X,Y,D)), min(MinDist,(P1,P2))). 

distance([X1,X2],[Y1,Y2],D) :- 
    D is sqrt((Y1-X1)*(Y1-X1)+(Y2-X2)*(Y2-X2)). 
distance([X1,X2,X3],[Y1,Y2,Y3],D) :- 
    D is sqrt((Y1-X1)*(Y1-X1)+(Y2-X2)*(Y2-X2)+(Y3-X3)*(Y3-X3)). 

?- distance_min([[1,1],[1,2],[6,3],[8,2]],D,X,Y). 
D = 1.0, 
X = [1, 1], 
Y = [1, 2]. 

Answer 4

Eine mäßig kurze und einfache Art und Weise, es zu schreiben, ohne findall und aggregate und so geht so etwas.

Zuerst wird ein Prädikat, das zwischen zwei Listen von Koordinaten, die die euklidische Distanz findet:

d([P|Ps], [Q|Qs], D) :- 
     sum_diff_sq(Ps, Qs, (P-Q)^2, R), 
     D is sqrt(R). 

sum_diff_sq([], [], V, V). 
sum_diff_sq([P|Ps], [Q|Qs], V0, V+V0) :- 
     sum_diff_sq(Ps, Qs, (P-Q)^2, V). 

Dies wird die Berechnung der Entfernung zwischen einem Paar von Koordinaten, die jeweils eine Liste von Zahlen.

?- d([1], [1], D). 
D = 0.0. 

?- d([1], [2], D). 
D = 1.0. 

?- d([1,1], [2,2], D). 
D = 1.4142135623730951. 

?- d([1,1,1], [2,2,2], D). 
D = 1.7320508075688772. 

?- d([1,1,1,1], [2,2,2,2], D). 
D = 2.0. 

Dann werden alle möglichen Abstände zu berechnen:

points_distances([], []). 
points_distances([P|Ps], Ds) :- 
     rest_distances(Ps, P, Ds, Ds0), 
     points_distances(Ps, Ds0). 

points_distances/2 macht eine Liste von Entfernungen zwischen dem Kopf und jeder der Koordinaten im Schwanz einer Liste, rekursiv (so bei der der Abstand zwischen jedem Paar wird im Ergebnis sein).

rest_distances([], _, Back, Back). 
rest_distances([P|Ps], X, [D|Ds], Back) :- 
     d(P, X, D), 
     rest_distances(Ps, X, Ds, Back). 

Dies berechnet einfach die Abstände zwischen einer Liste von Koordinaten und einer Koordinate. Das Ergebnis ist eine Differenzliste.

diese benutzen:

?- points_distances([[1,1],[1,2],[6,3],[8,2]], D). 
D = [1.0, 5.385164807134504, 7.0710678118654755, 5.0990195135927845, 7.0, 2.23606797749979]. 

?- points_distances([[1,2,3],[2,3,4],[1,7,3],[1,6,3]], D). 
D = [1.7320508075688772, 5.0, 4.0, 4.242640687119285, 3.3166247903554, 1.0]. 

Wenn Sie wollen, Sie „Speicher“ könnten das Koordinatenpaar in einem Abstand voneinander sind. Ändern Sie beispielsweise den Kopf der zweiten Klausel rest_distances/4 aus:

rest_distances([P|Ps], X, [D|Ds], Back) 

zu:

rest_distances([P|Ps], X, [D-pq(X,P)|Ds], Back) 

Jetzt, nachdem das Programm neu zu laden, können Sie das Ergebnis der points_distances/2 und nimmt das erste Element sortieren in es, genau wie in der anderen Antwort:

?- points_distances([[1,2,3],[2,3,4],[1,7,3],[1,6,3]] , D), 
    keysort(D, [Min_dist-pq(P,Q)|_]). 
D = [1.7320508075688772-pq([1, 2, 3], [2, 3, 4]), 
    5.0-pq([1, 2, 3], [1, 7, 3]), 
    4.0-pq([1, 2, 3], [1, 6, 3]), 
    4.242640687119285-pq([2, 3, 4], [1, 7, 3]), 
    3.3166247903554-pq([2, 3|...], [1, 6|...]), 
    1.0-pq([1|...], [1|...])], 
Min_dist = 1.0, 
P = [1, 7, 3], 
Q = [1, 6, 3].