Дано количество упорядоченных узлов в двунаправленном графе с известной только положительной стоимостью для каждого ребра.
Мне нужно найти кратчайший путь через заданные узлы в определенном порядке, который задан, при этом никогда не использовать какое-либо ребро дважды.
Так что, в отличие от задач коммивояжера, я знаю порядок обхода.
Однако последнее требование здесь является ключевым. Из-за невозможности использовать какое-либо ребро дважды, локально оптимальный путь между узлами 1 и 2 может создать субоптимальный путь между 2 и 3 и т. Д.
Сейчас я использую A-Star по очереди для построения полного пути, но ясно, что это не оптимально.
В псевдокоде:
for (int i = 0; i < numberOfNodes - 1; i++)
{
List<Tile> newPath = importantNodes[i].FindShortestPath(graph, importantNodes[i+1]);
graph.RemoveEdges(newPath);
totalPath.Add(newPath);
}
Итак, есть ли способ найти глобальный оптимум по всем заданным узлам, просматривая все их одновременно, чтобы найти оптимальный путь?