Graph in disjunkte Gruppen einteilen (TSP)

Neue Frage »

nwo Auf diesen Beitrag antworten »
Graph in disjunkte Gruppen einteilen (TSP)
Ich suche eine Methode einen Graphen in mehrere disjunkte Gruppen einzuteilen für eine Art erweitertes Problem des Handelsreisenden.

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.
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.
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »