c - 如何更改嵌套 for 循环中的行和列索引?
问题描述
我试图找出最短的城市旅行距离。我已经有了一个起点,城市'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;
}
推荐阅读
- python - 如何在 Django 中使用 AJAX 从 html 中正确调用函数/url?
- datatables - Datatables AJAX.reload 回调数据
- sql - SAS SQL JOIN 输出到表
- python - 将特定文本附加到输出数据以生成 url
- php - 如何访问我在 Magento 中创建的自定义属性?(在 PHP 中)
- azure-ad-b2c - 是否有托管在任何地方的 Azure B2C 示例应用程序?
- android - React Native android:在其父级范围之外的绝对定位的可触摸元素不可点击
- dockerfile - 链式 docker 镜像启动 httpd 和 php
- python - Selenium send_keys 太快了
- google-cloud-firestore - Firestore 本机模式下的 ComputedProperty (ndb Datastore) 等效项