AndiAbseits
Grünschnabel
Dabei seit: 04.07.2017
Beiträge: 1
 |
|
| Graphentheorie / Caching in Pfaden |
     |
Meine Frage:
Folgendes Problem.
Es geht darum einen vollständigen gewichteten bidirektionalen Graphen in einen endlichen Baum umzuwandeln, in dem jeder Knoten nur einmal besucht wird.
sprich aus einem Graphen G=(E,V) mit |V|=n wird für n=3:
1-2-3, 1-3-2, 2-3-1, 2-1-3, 3-1-2, 3-2-1.
Also im Grunde einfach alle Permutationen. ABER nun geht es um die Sortierung nach Länge der Pfade und diese sind nicht immer gleich, weil der Graph bidirektional ist und unterschiedlich gewichtet ist.
Also length(1-2-3) = length(3-1-2) gilt im allgemeinen nicht!
Soweit so gut.
Man erkennt, dass das Problem mit dem TSP verwandt ist, nur das "Hin- und Rückweg" unterschiedlich lang sein können. Also in jedem Fall auch NP-vollständig.
Dennoch möchte ich es lösen, was ja für ca. n=12 kein Problem ist ((n-1)! lässt sich ja noch lösen! Das sind 39916800 Pfade).
Allerdings ist meine Frage, ob man bei der Programmierung dessen ein bisschen optimieren kann durch geschicktes Caching. Man betrachte als Beispiel für n=11 die folgenden Pfade:
1-2-5-6-7-8-9-10-11-3-4 und 1-5-6-7-8-11-3-4-2-9-10
Es fällt auf, dass es unsinnig wäre, die Längen 5-6-7-8 und 11-3-4 mehrfach zu berechnen, da sie sich ja wiederholen. Allgemein wiederholen sich sehr sehr viele Abschnitte und man kann sich glaube ich massig Summenbildungen sparen, was doch bei 39916800 Pfaden lohnen kann, oder?
Nur empfinde ich das Problem als recht kompliziert, in Pfaden Teilmengen anderer Pfade zu suchen und einzusetzen und frage mich ob das nicht selbst aufwendiger ist, als die Ersparnis...
Hoffe, ihr versteht was ich meine. Würde mich über Tipps oder noch besser Pseudcode dazu freuen! Danke!
Meine Ideen:
Bisherige Ideen:
Induktiv die Pfade mit bereits existierenden Bausteinen zusammensetzen.
Sprich:
1) 2-Block-Liste: (1-2, 2-1, 1-3, 3-1, 2-3, 3-2, 1-4,...)
2) 3-Block-Liste: (verwende 2-Block-Liste und pack einen nicht verwendeten Knoten davor oder dahinter..
3) 4-Block-Liste: Verwende...
Allgemein: Verwende für n=12 Pfade, die 11-Blockliste, die wiederum die... usw.
Aber wie genau implementiere ich das und spart das wirklich etwas? kann das jemand mathematisch darlegen?
|
|
