已知所有点的坐标，求经过所有点的最短路径
求助：已知所有点的坐标，求经过所有点的最短路径
Dijkstra算法 贪心算法之类的都是找两点的最短路径了。。我是要经过所有点
大婶们 有没有思路啊？
------解决方案--------------------
仅供参考
本帖最后由 huangdigege 于 2014-05-27 12:17:17 编辑
如题，不是找两点的最短路径，是连接所有点的最短路径。Dijkstra算法 贪心算法之类的都是找两点的最短路径了。。我是要经过所有点
大婶们 有没有思路啊？
------解决方案--------------------
仅供参考
//1 2 3
//4 5 6 求一笔划过所有9个键的所有方法
//7 8 9
#include <stdio.h>
int g[10][9]={
{0,0,0,0,0,0,0,0,0},
{2,4,5,0,0,0,0,0,0},//1
{1,3,4,5,6,0,0,0,0},//2
{2,5,6,0,0,0,0,0,0},//3
{1,2,5,7,8,0,0,0,0},//4
{1,2,3,4,6,7,8,9,0},//5
{2,3,5,8,9,0,0,0,0},//6
{4,5,8,0,0,0,0,0,0},//7
{4,5,6,7,9,0,0,0,0},//8
{5,6,8,0,0,0,0,0,0},//9
};
int k,i,n;
int h[10];//记录是否划过h[1..9],history
int p[10];//记录划的顺序p[1..9],path
void go(int f,int L) {
int j;
if (L==9) {
p[L]=f;
n++;
printf("%08d:",n);
for (i=1;i<=9;i++) printf(" %d",p[i]);
printf("\n");
} else {
p[L]=f;
h[f]=1;
j=0;
while (1) {
if (g[f][j]==0) break;
if (h[g[f][j]]==0) {
go(g[f][j],L+1);
h[g[f][j]]=0;
}
j++;
}
}
}
int main() {
n=0;
for (k=1;k<=9;k++) {
for (i=1;i<=9;i++) h[i]=0;
go(k,1);
}
return 0;
}
//00000001: 1 2 3 5 4 7 8 6 9
//00000002: 1 2 3 5 4 7 8 9 6
//00000003: 1 2 3 5 6 9 8 4 7
//00000004: 1 2 3 5 6 9 8 7 4
//00000005: 1 2 3 5 7 4 8 6 9
//00000006: 1 2 3 5 7 4 8 9 6
//00000007: 1 2 3 5 9 6 8 4 7
//00000008: 1 2 3 5 9 6 8 7 4
//00000009: 1 2 3 6 5 4 7 8 9
//00000010: 1 2 3 6 5 7 4 8 9
//00000011: 1 2 3 6 5 9 8 4 7
//00000012: 1 2 3 6 5 9 8 7 4
//00000013: 1 2 3 6 8 4 7 5 9
//00000014: 1 2 3 6 8 7 4 5 9
//00000015: 1 2 3 6 8 9 5 4 7
//00000016: 1 2 3 6 8 9 5 7 4
//00000017: 1 2 3 6 9 5 4 7 8
//00000018: 1 2 3 6 9 5 4 8 7
//00000019: 1 2 3 6 9 5 7 4 8
//00000020: 1 2 3 6 9 5 7 8 4
//00000021: 1 2 3 6 9 5 8 4 7
//00000022: 1 2 3 6 9 5 8 7 4
//00000023: 1 2 3 6 9 8 4 5 7
//00000024: 1 2 3 6 9 8 4 7 5
//00000025: 1 2 3 6 9 8 5 4 7
//00000026: 1 2 3 6 9 8 5 7 4
//00000027: 1 2 3 6 9 8 7 4 5
//00000028: 1 2 3 6 9 8 7 5 4
//00000029: 1 2 4 5 3 6 9 8 7
//00000030: 1 2 4 5 7 8 9 6 3
//00000031: 1 2 4 7 5 3 6 8 9
//00000032: 1 2 4 7 5 3 6 9 8
//00000033: 1 2 4 7 5 8 9 6 3
//00000034: 1 2 4 7 5 9 8 6 3
//00000035: 1 2 4 7 8 5 3 6 9
//00000036: 1 2 4 7 8 5 9 6 3
//00000037: 1 2 4 7 8 6 3 5 9
//00000038: 1 2 4 7 8 6 9 5 3
//00000039: 1 2 4 7 8 9 5 3 6