0

我有一个包含 1000 个节点的完整加权图，需要在图中找到最长的哈密顿路径（更准确地说是节点序列）。我应该适合 5 秒（对于 Java），内存限制足够大。寻找最长的哈密顿路径看起来与寻找 TSP（旅行推销员）的解决方案没有太大区别。当然，最佳解决方案是不可能的，所以我正在寻找一个好的启发式方法。到目前为止，我最好的解决方案是使用最近邻算法，该算法易于实现并在多项式时间内运行（1000 个节点图大约需要 0.7 秒）。虽然它离最佳解决方案有点远。所以我正在寻找一种运行速度相对较快的更好的启发式算法。我看到提到禁忌搜索、模拟退火、蚁群、遗传学、分支和绑定，基于 MST 的算法等。问题是，由于它们的实现并不是微不足道的，因此很难找到它们的时间复杂度来决定哪些可以在 5 秒内完成。时限; 例如在多项式时间内运行。对于像 Christofides' 这样的一些算法，我看到复杂度是 O(V^4)，其中 V 是顶点数，这显然使得它无法拟合。

我遇到了 Bitonic Tour 解决方案，通常用于在欧几里得图中找到最短的哈密顿路径，但似乎也可以在非欧几里得图中找到最长的路径：

    public static void minCostTour(int[][] graph) {
        int n = graph.length;
        int[][] dp = new int[n][n];
        dp[0][1] = graph[0][1];

        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++)
                if (i == (j - 1) && i != 0) {
                    dp[i][j] = dp[0][j-1] + graph[0][j];
                    for (int k = 1; k <= j - 2; k++)
                        if ((dp[k][j-1] + graph[k][j] < dp[i][j])) { 
                            dp[i][j] = dp[k][j-1] + graph[k][j];
                        }
                } else if (i != 0 || j != 1) {
                    dp[i][j] = dp[i][j-1] + graph[j-1][j];
                }
        }
        System.out.println("Optimal Tour Cost: " + (dp[n-2][n-1] + graph[n-2][n-1]));
    }

标准算法包括坐标的初始排序，我跳过了它，因为显然没有坐标要排序（图是非欧几里得）。这个动态编程解决方案在 O(V^2) 中运行，所以它可能很好。问题是它输出哈密顿路径长度，我需要节点序列。我真的不明白如何从上述算法中恢复路径（如果可能的话）。

TL DR 版本： 上面的双调游算法能否用于在完整加权图中查找最长哈密顿路径上的节点序列？如果没有，您能否为该任务推荐具有相似（多项式）时间复杂度的算法？

4

0 回答 0