上次看啊哈算法中的深度优先搜索,自己用的是linux(linux粉,windows黑,嘿嘿),字符界面,为了强化对这个的理解,就在linux上对这个例子的代码做了一点修改可以很清楚的看到整个搜索过程,相当于动态的展示吧,虽然不是动画,本来想用QT来写的,不过实在是没时间(其实是QT太久没用了.....)
深度优先搜索说到底就是一条道走到黑直到达到目的,然后再往回走,看看上次选择的地方是否还有别的路可以选择走。代码中定义了宏MAX_NUM=8,
就是8x8的迷宫,
用户输入开始点和结束点,找到开始点到结束点的最短路径。LOOK:
其中工代表可以走的路,山是随机出现的20个障碍。
当指定了起始点后(没做校验,不能落在障碍点上),会将整个搜索过程在界面上打印出来,每秒显示一步:
当然也可能觉得不停的打印会太繁琐,那就将dfs中的调用dfs_print和sleep注释掉即可。
再看看最终的结果:
这个只是其中一条最短路径,而为了减少运算量,我将当前的路径长度和已经找到的路径长度做对比,大于等于时就不往下找了。
因为当迷宫是40*40,没有加这个,我的虚拟机运行了1分钟都没有出来结果(当然是将打印去掉的情况下)。
源码:
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #define MAX_NUM 8 5 6 void dfs_print(); 7 8 int maze[MAX_NUM][MAX_NUM]; 9 int book[MAX_NUM][MAX_NUM]; 10 int map[MAX_NUM][MAX_NUM]; 11 int min=10000; 12 int px,py; 13 int startx, starty; 14 15 int next[4][2] = { 16 {0,1}, 17 {1,0}, 18 {0,-1}, 19 {-1,0}}; 20 21 void dfs(int x, int y, int step) 22 { 23 int i; 24 int tx,ty; 25 26 /* 27 printf(" "); 28 dfs_print(); 29 sleep(1); 30 */ 31 32 if(step >= min) 33 return; 34 if(x==px && y==py) 35 { 36 printf("SUCCESS! 本次路径长度=%d", step); 37 if(step < min) 38 { 39 printf("本路径是当前最短的路径"); 40 memcpy(map, book, sizeof(book)); 41 min= step; 42 } 43 printf(" "); 44 return; 45 } 46 47 48 for(i=0;i<=3;i++) 49 { 50 tx = x+next[i][0]; 51 ty = y+next[i][1]; 52 if(tx <0 || tx >=MAX_NUM || ty <0 || ty >= MAX_NUM) 53 continue; 54 55 if(book[tx][ty] == 0 && maze[tx][ty] == 0) 56 { 57 book[tx][ty] = 1; 58 dfs(tx,ty,step+1); 59 book[tx][ty] = 0; 60 } 61 } 62 return; 63 } 64 65 void dfs_print() 66 { 67 int i,j; 68 printf("