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

/*返回值：成功－返回搜索节点数，节点数不够－(-1)，无解－(-2)*/

long bfs_search(char *begin, char *end)

{    long     h=0, r=1, c, i, j;

     EP_NODE l_end, node, *pnode;

     EP_MOVE mv[4];                       //每个局面最多4种走法

     TRANS(begin, m_ar[0].v);

     TRANS(end, l_end.v);

     m_ar[0].prev=NULL;

     m_root=m_ar;

     m_root->small=NULL;

     m_root->big=NULL;

     while((h < r) && (r < MAX_NODE - 4))

     {   c=move_gen(&m_ar[h], mv);

         for(i=0; i < c; i++)

         {   mov(&m_ar[h], &mv[i], &node);

             node.prev= &m_ar[h];

             if(node.v == l_end.v)

             {   pnode= &node;

                 j=0;

                 while(pnode->prev)

                 {   m_out[j]=*pnode;

                     j++;

                     pnode=pnode->prev;

                 }

                 m_depth=j;

                 return r;

             }

             if(add_node(&node, r)) r++; //只能对历史节点中没有的新节点搜索，否则会出现环

         }

         h++;

         printf("\rSearch...%9d/%d @ %d", h, r, get_node_depth(&m_ar[h]));

     }

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