使用每个节点恰好一次从源节点到结束节点的路由的算法

Question

我正在尝试创建一条路线，给定起始节点和结束节点，它将行进到图中的每个节点，并最大限度地减少这样做的成本。

该图是无向的，每个节点都直接相互连接。每条边的权重都是正的。我认为因为每个节点都相互连接，所以我的图中有很多 "loops"，但我不想生成一个带有循环的路由。

因此，对于具有 N 个节点的图，我有 (N*N-1) 条有向边。具有节点 A、B、C、D 的图将具有边：

A 到 B / B 到 A
A 到 C / C 到 A
A 到 D / D 到 A
B 到 C / C 到 B
C 到 D / D 到 C
B 到 D / D 到 B

当我从维基百科实施 Floyd Warshall 算法时，我只得到一个包含 2 个节点的数组。文中有一个函数可以给你从节点U到节点V的最短路径，也就是那个函数只需要returns [U,V]（包含U和V的数组）

我一定是误解了 Floyd Warshall 到底要解决什么问题。我将附上我的代码以展示我是如何在 javascript.

中实现它的

    function colorsToEdgeMatrix(colors){
        var dist = [];
        for(var i = 0; i < colors.length;i++){
        dist[i] = [];
        var c1 = colors[i];
        for(var j = 0; j < colors.length;j++){
           if(i == j){continue;}
        var c2 = colors[j];
        dist[i][j] = colorDistance(c1,c2);
        }
    }
    return dist;
}
    function colorsToNextMatrix(colors){
        var next = [];
        for(var i = 0; i < colors.length;i++){
            next[i] = [];
            for(var j = 0; j < colors.length;j++){
                if(i == j){continue;}
                next[i][j] = j;
            }
        }
        return next;
    }
    //lab colors
    function FloydWarshallWithPathReconstruction (colors){
       var next = [];
       var dist = colorsToEdgeMatrix(colors);
       var next = colorsToNextMatrix(colors);
       var N = colors.length;
        for(var k = 0; k < N; k++){ // standard Floyd-Warshall implementation
            for(var i = 0; i < N; i++){
                for(var j = 0; j < N; j++){
                    if(dist[i][k] + dist[k][j] < dist[i][j]){
                       dist[i][j] = dist[i][k] + dist[k][j]
                       next[i][j] = next[i][k]
                    }
                }
            }
       }
       return next;
    }

    function Path(next,u, v) {
       var path = [];
       if(next[u][v] == null){
           return []
       }
       path = [u]
       while(u != v){
           u = next[u][v]
           path.push(u)
       }
       return path;
    }


    var lab = randomLABArray(100); //make an array of LAB color space colors. a LAB element has an array structure [L,a,b]
    lab = sortLuminosityLAB(lab); //sorts the LAB colors from light to dark
    var next = FloydWarshallWithPathReconstruction(lab); //gets all paths using floyd warshall
    var path = Path(next, 0, lab.length-1); //gets the path calculated from lightest to darkest
    console.log( path );

这个算法不一定return一条路径经过每个节点吗？我猜它所做的只是为每个开始和结束节点吐出最佳路径，并不能保证任何路径都经过每个节点...

我使用了最近邻算法，结果还不错，10个元素后暴力破解是不可能的。我希望 Floyd Warshall 能给出更好的结果

嗯...所以这实际上可能是哈密顿路径问题，并不像我想的那么简单...

Answer 1

这可以简化为旅行商问题，如下所示。选择一个大于图中所有权重总和的大数 M。将此数字添加到图中所有边上的权重除了连接起始节点和结束节点的边。该边缘的成本应设置为零。解决由此产生的旅行商问题。很容易看出，TSP 的最优解将包括连接起始节点和结束节点的边。从最佳解决方案中剔除该优势并将权重调整回其原始值 - 您已经找到了问题的最佳解决方案。

相反，常规 TSP 可以更简单地简化为您的问题。随机选择一个节点并复制它。设这些新复制的节点之一为起始节点，另一个为结束节点。解决此实例的最佳路径问题。然后——将这两个节点重新合并到原始节点中，它将端点拼接在一起形成一个电路，这很容易看出是最优的。这证实了您的直觉，即该问题至少与哈密顿电路问题一样难。

使用每个节点恰好一次从源节点到结束节点的路由的算法

Algorithm to make a route from Source Node to End Node using every node exactly once

graph

routes

traveling-salesman

floyd-warshall