Wegfindung in Graphen

piXelshooter

Hallo.
Ich habe einen Graphen G{N;E} mit knoten N und verbindungen E (zu denen eine Gewichtsfunktion g zur Verfügung steht). Außerdem eine Menge an Aufträgen T, die zu bearbeiten sind. Ein Auftrag besteht aus einen Paar zweier Knoten. Beispiel: T={{1;3},{2;3}}. Diese Aufträge bedeuten, dass irgendjemand von Knoten 1 nach 3 und irgendjemand von 2 nach 3 fahren soll. Dazu verkehren Fahrzeuge (F) in dem Netz. Es ist egal, wer welchen Auftrag ausführt. einziges Ziel: Alle Aufträge sollen so schnell wie möglich abgearbeitet werden. Erschwerend kommt hinzu: Auf einem Knoten können sich nicht gleichzeitig zwei Fahrzeuge befinden. Daher hat jeder Knoten einen Kalender K, eine Liste von Zeiten, zu denen er Belegt ist. Bsp: K[1]={{1;4},{5;7}} würde bedeuten, Knoten 1 sei von Zeitpunkt 1 bis 4 und von 5 bis 7 belegt. In dieser Zeit kann dort niemand anders sich mehr befinden.

Mein Problem ist es jetzt, zu einem gegebenen F, T und F die optimale Strategie für die bearbeitung von T's elementen zu finden. Damit hab ich im Moment so meine Probleme, darum frage ich hier um hilfe

in Anlehnung an den A* Algorithmus habe ich mich bisher an folgender herangehensweise versucht:

erzeuge eine Menge P mit allen aktuellen Standpunkten, die zu Beginn natürlich nur die aktuellen Standpunkte der Fahrzeuge enthält.
Solange nicht genügend Aufträge erledigt {
    für jeden aktuellen weg
    {
        stelle für F[1] eine Menge Q1 möglicher folgender Wege her.
        für jeden Q1 als Q1[n]: {
            stelle für F[2] eine Menge Q2 möglicher folgender Wege her, die von Q[n] nicht ausgeschlossen ist.
        }
        ...
        Dabei entsteht eine Menge möglicher Wege (deren Umfang sehr schnell steigt).
    }
    Wähle hieraus die minimale verlängerung des originalen weges.
}

vir allem die größe der Qs macht mir angst: die innerste schleife braucht in einem vollständigen graphen des grades r für n fahrzeuge O=rⁿ. und das dann noch mal mal die anzahl der aktuellen standpunkte...

die klausel bei F[n]: die von Q[n-1][...] nicht ausgeschlossen ist: Das lässt auch noch auf Speicherbelastung schielen...

also gut finde ich des system nicht! Ich wäre deshalb offen für ideen.

Link: http://aintelligence.ai.funpic.de/forum/viewtopic.php?f=4&t=32

darthdespotism

So schlecht ist das doch gar nicht. Nur von der Anzahl der Fahrzeuge exponentiell abhängig und da werden es wohl kaum viele werden oder?

Was muss der Algorithmus den liefern? Vollständigkeit? Optimalität?

piXelshooter

Naja. Es soll einigermaßen universell sein, von daher rechne ich mit 10-20, wo es noch wenige sekunden brauchen sollte. Ob das überhaupt möglich ist... kA

die idee dahinter war es, die optimale lösung zu finden, in dem sinne, dass optimal die kürzeste gesamtzeit bis zur erfüllung aller aufträge ist.