Algorithmus zum Anordnen von kartesischen Punkten

Question

Ich habe einige kartesische Punkte der Form: (x, y)
wo x und y beide nicht negative ganze Zahlen sind.

Für z.B.
(0,0), (1,1), (0,1)

Ich brauche einen Algorithmus die oben genannten Punkte
so anzuordnen, die auf andere
Änderungen entweder x von einem Punkt gehen oder y um 1.

mit anderen Worten, würde Ich mag
diagonale Bewegung vermeiden. Die oben genannten Punkte werden wie folgt angeordnet:
(0,0), (0,1), (1,1).

Ähnlich für (0,0), (1,1), (0,2)
ist eine solche Anordnung nicht möglich.

Ich bin nicht sicher, was es nennen
aber ich würde es Manhattan nennen bestellen.

Kann jemand helfen?

Answer 1

Wenn Sie für eine Anordnung suchen, die Scheitelpunkte nicht wiederholen:

Was scheinen Sie gesucht werden soll, ein Hamilton-Pfad in einem Grid Graph.

Dies ist bekannt für die allgemeine Grid Graphen NP-vollständig, Hamilton Paths in Grid Graphs sehen.

So können Sie wahrscheinlich versuchen Sie Ihr Glück mit einem ungefähren/heuristisch/etc Algorithmen für die Hamilton-Pfad bekannt/euklidisches Salesman Problem Reisen.

---

Wenn Sie für eine Anordnung suchen, wiederholen kann, aber die minimal mögliche Anzahl von Punkten in der Anordnung wollen:

Dies ist wieder NP-vollständig. Das obige Problem kann darauf reduziert werden. Dies liegt daran, dass der minimal mögliche Weg genau dann n Knoten hat, wenn der Graph einen Hamilton-Pfad hat.

---

Wenn Sie nur für einige Anordnung von Punkten suchen,

Dann alles, was Sie tun müssen, ist zu überprüfen, ob der Graph verbunden ist. Wenn es nicht verbunden ist, kann es keine solche Anordnung geben.

Sie können eine Tiefensuche tun, um das herauszufinden. Die Tiefensuche gibt Ihnen auch eine solche Anordnung, falls der Graph verbunden ist.

Wenn Sie etwas näher an einem optimalen wollen (aber in recht schnell Zeit), können Sie wahrscheinlich Approximationsalgorithmen für das euklidische Reiseproblem verwenden.

Answer 2

Dies könnte vereinfacht werden, indem der Abstand zwischen jedem aufeinanderfolgenden Punkt minimiert wird. Von (0,0) zu (0,1) zu gehen ist einfach 1 Einheit, aber von (0,0) zu (1,1) zu gehen ist tatsächlich sqrt (2). Wenn Sie also die Punkte zu einem Diagramm zusammenfassen und dann eine einfache Mindest-Gesamtdistanz (reisender Verkäufer) durchführen, sollten Sie sie richtig anordnen.

Edit: Wenn Sie nie einen Schritt wünschen, der größer als 1 wäre, fügen Sie einfach keine Kanten größer als 1 hinzu. Die Traversierung funktioniert immer noch korrekt und ignoriert alle Pfade, die eine Bewegung erfordern> 1.

Edit 2: Um weiter zu verdeutlichen, können Sie einen beliebigen Kantenauswahlalgorithmus verwenden. Wenn Sie sich mit 2 Leerzeichen bewegen, solange der Platz nicht diagonal ist, können Sie eine Kante zwischen (0,2) und (0,4) einfügen. Der Algorithmus für minimale Entfernung funktioniert weiterhin. Platzieren Sie einfach die Kanten auf intelligente Weise, und Sie können eine beliebige Anzahl von Auswahlkriterien verwenden, um das Ergebnis zu bestimmen.

Answer 3

Eine Möglichkeit besteht darin, zwei sortierte Listen der Koordinaten zu erstellen. Einer sortiert nach x und einer nach y sortiert. Suchen Sie dann rekursiv nach einer Lösung.

Code kommt (nicht sicher, welche Sprache noch, vielleicht Pseudocode?) ... Bearbeiten - vergiss es, denn meine Antwort ist nicht so gut wie einige der anderen sowieso.

Answer 4

Sie können ein Diagramm erstellen, bei dem die Scheitelpunkte Ihre Punkte sind und die Kanten die gültigen Schritte sind.

Was Sie dann suchen, ist ein Hamiltonian path für dieses Diagramm. Dies ist in seiner allgemeinen Form ein NP-vollständiges Problem, was bedeutet, dass es keine bekannte effiziente Lösung gibt (d. H. Eine, die gut mit der Anzahl von Punkten skaliert). Wikipedia beschreibt ein randomized algorithm, die „schnell auf den meisten Graphen“ und könnte von Nutzen sein:

Starten von einem zufälligen Scheitel, und weiter, wenn es ein Nachbar ist nicht besucht.Wenn es keine nicht mehr besuchten Nachbarn mehr gibt und der gebildete Pfad kein Hamiltonoperator ist, wählen Sie einen Nachbarn gleichmäßig zufällig aus und rotieren Sie mit diesem Nachbarn als Drehpunkt. (Das heißt, fügen Sie diesem Nachbarn eine Kante hinzu und entfernen Sie eine der vorhandenen Kanten von diesem Nachbarn, um keine Schleife zu bilden.) Fahren Sie dann mit dem Algorithmus am neuen Ende des Pfads fort.

Eine effizientere Lösung könnte jedoch für diese spezielle Situation existieren.

Answer 5

Betrachten Sie es als Graph, wobei jeder Knoten als höchstens vier Kanten. Dann tun Tiefe/Breite-zuerst-Suche.

Answer 6

Wie wärs mit einer Brute-Force-rekursive REXX Routine ... alle möglichen Pfade Versuchen und aus arbeiten diejenigen, die gedruckt werden.

/* rexx */ 
point. = 0 /* Boolean for each existing point */ 
say 'Enter origin x and y coordinate:' 
pull xo yo 
point.xo.yo = 1 /* Point exists... */ 
say 'Enter destination x and y coordinate:' 
pull xd yd 
point.xd.yd = 1 /* Point exists... */ 
say 'Enter remaining x and y coordinates, one pair per line:' 
do forever 
    pull x y 
    if x = '' then leave 
    point.x.y = 1 
end 

path = '' 
call findpath xo yo path 
say 'All possible paths have been displayed' 
return 

findpath: procedure expose point. xd yd 
arg x y path 
if \point.x.y then return    /* no such point */ 
newpoint = '(' || x y || ')' 
if pos(newpoint, path) > 0 then return /* abandon on cycle */ 
if x = xd & y = yd then     /* found a path */ 
    say path newpoint 
else do         /* keep searching */ 
    call findpath x+1 y path newpoint 
    call findpath x-1 y path newpoint 
    call findpath x y+1 path newpoint 
    call findpath x y-1 path newpoint 
    end 
return 

Beispielsitzung:

Path.rex 
Enter origin x and y coordinate: 
0 0 
Enter destination x and y coordinate: 
2 2 
Enter remaining x and y coordinates, one pair per line: 
0 1 
1 1 
2 1 
1 2 

(0 0) (0 1) (1 1) (2 1) (2 2) 
(0 0) (0 1) (1 1) (1 2) (2 2) 
All possible paths have been displayed 

Diese Mitteilung nicht auf irgendetwas versuchen groß obwohl - eine sehr lange Zeit in Anspruch nehmen könnte! Aber dann hat die Frage nie etwas über eine optimale Lösung gesagt.