用图搜索法：广度优先、深度优先和A*算法实现八数码问题 第2页

{char     x;                   //位置x和位置y上的数字换位

 char     y;                   //其中x是0所在的位置

} EP_MOVE;

#define SIZE         3            //8数码问题，理论上本程序也可解决15数码问题，

#define NUM          SIZE * SIZE //但move_gen需要做很多修改，输入初始和结束状态的部分和check_input也要修改

#define MAX_NODE     1000000

#define MAX_DEP      100

#define XCHG(a, b)   { a=a + b; b=a - b; a=a - b; }

#define TRANS(a, b)

{ long     iii; (b)=0; for(iii=0; iii < NUM; iii++) (b)=((b) << 4) + a[iii]; }    //将数组a转换为一个64位的整数b

#define RTRANS(a, b) \

     { \

         long     iii; \

         UINT64   ttt=(a); \

         for(iii=NUM - 1; iii >= 0; iii--) \

         { \

             b[iii]=ttt & 0xf; \

             ttt>>=4; \

         } \

     }    //将一个64位整数a转换为数组b

//

typedef struct   EP_NODE_Tag

{ UINT64              v;   //保存状态，每个数字占4个二进制位，可解决16数码问题

 struct EP_NODE_Tag   *prev;   //父节点

 struct EP_NODE_Tag   *small, *big;

} EP_NODE;

EP_NODE m_ar[MAX_NODE];

EP_NODE *m_root;

long     m_depth;                 //搜索深度

EP_NODE m_out[MAX_DEP];          //输出路径

//

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 下一页