是否有一种有效的算法来查找或近似必须访问图的某些顶点子集的图的最短路径？
Is there an efficient algorithm for finding or approximating the shortest walk of a graph which must visit some subset of vertices of the graph?
标题是mouth-full，但简单地说，我有一个大的、无向的、不完整的图，我需要在（大约）最短的时间内访问一些顶点的子集。请注意，这不是 TSP，因为我不需要访问 all 个顶点。
最简单的方法是 brute-force 通过尝试包括所需顶点的每一种可能的遍历来简单地解决方案，例如，使用 A* 来计算所需顶点之间的遍历。但是，这是 O(n!)，其中 n 是所需顶点的数量。这对我来说是不可行的，因为在我的平均情况下 n > 40，在我最坏的情况下 n ≈ 80。
对此是否有更有效的算法，也许是近似解的算法？
此问题与问题 here 类似，但不同之处在于我的图表比链接问题中的图表大。还有其他几个类似的问题，但我看到的 none 完全解决了我的具体问题。
如果允许多次访问相同的节点，请找到每对强制顶点之间的最短路径。然后使用上述最短路径成本解决强制顶点之间的 TSP。如果你不允许多次访问，问题就更糟了。
恐怕你逃不过TSP
标题是mouth-full，但简单地说，我有一个大的、无向的、不完整的图，我需要在（大约）最短的时间内访问一些顶点的子集。请注意，这不是 TSP，因为我不需要访问 all 个顶点。
最简单的方法是 brute-force 通过尝试包括所需顶点的每一种可能的遍历来简单地解决方案，例如，使用 A* 来计算所需顶点之间的遍历。但是，这是 O(n!)，其中 n 是所需顶点的数量。这对我来说是不可行的，因为在我的平均情况下 n > 40，在我最坏的情况下 n ≈ 80。
对此是否有更有效的算法，也许是近似解的算法？
此问题与问题 here 类似，但不同之处在于我的图表比链接问题中的图表大。还有其他几个类似的问题，但我看到的 none 完全解决了我的具体问题。
如果允许多次访问相同的节点，请找到每对强制顶点之间的最短路径。然后使用上述最短路径成本解决强制顶点之间的 TSP。如果你不允许多次访问，问题就更糟了。
恐怕你逃不过TSP