我正在尝试计算出这座城市的最短距离。 我已经有了一个起点,城市“0”,然后我们将访问每一个城市,而不会重新访问前一个城市。这样的话,我们就不需要回到0号城市了。
假设我们有 4 个城市,那么我们将有一个包含距离的矩阵。 我想做的是迭代每条可能的路线并获取每条路线的成本。
所以城市号为 4 的所有可能路线是
city[0][1] + city[1][2] + city[2][3]
city[0][1] + city[1][3] + city[3][2]
city[0][2] + city[2][1] + city[1][3]
city[0][2] + city[2][3] + city[3][1]
city[0][3] + city[3][1] + city[1][2]
city[0][3] + city[3][2] + city[2][1]
我的问题是如何为这些方程制作嵌套 for 循环? 我可以看到有一种模式,“列索引”应该转到下一个“行索引”,依此类推。
最佳答案
您正在寻找第一个城市固定的所有城市的排列。如果城市数量固定,您可以编写多个嵌套的 for
循环,但这很快就会变得很麻烦。
相反,递归地排列数组:
- 创建一个包含访问城市顺序的数组
path
;以 {0, ..., N - 1} 开头。 - 选择一个起始索引。如果您想要所有可能的起始品脱,请选择 0。在这里,第一个城市是固定的,因此从索引 1 开始,因为
path[1]
是第一个应该更改的条目。 - 调用排列函数:
- 现在,如果仍有城市需要排列,则依次将每个城市交换到下一个位置,使用下一个索引调用排列函数,然后将城市交换回来。当你递归时,记录当前的距离。
- 如果没有更多城市,则您已到达列表末尾。打印路径和距离或者任何你想做的事情,不要做任何其他事情。
代码如下:
#include <stdlib.h>
#include <stdio.h>
enum {
N = 4 // number of cities
};
const int city[N][N] = {
{0, 2, 5, 5},
{2, 0, 3, 4},
{5, 3, 0, 6},
{5, 4, 6, 0},
};
/*
* Swap array elements at indices i and j
*/
void swap(int a[], int i, int j)
{
if (i != j) {
int swap = a[i]; a[i] = a[j]; a[j] = swap;
}
}
/*
* Permute the subarray of length n, starting at index i
*/
void perm(int path[], int i, int n, int weight)
{
int j;
if (i == n) { // path is exhausted:
for (j = 0; j < n; j++) { // print path and distance
printf("%c ", 'A' + path[j]);
}
printf("-> %d\n", weight);
} else { // more cities to visit:
for (j = i; j < n; j++) { // pick each of them as ...
int w = 0; // ... destination
if (i > 0) { // determine distance ...
w = city[path[i - 1]][path[j]]; // ... from prev. city,
} // ... if any
swap(path, i, j); // swap city in;
perm(path, i + 1, n, weight + w); // recurse;
swap(path, i, j); // swap city back
}
}
}
int main()
{
int path[N];
int i;
for (i = 0; i < N; i++) path[i] = i; // initial path
perm(path, 1, N, 0);
return 0;
}
关于c - 如何更改嵌套 for 循环中的行索引和列索引?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55872749/