Das Abgehen einer ungeordneten Liste
lima-city → Forum → Programmiersprachen → Java
beispiel
code
eigentliches ziel
element
feld
graph
import
kante
knoten
koordinate
list
liste
null
pfad
point
punkt
start
system
url
ursprung
-
Für alle, die gerne etwas knoblen, habe ich folgendes Problem:
Ich habe eine Liste mit mehreren Elementen. Jedes Element hat eine x und eine y Variable. Folglich beschreibt ein Element eine Koordinate. Es gibt aber nur ganze Zahlen als x und y Werte. Jetzt sollen die Elemente so gelöscht werden, dass vom Punkt 0|0 aus alle Koordinaten abgegangen und in einer anderen Liste gespeichert werden. Dabei muss die Koordinate, auf die als nächstes gegangen werden soll (egal, ob sie schon einmal benutzt wurde oder nicht) die aktuelle Koordinate als direkten Nachbar haben.
Das Thema heißt "ungeordnete Liste", weil die Liste mit den Koordinaten ursprünglich ungeordnet ist. Sie kann natürlich auch während dem Vorgang geordnet werden, das ist egal. Auch wenn ihr einen anderen Aufbau vorschlagt, um Punkte so abzugehen, ist das in Ordnung.
Ich freue mich über Tipps und Hilfestellungen.
PS: Ihr müsst kein Java können, ich erwarte keinen Code.
Beitrag zuletzt geändert: 20.2.2010 21:42:27 von toolz -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Ich weiß nicht genau, was du willst. Also, was ist dein eigentliches Ziel?
-
nikic schrieb:
Ich weiß nicht genau, was du willst. Also, was ist dein eigentliches Ziel?
Dito. Was toolz hier beschreibt ist ein Mischmasch zwischen Array( zweidimensional x und y als Ordnungskriterium ) und Liste ( komplette Koordinate und unabhängig/ungeordnet ) und es ist fraglich, ob es überhaupt umsetzbar ist.
Wie soll man das geordnet abgehen, wenn es ungeordnet ist?
Da sind mir zuviel scheinbare Widersprüche da. Vllt könntest du ja nen Beispiel geben. -
Klar. Ein Beispiel:
Ursprung = 0|0
K1 = 1|1
K2 = 3|4
K3 = 2|1
K4 = 0|1
K5 = 0|-1
Jetzt müssen die Koordinaten eins nach dem Anderen abgegangen werden. Dabei ist egal, in welcher Reiheinfolge das gemacht wird. Einzige Vorraussetzung: Der nächste Punkt muss neben dem aktuellen liegen.
Eine Lösung wäre:
Ursprung, K5, Ursprung, K4, K1, K3
K2 kann nicht erreicht werden. -
Und jetzt soll ein Algorithmus sozusagen den Weg finden, der am kürzesten ist und, wenn er nicht alle schafft, die fehlenden Koordinaten ausgeben oder wie?
Bzw, hast du ja gesagt, dass der Algorythmus zum löschen da ist, aber wie soll er da zweimal über einen Punkt gehen können, wenn er beim zweiten Mal ja nichtmehr da ist?
Dabei fällt mir was ein. Das klingt ziemlich nach nem Automatenproblem und müsste mit Kara simuliert werden können. Dabei sind Felder mit dem Kleeblatt Koordinaten aus der Liste und Kara kann ja nur von Feld zu Feld gehn. vieleicht hilft das weiter.
Wenn du Kara nicht kennst:
http://de.wikipedia.org/wiki/Kara_(Programmierumgebung)
Beitrag zuletzt geändert: 21.2.2010 12:58:26 von reimann -
Hi,
deine Frage motiviert mich zur Erinnerung an scheinbar längst vergessene Zeiten ;).
Die Liste kann man sich als Graph vorstellen, der aus Knoten und Kanten besteht. Die Knoten sind durch ihre Koordinaten bestimmt, die Kanten existieren nur zwischen benachbarten Knoten (so wie du benachbart definiert hast).
Alle Knoten werden mit einem Tiefendurchlauf druchlaufen, wenn der Graph zusammenhängend ist. Sofern nicht, müssen mehrere Durchläufe gestartet werden. Hier mal etwas Code zu deinem Beispiel:
Dabei werden Knoten mehrfach durchlaufen und der Durchlauf endet am Startknoten.package liste; import java.awt.Point; import java.util.ArrayList; public class Tiefendurchlauf { Point P0 = new Point(0, 0); Point P1 = new Point(1, 1); Point P2 = new Point(3, 4); Point P3 = new Point(2, 1); Point P4 = new Point(0, 1); Point P5 = new Point(0, -1); ArrayList<Node> list = new ArrayList<Node>(); boolean[][] edge; public Tiefendurchlauf() { list.add(new Node(P0)); list.add(new Node(P1)); list.add(new Node(P2)); list.add(new Node(P3)); list.add(new Node(P4)); list.add(new Node(P5)); for (int i = 0; i < list.size() - 1; i++) for (int j = i + 1; j < list.size(); j++) if (sindNachbarn(list.get(i), list.get(j))) { list.get(i).neighbour.add(list.get(j)); list.get(j).neighbour.add(list.get(i)); } for (int i = 0; i < list.size(); i++) { if (list.get(i).visited == 0) { runTree(list.get(i)); System.out.println("****************************"); } } } public static void main(String[] args) { new Tiefendurchlauf(); } public boolean sindNachbarn(Node n1, Node n2) { if ((n1.point.x == n2.point.x || n1.point.y == n2.point.y) && (Math.abs(n1.point.x - n2.point.x) == 1 || Math .abs(n1.point.y - n2.point.y) == 1)) return true; else return false; } public void runTree(Node n) { boolean end = true; System.out.println(n.point); if (n.visited == 0) { n.visited++; for (Node v : n.neighbour) { if (v.visited == 0) { end = false; runTree(v); } } } n.visited = 2; if (!end) System.out.println("+" + n.point); } private class Node { public Point point; public int visited; ArrayList<Node> neighbour; public Node(Point p) { visited = 0; point = p; neighbour = new ArrayList<Node>(); } } }
Eine Variante ist die folgende. Hier wird der längste mögliche Pfad gesucht, wobei die Knoten jeweils nur ein mal durchlaufen werden.
Ich hoffe du kannst was davon brauchen.package liste; import java.awt.Point; public class FindeAlle { static int maxTiefe; static Point[] pfad = null; public static void main(String[] args) { Point P0 = new Point(0, 0); Point P1 = new Point(1, 1); Point P2 = new Point(3, 4); Point P3 = new Point(2, 1); Point P4 = new Point(0, 1); Point P5 = new Point(0, -1); Point[] Points = { P0, P1, P2, P3, P4, P5 }; maxTiefe = Points.length +1; while (pfad == null){ maxTiefe--; findePfad(Points,0); } if (pfad == null)System.out.print(pfad); else { System.out.println("Pfadlänge: " + maxTiefe); for (int i= 0; i < pfad.length; i++){ System.out.println(pfad[i]); } } } public static void findePfad(Point[] teilPfad, int start) { if (start == maxTiefe) { pfad = teilPfad.clone(); return; } for (int i = start; i < teilPfad.length; i++) { if (start==0 || sindNachbarn(teilPfad[start-1], teilPfad[i])) { Point[] hilfPfad = teilPfad; Point merk = hilfPfad[start]; hilfPfad[start] = hilfPfad[i]; hilfPfad[i] = merk; findePfad(hilfPfad, start + 1); } } } public static boolean sindNachbarn(Point P1, Point P2) { if ((P1.x == P2.x || P1.y == P2.y) && (Math.abs(P1.x - P2.x) == 1 || Math.abs(P1.y - P2.y) == 1)) return true; else return false; } }
Gruß
Manni -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
