#graph #graph-theory #graph-algorithm #directed-graph #weighted-graph
Вопрос:
У меня есть взвешенный ориентированный график. Я определяю здесь «охватывающий проход» как проход по графу, который посещает каждую вершину по крайней мере один раз, без ограничений на то, какие ребра необходимо пересечь. Я пытаюсь найти самую короткую из таких прогулок, если таковая существует. Вот изображение примера графика, кратчайший путь по которому составляет c->d->>b->>>a, длиной 6
Я пытался изучить гамильтоновы пути, проблему Коммивояжера и тому подобное, но, поскольку в моей задаче мне разрешено посещать вершину несколько раз, я не знаю, смогу ли я ее использовать. Я почти полностью убежден, что проблема NP-сложная, но интересно, есть ли что-нибудь, чтобы поиск не занял столетия для больших графиков.
Комментарии:
1. Это похоже на версию проблемы Коммивояжера .
2. в TSP говорится, что вы можете посетить каждый город ровно один раз, что здесь не является ограничением, но я уверен, что это очень связано с внесением правки, спасибо c: