[算法]穷举寻径。。。

iptton

中国象棋棋盘上，从指定的起始位置，到达指定的位置，马有哪几条路径。

初略写了算法描述，就去听单片机讲座了，想想那个算法有考虑不周的地方。。。


试卷上说的好像是从左上角到右下角　的一个特例，
上面的题目是刚在研发中心的论坛上发现的

[ 本帖最后由 iptton 于 2006-10-21 21:50 编辑 ]

iptton

核心算法没写上，先帖了。。。

1. 
   
2. #include <stdio.h>
   
3. typedef struct point{
   
4.   int x;
   
5.   int y;
   
6.   int flag;
   
7. }T_chess[9][10];
   
8. struct pointStack{
   
9.   struct point * value;
   
10.   struct pointStack *next;
    
11. }
    
12. 
    
13. T_chess chess;
    
14. 
    
15. 
    
16. void findDir(struct point*,struct point*);
    
17. void printDir(struct point*);
    
18. struct pointStack * allocStack(struct point* value);
    
19. 
    
20. int main(){
    
21.   struct point start,end;
    
22. 
    
23.   //initial data
    
24.   for(i=0;i<9;i++){
    
25.     for(j=0;j<10;j++){
    
26.       chess[i][j].x=i;
    
27.       chess[i][j].y=j;
    
28.       chess[i][j].flag=0;
    
29.     }
    
30.   }
    
31. 
    
32.   scanf("%d %d %d %d",&start.x,&start.y,&end.x,&end.y);
    
33.   start.flag=1;
    
34.   end.flag=0;
    
35. 
    
36.   findDir(&start,&end);
    
37. }
    
38. 
    
39. void findDir(struct point *s,struct point *e)
    
40. {
    
41. 
    
42. 
    
43. }
    
44. void printDir(struct pointStack *s)
    
45. {
    
46.   struct pointStack *tmp;
    
47.   while(!s){
    
48.     printf("[%d,%d]  ",(s->value).x,(s->value).y);
    
49.     tmp=s->next;
    
50.     s=tmp;
    
51.   }
    
52. 
    
53. }
    
54. struct pointStack * allocStack(struct point * value){
    
55.   struct pointStack *ret=malloc(sizof(struct pointStack));
    
56.   ret->next=null;
    
57.   ret->value=s;
    
58.   return ret;
    
59. }
    

复制代码

[ 本帖最后由 iptton 于 2006-10-21 19:47 编辑 ]

Freedomer

lz能不能简单介绍一下这个算法啊,我看到这道题是,根本不知从什么方向着手...

iptton

楼上可以去找找　寻径算法　
搜索这两个关键词：
　深度优先　　回溯


算法的计算机实现是要依赖相应的数据结构的，

不过学C语言时已学过链表了，所以这道题应该只是考算法设计

说说我的思路：
  

         每走一步之前，
　　　
　　　1　
　　　　找到下一步可以走的所有的位置，
　　　　标记之（如图中点红色，本来应该各个点的“红”色都不同才对的。。。），
　　　　　
　　　　选择上面标记　红　了的步中一步
　　　　标记此步为已经走过了（如图中的黑色），以免在同两步上死循环

　　　2
　         。。。。。。（有空再写）
　　　　

   

　　　
　　　计算机对每一个点（棋位）的信息存储应当包括：X，Y座标，当前路径是否已走过这一步的标记（flag）,如果这一步走完了,以这一步为起点可走的(即FLAG为false的)点的位置组（为节省空间，可用链表），所以一个点的数据结构应该为：

1. 
   
2. typedef struct point{
   
3.       int x;　　　       //     [0,9)
   
4.       int y;                   //     [0,10)
   
5.       int flag;                //0 OR 1
   
6.       struct point*next;
   
7. }T_point[9][10];       //因为中国象棋只有　10＊9                     
   

复制代码

为保存以走的路径信息，又需要一个组有顺序，按先进后出规则操作的的空间（一般称这个为栈）：

1. 
   
2. struct curPath{
   
3.     struct point *pointInPath;    //为节省空间，用指针，初始化时要记得用NULL
   
4.     struct curPath* next;           //
   
5. }
   

复制代码

[ 本帖最后由 iptton 于 2006-10-22 12:42 编辑 ]

iptton

很明显，第二次回溯后的线路是不能到达目的点的（这个因应该是这个问题的解的优化之处）

powerwind

IP，这个可能对你有帮助。

较高人工智能的人机博弈程序实现(多个算法结合)含C++源码

iptton

这道题只是一道很简单的算法题。。。

离AI还远着呢。。。。