Graph Suche Problem mit Route Einschränkungen

Question

Ich möchte die profitabelste Route berechnen und ich denke, das ist eine Art von Reisen Verkäufer Problem.
Ich habe eine Reihe von Knoten, die ich besuchen kann und eine Funktion zur Berechnung der Kosten für die Reise zwischen den Knoten und Punkten zum Erreichen der Knoten. Ziel ist es, eine festgelegte bekannte Punktzahl zu erreichen und gleichzeitig die Kosten zu minimieren.

Diese Kosten und Belohnungen sind nicht festgelegt und hängen von den zuvor besuchten Knoten ab.
Der Startknoten ist fixiert.

Es gibt einige Einschränkungen, wie Knoten besucht werden können. Einige Beispiele sind vereinfachte:

• Node B kann erst nach einer
• besucht werden, nachdem der Knoten C wurde besucht, D oder E besichtigt werden können. Besuch mindestens eines ist erforderlich, beide Besuche sind erlaubt.
• Z kann erst nach mindestens fünf anderen Knoten besucht werden haben
• Sobald 50 Knoten besucht wurden besucht, die Knoten AM nicht mehr Bonuspunkte
• Bestimmte Knoten können (und wahrscheinlich auch müssen) mehrmals besucht werden

Derzeit kann ich denke nur zwei Möglichkeiten, dieses Problem zu lösen:
a) Genetische Algorithmen, mit der Fitness-Funktion, um die Kosten/Nutzen der erzeugten Route
b) Dijkstra Suche durch den Graphen zu berechnen, da die Startknoten ist behoben, obwohl die Lar Die Anzahl der Knoten wird dies wahrscheinlich nicht machbar machen.

Gibt es noch andere Möglichkeiten, die beste Route durch das Diagramm zu bestimmen? Es muss nicht perfekt sein, ein angenäherter Pfad ist vollkommen in Ordnung, solange es fehlerfrei ist.
Wären TSP-Löser hier eine Option?

Answer 1

Mit dieser viel seltsamen Variation und Pfadabhängigkeit, was Sie tatsächlich suchen, ist nicht der Graph selbst, sondern der Raum der Pfade von der Wurzel, die ein Baum ist. Wenn das Problem so allgemein ist, wie Sie sagen, werden Sie nicht besser sein können, als direkt den "Baumpfad" zu durchsuchen und den besten Wert und den entsprechenden Pfad zu speichern. Wenn Sie es in irgendeine Weise transformieren können, so dass es keine solche Pfadabhängigkeit gibt, sollten Sie dies wahrscheinlich tun.

Wenn dies nicht möglich ist, gibt es zwei grundlegende Optionen: breath-first, die die Pfade in der Reihenfolge der Länge zurückgibt, aber auf Kosten hoher Speicherauslastung, da viele temporäre Pfade gespeichert werden müssen. Die Tiefensuche muss nur einen einzelnen Pfad speichern (der vollständig als eine Reihe von rekursiven Aufrufen ausgeführt werden kann), hat jedoch keinen natürlichen Haltepunkt und kann nicht garantiert enden, wenn keine obere Grenze für die Pfadgröße vorhanden ist.

Wenn Sie Glück haben, dass die Kosten mit jedem weiteren Schritt monoton steigen, können Sie stattdessen nach Kosten sortieren. Der erste, der gut genug ist, ist derjenige, den Sie dann wollen. Die Suche nach der Breite wird manchmal implementiert, indem die zu untersuchenden Pfade in eine Warteschlange gestellt werden. Ändern Sie diese anhand der Kosten in eine Prioritätswarteschlange, und Sie haben jetzt eine "Suche nach Kosten zuerst", formal bekannt als Uniform-cost search.

Wenn die Kostenfunktion kann durch Hinzufügen auf dem Pfad verringern, kann A * Suche geändert werden, um die Suche zu tun, aber Sie haben nicht mehr die Garantie, dass Sie früh aufhören können.