BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ zhuxiao (蜗牛) 于 (Sun Dec 31 00:34:51 2006) 提到: 骑士遍历的算法分析和去边法求最小生成树的算法复杂度分别为多少?我在网上搜了半天也没找到~~郁闷~~ ☆─────────────────────────────────────☆ dby (猪的天空之猪很无奈) 于 (Sun Dec 31 20:01:46 2006) 提到: 不是达人，路过…… 骑士遍历是求哈密顿路，NP问题。至于去边法，我不是太清楚这个算法…… ☆─────────────────────────────────────☆ xiaoming (namespace) 于 (Mon Jan 1 01:18:04 2007) 提到: 骑士遍历可以用构造的方法去求哈密顿路，有Ｏ（Ｎ＾２）的算法．去边法去边时排序最快要用Ｏ（N^2LOGN），然去每条边删了后用深搜或广搜去判连通看试是否能删，枚举最大边是O(N^2)再用深搜或广搜O(n),总的应该是 O(N^3) ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Tue Jan 2 20:27:16 2007) 提到: 怎么构造？【在 xiaoming 的大作中提到: 】 ☆─────────────────────────────────────☆ namespace (dev c++) 于 (Wed Jan 3 10:23:41 2007) 提到: //先计算每个格点的度数，然后选一个开始点，每次都往度数最少的点走就可以了 #include<stdio.h> main() { int i,j,m,n,k,x,y,p,min; int step[9][3]={{0,0,0}, {0,2,1}, {0,2,-1}, {0,1,2}, {0,1,-2}, {0,-1,2}, {0,-1,-2}, {0,-2,1}, {0,-2,-1}}; int a[9][9];//节点的度数 int object[9][9];//漫游时候的次序 for(i=1;i<=8;i++) for(j=1;j<=8;j++) a[i][j]=0; for(i=1;i<=8;i++) for(j=1;j<=8;j++) for(k=1;k<=8;k++) { x=i+step[k][1]; y=j+step[k][2]; if(x>0&&x<=8&&y>0&&y<=8) a[x][y]++; } printf("请输入初始的位置.\n "); scanf("%d",&i); scanf("%d",&j); for(k=1;k<=63;k++) { min=10; object[i][j]=k; for(p=1;p<=8;p++) { x=i+step[p][1]; y=j+step[p][2]; if(x>0&&x<=8&&y>0&&y<=8) if(a[x][y]!=0) { a[x][y]--; if(a[x][y]<min) { min=a[x][y]; m=x; n=y; } } } a[i][j]=0; i=m;j=n; } object[i][j]=64; for(i=1;i<=8;i++) { for(j=1;j<=8;j++) printf("%d\t",object[i][j]); printf("\n\n"); } system("pause"); } ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Wed Jan 3 10:34:40 2007) 提到: 这个思路怎么来的？【在 namespace 的大作中提到: 】 ☆─────────────────────────────────────☆ namespace (dev c++) 于 (Wed Jan 3 10:38:45 2007) 提到: 大一Ｃ语言的课本上有这样的例子，好像是说要我们用各种方法去解这个问题，然后比较效率．．．方法的正确性证明我也不知道 ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Wed Jan 3 10:53:40 2007) 提到: 这个方法是书上的？ ☆─────────────────────────────────────☆ namespace (dev c++) 于 (Wed Jan 3 10:56:19 2007) 提到: 那当然．．．．． ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Wed Jan 3 11:36:28 2007) 提到: 书是什么名字？ ☆─────────────────────────────────────☆ xiaolonghing (xiaolonghingis) 于 (Wed Jan 3 11:39:32 2007) 提到: 【在 namespace 的大作中提到: 】当年漆涛让编骑士漫游我就用的这个方法，不过加了回溯。仅仅这样构造不回溯的话这个方法是不能保证正确性的，只是因为8＊8的可以找到一条路径罢了，我觉得骑士漫游还是属于np问题，这种构造只是在有解的情况下能提高效率。 ☆─────────────────────────────────────☆ xiaolonghing (xiaolonghingis) 于 (Wed Jan 3 11:40:45 2007) 提到: 【在 sunmoonstar 的大作中提到: 】那本绿皮书，C程序设计教程。 ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Wed Jan 3 12:45:19 2007) 提到: 可不可以推广到 4k*4k k = 1,2,3...... 【在 xiaolonghing 的大作中提到: 】 ☆─────────────────────────────────────☆ dby (猪的天空之猪很无奈) 于 (Wed Jan 3 13:20:38 2007) 提到: I think it's wrong when 2,7 5,5 5,8 【在 namespace 的大作中提到: 】 ☆─────────────────────────────────────☆ namespace (dev c++) 于 (Wed Jan 3 15:08:04 2007) 提到: 我也发现了．．．．是错的．．．．可能真的要用回朔才能保证正确性．．．．．那个方法可能是只能更快的找到路径．．．．是不是用点像Ａ＊的算法．． ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Wed Jan 3 16:24:19 2007) 提到: namespace 够猛啊, A*算法怎么做【在 namespace 的大作中提到: 】 ☆─────────────────────────────────────☆ xiaolonghing (xiaolonghingis) 于 (Wed Jan 3 16:42:15 2007) 提到: 【在 sunmoonstar 的大作中提到: 】同问，A*怎么做？我还是觉得只能暴搜。用那些方法在有解得情况下比较快，但无解时和暴搜一样的效率 ☆─────────────────────────────────────☆ namespace (dev c++) 于 (Wed Jan 3 17:37:25 2007) 提到: 我也不知道怎么做．．．．．我在想是不是用原来的方法去暴搜会快一些。 ☆─────────────────────────────────────☆ namespace (dev c++) 于 (Wed Jan 3 17:44:02 2007) 提到: 有无解的情况的吗．．．对于８＊８来说是有解的．除非是特殊的边长．．．．其实我自己也不懂什么的，各位大牛不用这样．．．．． ☆─────────────────────────────────────☆ namespace (dev c++) 于 (Wed Jan 3 17:47:09 2007) 提到: 只是受书上的误导写了个错误的算法．．．．．．． ☆─────────────────────────────────────☆ dby (猪的天空之猪很无奈) 于 (Wed Jan 3 19:21:52 2007) 提到: 大家一起讨论而已，没什么的~ ：）【在 namespace 的大作中提到: 】 ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Wed Jan 3 19:34:53 2007) 提到: n = 4k 的情况可以保证正确吗? 【在 namespace 的大作中提到: 】 ☆─────────────────────────────────────☆ xiaolonghing (xiaolonghingis) 于 (Wed Jan 3 21:23:44 2007) 提到: 【在 namespace 的大作中提到: 】呵呵，大家都是讨论嘛。你这会已经很强了，明年acm的绝对牛人阿。。我在你这会还不知道干嘛呢？一直后悔直到大二下才接触acm，浪费了一年，sigh。。 ☆─────────────────────────────────────☆ namespace (dev c++) 于 (Wed Jan 3 21:32:03 2007) 提到: 【在 sunmoonstar 的大作中提到: 】Ｎ＝８的时候不用回溯也是错的，ＤＢＹ在上面有几个例子了．．．．我自已也找到错的了．

骑士遍历和去边法求最小生成树