1

The title is a mouth-full, but put simply, I have a large, undirected, incomplete graph, and I need to visit some subset of vertices in the (approximately) shortest time possible. Note that this isn't TSP, as I don't need to visit all vertices.

The naive approach would be to simply brute-force the solution by trying every possible walk which includes the required vertices, using A*, for example, to calculate the walks between required vertices. However, this is O(n!) where n is the number of required vertices. This is unfeasible for me, as n > 40 in my average case, and n ≈ 80 in my worst case.

Is there a more efficient algorithm for this, perhaps one that approximates the solution?

This question is similar to the question here, but differs in the fact that my graph is larger than the one in the linked question. There are several other similar questions, but none that I've seen exactly solve my specific problem.

Steven
  • 1,709
  • 3
  • 17
  • 27
  • That is a TSP if you build graph of distances between vertices in your subset (using Floyd's algorithm for example), so there's no polynomial exact solution and I think there is no fast enough exact solution for 80 nodes in subset. But you can approximate enough effective https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computing_a_solution – fas Apr 06 '20 at 06:45

1 Answers1

3

If you allow visiting the same nodes several times, find the shortest path between each pair of mandatory vertices. Then you solve the TSP between the mandatory vertices, using the above shortest path costs. If you disallow multiple visits, the problem is much worse.

I am afraid you cannot escape the TSP.