Kürzesten Pfad im Graphen finden
-
Hallo,
also ich suche einen Algorithmus, der den kürzesten Pfad (in einem gewichteten Graphen) findet, der eine Menge an Punkten verbindet. Dabei darf es keine Abzweigungen geben und ein Knoten darf nicht zweimal besucht werden.
-
Also einen Hamiltonpfad? Tja, das ist schwierig. Das Problem ist NP-schwer. Wenn Du in einem beliebigen Graphen bist ist es sogar schwer zu approximieren (also ne Lösung zu finden, die höchstens Faktor k länger ist als das Optimum).
Handelt es sich um Punkte in der Ebene und das Gewicht ist die Distanz der Punkte, oder gilt wenigstens die Dreiecksungleichung? Dann kriegt man relativ leicht ne Faktor-2-Approximation oder sogar besseres hin.
-
Naja, Hamiltonpfad nicht unbedingt. Das ist ja nur die Frage OB eine Verbindung zwischen allen Knoten im Graphen besteht, oder?
Bei mir ist die Frage, welches die kürzeste Verbindung ist (also mehr so Richtung "Problem des Handlungsreisenden...).
Ich brauch den Algorithmus für das Erstellen eines Zeitplans.
Mein Problem:
Also, sagen wir, in einer Woche ist Elternsprechtag. Die Eltern melden sich über die Seite der Schule an, sagen welche Lehrer sie besuchen wollen und wie lange sie mit ihm reden wollen (5,10,15 Minuten).Mein Programm soll sie dann so einteilen, dass sie möglichst schnell alle Lehrer besucht haben und möglichst kurze Wartezeiten dazwischen haben.
So, meine Ideen bisher:
*Also, ich erstelle die Zeitpläne für alle Eltern nacheinander, das führt zwar nicht zur optimalsten Lösung, macht aber das Problem etwas weniger komplex ;). Anfangen tu ich mit den Eltern, die die meisten Lehrer besuchen wollen.
*So, jetzt muss ich für ein Elter (richtig so ?) den optimalen Weg finden. Also erstell ich einen gerichteten Graphen, mit den Lehrern als Knoten und den Wartezeiten als Gewicht der Kanten.
So, und jetzt muss ich den kürzesten Pfad ohne Abzweigungen finden.
-
Du hast recht. Nicht Hamiltonpfad, sondern TSP. Meine Aussagen oben gelten auch nur für's TSP, ich hab den Namen verwechselt. Einen Hamiltonpfad kann man nicht approximieren, den gibt's oder eben nicht.
Das Problem ist ziemlich sicher nicht schnell optimal lösbar. Die Graphen-Modellierung halte ich allerdings nicht für sooo sinnvoll. Imho lässt sich das besser als eine Art Scheduling-Problem modellieren. Allerdings ein recht kniffliges.