A*算法实现迷宫最短路径搜索（C＋＋实现）

          在今天早上的时候，我还到处“求医问药”希望能解决程序中未能解决的问题，郁闷了一天，总算是明白问题是出在什么地方的了。好了，还是先将迷宫算法的解决 算法发上来，之后再讨论之前的问题出在什么地方，又是怎样解决的。

迷宫算法如下：

//#############################################################//

//在VC6及vs2005里面都没有调试通过，在MinGW Developer Studio和gCC里面调试通过

#include
#include
#include
#include

#define MAZE_ROW      9
#define MAZE_COL      7

char maze[MAZE_ROW][MAZE_COL]={
' ',' ',' ','#','#','#','#',
'#','#',' ','#','#','#','#',
' ','#',' ','#','#','#','#',
' ','#',' ',' ',' ',' ',' ',
' ',' ','#','#','#','#',' ',
'#',' ',' ',' ',' ','#',' ',
'#','#',' ','#',' ','#',' ',
' ',' ',' ',' ','#','#',' ',
' ',' ','#',' ',' ','#',' ',
};

typedef struct {
int gn;
int fn;
int flag; //1——in open; 2——in close
}GFN;

map gmap; //g值

int Bi=0, Bj=0;
int Ei=6, Ej=6;

bool opensort(int n1,int n2)
{
map::iterator pos1,pos2;
pos1 = gmap.find(n1);
pos2 = gmap.find(n2);
return pos1->second->fn < pos2->second->fn;
}

void getway(int i,int j,int gn);     //输出路径
void printmaze();
void printway();
bool isok(int i,int j);//判断n1位置为迷宫中可以走的位置

int main()
{
vector open;
vector close;

map::iterator pos;
vector::iterator it;

int n,gn,fn;
int n1,gn1,fn1;
int ci,cj;
int ni,nj;

GFN* pgf = NULL;

printmaze();

ci = Bi;
cj = Bj;

n = ci*MAZE_COL + cj;
gn = 0;
fn = abs(Ei-ci)+abs(Ej-cj);

pgf=new GFN;
pgf->gn = 0;
pgf->fn = fn;
pgf->flag = 1;

gmap[n] = pgf;
open.push_back(n);

while(!open.empty()){
     n = open.front(); //pop front from open
     open.erase(open.begin());

     ci = n/MAZE_COL;       //the corren sit
     cj = n%MAZE_COL;

     pos = gmap.find(n);     //find the sit
     gn = pos->second->gn;
     fn = pos->second->fn;

     pos->second->flag = 2;
     close.push_back(n);     //push n into close

     if(ci==Ei && cj==Ej)
     {
      cout<<"找到最短路径，长度为："< //      getway(Ei,Ej,gn-1);
//      printway();
      return 1;
     }

     gn1 = gn+1;
     for(int d=0; d<4; ++d){
      ni = ci;
      nj = cj;
      switch(d){
      case 0 : //left derect
       nj = cj-1;
       break;
      case 1 : //up derect
       ni = ci-1;
       break;
      case 2 : //right derect
       nj = cj+1;
       break;
      case 3 : //down derect
       ni = ci+1;
       break;
      }//end_switch
   
      if(isok(ni,nj)){
       n1 = ni*MAZE_COL+nj;
       fn1 = abs(Ei-ni)+abs(Ej-nj)+gn1;
       pos = gmap.find(n1);
       if(pos!=gmap.end()){//n1 is old
        if(pos->second->fn   >   fn1){
         pos->second->fn = fn1;
         pos->second->gn = gn1;
         if(pos->second->flag==2){
          it = find(close.begin(),close.end(),n1);
          close.erase(it);
          open.push_back(n1);
         }
         sort(open.begin(),open.end(),opensort );
        }
       }
       else{//
        pgf = new GFN;
        pgf->gn = gn1;
        pgf->fn = fn1;
        pgf->flag = 1;

        gmap[n1] = pgf;
        open.push_back(n1);
        sort(open.begin(),open.end(),opensort );
       }//end_else
      }//end_if
     }//end_for
}//end_while

cout<<"没有路径可以到达出口！\n\n\n"< return 1;
}

bool isok(int i,int j) //判断n1位置为迷宫中可以走的位置
{
if( i>=0 && i<=MAZE_ROW && j>=0 && j<=MAZE_COL && maze[i][j]==' ')
     return true;
return false;
}

void printmaze()
{
cout<<"迷宫："< for(int i=0; i      for(int j=0; j       cout<      cout< }
cout<<"入口坐标为：("<

}
//#############################################################//

早上的问题：

原来在这个程序里面，我用的是list作为open和close的容器，然而在使用中的sort对open排 序时总是有9个错误，在MinGW Developer Studio里调试都一样，我就到处求教，我很是郁闷，下午睡了一觉，醒来想到list里面本身有sort成员函数,可能 是中的sort不支持list，于是我按照的我的想法写了一个小的test代码来验证一下。哇噻,原来真是这样，看 来问题就是出在这里。于是解决的办法有如下两种：

             办法一：将list改为vector容器，相应的open.pop_front()改为open.erase(pop.begin());这 样里的sort就可以比较对open表排序了。
             办法二：对open排序的地方（及sort(open.bengin(),open.end().opensort())）改为 open.sort(opensort() )不过这时opensort要改为如下结构：
struct opensort: public binary_function
{
           bool operator () (const int& n1,const int& n2)const
           {
                    map::iterator pos1,pos2;
                   pos1 = gmap.find(n1);
                   pos2 = gmap.find(n2);
                  return pos1->second->fn < pos2->second->fn;
  
            }
};
这样，就没有问题了，哈哈，太好了，遇到问题，郁闷了一天，现在总算明白了

//#############################################################//

在这里谢谢一个朋友给的一个答复，他解释如下（其实不是这里的问题，但是他的答复让我知道了这个方法）：

Map是一个通过key（键）来获得value(值)的模板类。另一个问题是你希望在map中使用自己的类而不是已有的数据类型，比如现在已经用过 的int。建立一个“为模板准备的（template-ready）”类，你必须确保在该类中包含一些成员函数和重载操作符。下面的一些成员是必须的：
•缺省的构造函数（通常为空）
•拷贝构造函数
•重载的”=”运算符
你应该重载尽可能多的运算符来满足特定模板的需要，比如，如果你想定义一个类作为 map中的键（key），你必须重载相关的运算符。但在这里不对重载运算符做过多讨论了。
//程序：映射自定义的类。
//目的：说明在map中怎样使用自定义的类。
#include
#include
#include
#include

class CStudent
{
public:
      int nStudentID;
      int nAge;
public:
      CStudent(){}//缺省构造函数——通常为空
      //完整的构造函数
      CStudent(int nSID, int nA){ nStudentID=nSID; nAge=nA;}
      //拷贝构造函数
      CStudent(const CStudent& ob){ nStudentID=ob.nStudentID; nAge=ob.nAge;}
      // 重载“=”
      void operator = (const CStudent& ob){nStudentID=ob.nStudentID; nAge=ob.nAge;}
};

int main(int argc, char* argv[])
{
map mapStudent;
mapStudent["Joe Lennon"] = CStudent(103547, 22);
mapStudent["Phil McCartney"] = CStudent(100723, 22);
mapStudent["Raoul Starr"] = CStudent(107350, 24);
mapStudent["Gordon Hamilton"] = CStudent(102330, 22);
// 通过姓名来访问Cstudent类中的成员
cout <<"The Student number for Joe Lennon is "<<
(mapStudent["Joe Lennon"].nStudentID) << endl;
return 0;
}

/****************************************************************/
谢谢这位朋友，来自：