Dynamischer Graph Algorithmus kürzester Weg

Question

Ich habe ein Problem, das ich in eine TSP-Art von Problem umwandeln, so dass ich es hier erklären kann, und ich suche nach irgendwelchen vorhandenen Algorithmen, die mir helfen könnten.

1. Es gibt eine Liste von Orten, die ich besuchen muss und ich muss sie alle besuchen.
2. Es gibt einige Orte, die als erste x von n besucht werden müssen (IE, sie müssen die ersten 3 oder die ersten 5 besuchten Orte sein). (wo die Zahl ist beliebig)
3. Es gibt einige andere Orte, die als letztes y von n besucht werden müssen (IE, sie müssen die letzten 3 oder die letzten 5 besuchten Orte sein).
4. Die Orte können kategorisiert werden (einige haben vielleicht keine Kategorie), für diejenigen in einer Kategorie müssen sie so weit voneinander entfernt sein (dh wenn 2 Orte als grün kategorisiert werden, dann würde ich gerne besuchen, wie viele andere Kategorie Orte wie möglich zwischen diesen grünen kategorisierte Orte)

Hier ist ein Beispiel Liste:

A: Kategorie grün: letzte 3

B: Kategorie none: Bestellung keine

C: Kategorie pink: erste 3

D: Kategorie none: Bestellung keine

E: Kategorie none: letzte 3

F: Kategorie grün: Bestellung keine

G: Kategorie pink: erster 3

Die Reihenfolge ich mit kommen möchte:

g (rosa, first3) -> F (g reen, keine) -> C (pink, first3) -> D (keine, keine) -> B (keine, keine) -> E (keine, letzte3) -> A (grün, letzte3)

Erklärung : G kam zuerst, um es so weit wie möglich von C entfernt zu halten. F kam als nächstes, um es so weit wie möglich von A fernzuhalten. C kam als nächstes in der ersten 3. C und G könnte ausgetauscht werden DB könnte überall platziert werden E kam als nächstes musste es zuletzt 3 A kam zuletzt, da es letzte 3 sein musste und durch Platzierung Es war am Ende, es war so weit wie möglich von F.

Meine Idee ist es, jede Kante Kosten zu bewerten und die Kante Kosten würden dynamisch berechnet werden. Also, wenn Sie versuchten, A und dann F zu besuchen, hätte es einen hohen Preis, im Gegensatz zu A und dann an einem anderen Ort und dann F (wo die Anzahl der Plätze dazwischen wäre ein Teil der Kosten). Außerdem würde ich einen Start- und Endplatz einführen, und wenn ich also einige Orte als erstes x besuchen müsste, wäre ich in der Lage, einen niedrigen Preis zu geben, wenn der Start innerhalb von N Orten dieses Ortes wäre. Gleiches für das Ende.

Ich frage mich, ob es einen Graphalgorithmus gibt, der solche dynamischen Gewichte/Kosten berücksichtigen und den kürzesten Weg vom Anfang bis zum Ende bestimmen kann?

Hinweis: In einigen Fällen ist ein bester Fall möglicherweise nicht verfügbar, und das wäre in Ordnung, solange ich zeigen kann, dass die Kosten hoch sind, weil es nicht genügend Kategorietrennung gab (zB: alle Orte waren in der gleichen Kategorie)).

Brute-Force-Algorithmus Idee I hatte: eine Liste der Orte gegeben, mit allen Kombinationen von Ort Ordnung kommen und die Kosten zwischen den einzelnen berechnen und dann die günstigste wählen. (aber das würde bedeuten, n zu bewerten! wo für 8 wäre das 362880 Bestellungen, die ich auswerten müsste! warum 8, denn das ist, was ich glaube, wird die durchschnittliche Anzahl von Orten zu bewerten sein)

Aber ist da ein Algorithmus, den ich verwenden könnte, um es zu bestimmen, ohne alle Ordnungen zu prüfen.

Answer 1

Eines könnte man tun:

• Auftrag die Orte wie folgt: zuerst 1, ... erste n, ungeordnete, last n, ... zuletzt 1.
• Gehen Sie durch die Liste und getrennte elemnts mit der gleichen Farbe, wo möglich, ohne die vorherige Bestellung
• Berechnen Sie die Kosten dieser Liste zu verletzen und speichern Sie es als die gegenwärtig beste
• Verwenden Sie diese Liste um die Reihenfolge zu bestimmen, in dem Sie Permutationen bewerten
• Whi Sie bauen Permutationen, verfolgen Sie die Kosten
• Abbruch der Erstellung der aktuellen Permutation, wenn die Kosten übersteigt die aktuelle beste (einschließlich der theoretischen Mindestkosten für die verbleibenden Plätze, wenn es welche gibt)
• Auch abbrechen, wenn Sie haben theoretisch mögliche Bestnote.