Minimierung der Kosten für Reisen zwischen den Städten

Question

Hallo Ich habe ein Optimierungsproblem, wo ich n Tage habe, um in k Städte zu reisen, und ich meine Reise so planen muss, dass meine Gesamtkosten der Reise minimiert werden.

Die Reisekosten zwischen zwei Städten u und v, ist abhängig von dem Tag, an dem ich mich entscheide zu reisen (also Reisekosten zwischen u und v ist eine Funktion f (u, v, n) mit n ist die Tag, wenn ich reise) und ich kann nur einmal am Tag reisen. Ich kann auch wählen, in der gleichen Stadt zu bleiben.

Gibt es eine Möglichkeit, dies durch einen Algorithmus für den kürzesten Weg zu lösen?

Answer 1

Dies ist ein NP-vollständiges Problem (da es vom Hamilton-Pfad reduziert wird). Der einzige große Unterschied zwischen diesem Problem und dem Standardproblem des Traveling Salesman besteht darin, dass die Kantengewichte dynamisch sind. Dies bedeutet, dass Sie eine einmalige Vorverarbeitungskosten von O (V V E!) Komplexität haben und dass der gesamte Zyklus in einer O (V^3) Worst-Case-Zeit gelöst werden kann.

Ich konnte einige Details eines ähnlichen Problems in dieser paper in IEEE veröffentlicht, die das Intelligent Transportation-TSP-Problem beschreibt.