c - 如何打印旅行商问题中的路径

Question

我试图用C解决旅行商问题。我成功地计算出正确的最小距离，但我似乎无法生成相应的路径。 注意:我不需要回到第一个城市，这就是为什么功能可能与经典城市略有不同。

我用来解决这个问题的想法如下: 我递归地调用一个名为travelingSalesMan的函数，如果访问过的所有城市(我使用访问过的数组来跟踪访问过的城市)或当前遵循的路径大于前一个路径，我只返回当前距离之间的最小值，存储在变量中，以及当前的最小距离(在开始时设置为最大)。

我尝试使用一个名为 currentPath 的数组以及 pathLen 来跟踪路径，它告诉我路径中有多少个元素。

这是我现在拥有的代码:

int travelingSalesMan(int** distMatrix, int arrSize,  int* visited, int currentCity, int* currentPath, int cur_dist, int min_dist, int* minPath, int pathLen){


    if (complete(visited, arrSize) == arrSize) {
        // minPath[index] = currentPath[index];
        printf("Path len: %d\n", pathLen);
        for(int i = 0; i<arrSize; i++){
            minPath[i] = currentPath[i];
        }
        minPath[arrSize - 1] = currentCity;
        return min(cur_dist, min_dist);
    }

    // no need to pursue the path that is not minimum
    if(cur_dist >= min_dist){
        pathLen--;
        return min(cur_dist, min_dist);
    }

    for (int i = 0; i<arrSize; i++) {
        if (visited[i] == 0 && i != currentCity) {
            cur_dist += distMatrix[currentCity][i];

            currentPath[pathLen++] = currentCity;
            visited[i] = 1;
            min_dist = travelingSalesMan(distMatrix, arrSize, visited, i, currentPath, cur_dist, min_dist, minPath, pathLen);
            visited[i] = 0;

            cur_dist -= distMatrix[currentCity][i];
            pathLen--;
        }
    }


    return min_dist;
}

我使用以下参数调用了上面的函数:

distance = travelingSalesMan(distMatrix, N, visited, 0, currentPath, 0, INT_MAX, minPath, 1);

对于给定的 distMatrix:

[
{0 10 10 10 10}
{10 0 2 4 11}
{10 2 0 12 4} 
{10 4 12 0 8}
{10 11 4 8 0}
]

最小权重为 20，因此我期望看到如下路径:

0 3 1 2 4 

谢谢!

Answer 1

在 block 中if (complete(visited, arrSize) == arrSize) { 仅当当前路径短于找到的最佳路径时，才应写入 min_path。