Ich wende mich heute mit einem Problem an euch, zu lösen dessen ich nicht im Stande bin. Es handelt sich um ein einfaches 'kürzeste Wege Problem'; dachte ich. Es geht um einen ungerichteten Graphen mit 17 Knoten und 32 ungewichteten Kanten. Dieser repräsentiert klassisch Wege und Kreuzungen (bzw. Orte). Es gibt nun jeweils einen ausgewiesenen Start- und Endknoten (wobei dies auch Später ein Knoten sein kann; Stichwort - Rundreise)
Mein Ziel ist es nun den kürzesten Weg zwischen Start und Ziel zu finden. Soweit kein Problem, Dijkstra nimmt sich dieser gerne an. Jedoch habe ich eine zusätzliche Bedingung, die mir Kopfzerbrechen bereitet. Ich möchte nämlich auf dem Weg noch an (über) ganz bestimmte Knoten vorbeikommen (besuchen). Das soll heißen, dass ich eine kürzeste Route möchte die noch die Knoten (3,7,10,13) enthält.
Der kürzeste Wege erster Streich:
Mein erster Versuch bestand nun darin, ausgehend vom Startknoten, jeweils zu dem zu gehen der am nächsten gelegen ist. Ich habe also eine Liste (zlist) mit allen Zwischenstopps. Von Start aus berechne ich alle Entfernungen zu den Punkten in zlist, gehen dann zu dem mit dem kürzesten Weg und streiche jenen dann aus der zlist. Was sich zunächst gut anhörte hatte nur mäßigen Erfolg. Die Route sah einigermaßen gut aus, aber in bestimmten Konstellationen war es auch einfach nicht zu gebrauchen; die Route war ein einziges hin und her. Das ist nicht ganz unverständlich, wenn man bedenkt, dass ich für das Problem immer nur ein lokales Minima suche, obschon ein globales Minima gesucht ist - diese beiden koinzidieren leider nicht immer.
Man kann hier leicht sehen, dass der Algorithmus den "Fehler" macht und am Anfang vom Startknoten E1 zu Knoten 7 geht. Aus lokaler Sicht (und für die Art des Algos) ist das natürlich Richtig, nur ist es für meine Zwecke denkbar schlecht. Danach Sucht er sich wieder den nächsten Punkt über 13 und 10 und muss dann wieder zurück zu Punkt 3 um dann abermals zurück zum Zielpunkt E2 zu gehen. "Klüger" wäre es in diesem Fall zum weiter entfernteren Knoten 3 zu gehen ...
Der kürzeste Wege zweiter Streich:
Unzufrieden mit dem Ergebnis habe ich dann versucht das Problem anders anzugehen. Ausgehend von der Schwäche der "lokalen Minima", musste nun was globaleres her. Ich habe also eine Liste (zlist) mit allen Zwischenstopps. Nun berechne ich zu allen Paaren in zlist die kürzesten Wege untereinander - Dijkstra übernehmen Sie. Diese Wege der Paarungen speichere ich mir in einem Dict (pdict) mit der Form pdict[startknoten][zielknoten] = [startknoten, knoten1, knoten2, ... , zielknoten]. Also jeweils die kürzesten Wege zwischen zwei Punkte in zlist (Den Punkten die ich unbedingt besuchen will). Nun Berechne ich mir zu allen Permutationen von zlist (also alle möglichen Wege) wer denn nun der kürzeste ist. Beispielsweise die Permutation [E1, 3, 7, 10, 13, E2]. Hierzu nehme ich einfach pdict[E1][3] und füge die Teilstrecke dem gesamt Weg hinzu, weiter mit pdict[3][7] ... usw und vergleiche dann die Länge der gesamt Wege.
Das funktioniert auch alles wunderbar und das Ergebnis ist fast identisch mit dem was ich mir ersonnen hatte.
Leider hat die Sache einen entscheidenen Haken: " Nun Berechne ich mir zu allen Permutationen von zlist". Leider hat das ganze ein O(n!) für alle Permutationen und da komme ich bei 9 Elementen in zlist schon auf knapp 4 Sekunden, 10 Elemente knapp 40 Sekunden und bei 11 sind es fast schon 10 Minuten.
Kennt jemand vielleicht eine Methode das Problem schneller zu lösen als O(n!)? Habe ich vielleicht Problemen mit meinem jetzigen Code, dass ich so schnell schon an die Grenze stoße - ich meine 9! ist gerade mal 362880 und dafür schon 4 Sekunden? Macht es sinn Code zu Posten oder bewegen wir uns hier in einem "normalen" Ramen? Ich denke das Hauptproblem liegt nicht an unoptimiertem Code denn des aufwendigen Algorithmus'es
Was ich schon versucht habe, ist eine Art Abschätzung wann ich das "Streckenbilden" abbrechen kann. Ich lasse den Algorithmus aus dem "ersten Streich" laufen (der ungemein schneller ist) und habe damit eine obere Schranke. Wenn ich also eine Strecke bilde die schon genauso lang ist breche ich ab. Genause wie ich mir die Momentan kürzeste Strecke merke (auch als obere Schranke) und abbreche wenn diese Überschritten wird. Das alles gibt aber maximal so um die 2% zuwachs an Geschwindigkeit.
Über Denkanregungen in dieser Hinsicht würde ich mich freuen.
hochachtungsvoll Lordnaikon
Was ich sagen wollte war: Intuitiv kam mir das Problem als solches nicht so ungewöhnlich vor; nicht ungewöhnlich genug, als dass es nicht schon tausendfach in Hobbyspieleprogrammierforen gefragt wurde - wie lasse ich die KI möglichst schnell alle Medipacks aufsammeln/ Schalter betätigen ... usw. Danke erstmal für die Hinweise! Jetzt habe ich wenigstens mal so einigermaßen einen Überblick. Witzig, dass meine Projekte sich öfter mal an graphentheoretischen Sachen aufhängen. Ich erinnere mich da noch an eine Diskussion mit, unter anderem, BlackJack an dieser 
... wer hätte das gedacht :K
