Заголовок полный, но, проще говоря, у меня есть большой, неориентированный, неполный граф, и мне нужно посетить некоторое подмножество вершин в (приблизительно) кратчайшее возможное время. Обратите внимание, что это не TSP, поскольку мне не нужно посещать все вершины.
Наивный подход состоял бы в том, чтобы просто перебрать решение путем грубой силы, пробуя каждую возможную прогулку, которая включает в себя требуемые вершины, используя, например, A *, для вычисления обходов между требуемыми вершинами. Однако это O(n!), где n - количество требуемых вершин. Это невозможно для меня, как n > 40 в моем среднем случае и n ≈ 80 в моем худшем случае.
Существует ли более эффективный алгоритм для этого, возможно, такой, который приближает решение?
Этот вопрос похож на вопрос здесь , но отличается тем, что мой график больше, чем в связанном вопросе. Есть несколько других подобных вопросов, но ни один из тех, что я видел, точно не решает мою конкретную проблему c.