Graph in disjunkte Gruppen einteilen (TSP) |
18.01.2004, 18:15 | nwo | Auf diesen Beitrag antworten » |
Graph in disjunkte Gruppen einteilen (TSP) Dazu habe ich das Problem beim einteilen des Graphen in disjunkte Gruppen. Die Gruppen sollen so gewählet werden, dass wenn man bei jeder Gruppe den hamilton-zyklus bildet und die Längen der Zyklen addiert, diese Länge minimal ist. Auf Grund der komplexen Struktur ist keinesfalls eine optimale Methode nötig, aber ein möglicht gutes Verfahren. Meine Grundidee ist es, wenn die "Ränder" der Gruppen möglichst weit entfernt sind, dass dann die Hamilton-zyklen auch möglicht optimal werden. Wie finde ich aber solche Gruppen? Es geht hier auch nicht um den Allgemeinen Fall des Handelsreisendenproblems, man kann sich die Räumliche Struktur des euklidischen Raumes zunutze machen. |
||
19.01.2004, 02:40 | epikur | Auf diesen Beitrag antworten » |
Was meinst du denn mit disjunkten Gruppen ? Zusammenhangskomponenten ? Eine Zusammenhangskomponente eine Graphen G ist eine Menge von Knoten V', so das es in G von jedem Knoten v in V' zu jedem anderen Knoten u in V' einen Weg gibt. Zusammenhangskomponenten eines Graphen sind mit sehr geringem Rechenaufwand exakt bestimmbar, zB mittels einer Breiten- (BFS) oder Tiefensuche (DFS). Zu diesen beiden Algortihmen existieren etwa 1234567890 Demonstrationsapplets im Netz. Google hilft. |
||
19.01.2004, 19:03 | nwo | Auf diesen Beitrag antworten » |
Das Problem ist, das in meinem Fall jeder Knoten mit jedem verbunden ist, nur das manche Knoten weit von einander Entfernt sind. Daher bringt mir das leider nichts. Von allen Knoten muss ich die Knoten, die nah beisammen liegen gruppieren. Vielleicht muss ich auch auf die Graphenteoretische Betrachtung verzichten und mit einer Ebene arbeiten in der Puntke sind und dann diese Punkte gruppieren. Die drei Gruppen sollten einfach möglicht nah zusammen liegen, da jede Gruppe später eine Instanz des Handelsreisenden Problems bilden soll. Die gesamtlänge soll dadurch minimiert werden. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|