сведение к минимуму стоимости проезда между городами

Question

Привет, У меня есть проблема оптимизации, когда у меня есть n дней, чтобы путешествовать в k городов, и я должен запланировать свое путешествие, чтобы моя общая стоимость поездки была сведена к минимуму.

Стоимость путешествия между любыми 2 городами u и v зависит от дня, когда я решаю путешествовать (так что стоимость проезда между u и v является функцией f (u, v, n), где n является день, когда я путешествую), и я могу путешествовать только один раз в день. Я также могу остановиться в том же городе.

Есть ли способ решить эту проблему с помощью алгоритма кратчайшего пути?

Answer 1

Это проблема NP-Complete (так как она сводится к гамильтоновскому пути). Единственное существенное различие между этой и стандартной проблемой Traveling Salesman заключается в том, что весовые коэффициенты динамические. Это означает, что вы сталкиваетесь с однократной предварительной обработкой стоимости O (V V E!) И что весь цикл может быть разрешен в худшем случае O (V^3).

Я смог найти некоторые детали аналогичной проблемы в этом paper, опубликованном в IEEE, в котором описывается проблема Intelligent Transportation-TSP.