回 帖 发 新 帖 刷新版面

主题:[原创]A*算法, 学了人工智能,用她编的求迷宫最短路径的小程序

             人工智能作业



一、    程序目的:
通过编制迷宫程序来熟练掌握A*算法。充分理解A*算法和启发函数的关系。

二、A*算法梗概:
1.    OPEN:=(S),F(S):=G(S)+H(S);
2.    LOOP : IF OPEN-() THEN EXIT (FALL);
3.    N:=FIRST (OPEN);
4.    IF GOAL(N) THEN EXIT (SUCCESS);
5.    REMOVE (N,OPEN), ADD (N,CLOSED);
6.    EXPAND (N){Mi}, 计算F(N,Mi)=G(N,Mi)+H(Mj); G(N,M)是通过n到Mi的好散值的估计。ADD (Mj,OPEN),标记Mj到n的指针。IF  F(N,Mk)〈F(Mk) THEN  F(Mk):=F(N,Mk),标记Mk到n的指针;比较F(N,Mk)和F(Mk),F(Mk)是扩展前计算的耗散值。IF F(N,Ml)〈F(Ml) THEN F(Ml):=F(N,Ml),标记Ml到n的指针ADD (Ml,OPEN); 把Ml重新放回OPEN中,不必考虑修改到其中结点的指针。
7.    OPEN 中的结点按F值从大到小排序;
8.    GO LOOP;
调用函数说明:
1、
void AddClosed(struct Gather  *des)
des为struct Gather *类型的结点;
该函数的功能是将des结点加到CLOSED集合中,无返回值。
2、
void PartInit_Point(void)
无行参,无返回值。
该函数的功能是初始化Point P[]中的部分成员。
3、
void AddOpen(struct Point des)
行参为struct Point 类型,可以直接将P[i]作行参。
该函数的功能是将点des加到OPEN集合中。
4、
bool Goal(struct Gather *n)
行参为struct Gather *类型, 返回值为bool型。
该函数的功能是判断n是不是目标结点。是返回TRUE, 否返回FALSE;
5、
bool IsOpenEmpty(void)
返回值为bool型。OPEN集合为空,返回TRUE, 否则返回FALSE;
6、
void Remove(struct Gather *des)
des为struct Gather *类型的结点;
该函数的功能是将des从OPEN集合中删除。
7、
struct Gather *First(void)
返回struct Gather *类型的结点;
该函数的功能是取OPEN集合中存储的第一个有效结点。创建OPEN集合时,头结点未存有效结点。
8、
int InOPENorCLOSED(struct Point R)
返回值为int型,行参为struct Point类型。用法InOPENorCLOSED(P[i])
该函数的功能是判断点R在OPEN集合,或者CLOSED集合,或者都不在
在OPEN中,返回0
在CLOSED中,返回1
俱不在,返回2
9、
void Expand(struct Gather *curr)
无返回值,行参为struct Point类型
该函数的功能是扩展当前结点curr。
10、
void DrawMap(void)
画个草图。

三、源程序:
// C++编写, Visual Studio 6.0调试成功
#include <iostream>
using namespace std;
const int PointNum = 16; //迷宫点的总数
const int SideNum  = 18; //迷宫边的总数

struct Point
{
    int    x;        //横坐标
    int    y;        //纵坐标
    int    F;        //评价函数值
    int    H;        //当前点到目标点的横截距与纵截距之和
    int    D;        //深度
    int    index;    //点的编号
    int    pre;        //保存路径,作标志指针之用
};

struct Index
{
    int    from;        //边的起点
    int    to;            //边的终点   注:由于是无向图,from,to既是起点又是终点。
};

struct Gather
{
    struct Point     pnode;
    struct Gather    *next;
};

//存储点的信息 共PointNum个点
struct Point P[PointNum] = {
    {1,1,0,0,0,0, -1}, {1,2,0,0,0,1 ,-2}, {1,3,0,0,0,2 ,-2}, {1,4,0,0,0,3 ,-2},
    {2,1,0,0,0,4 ,-2}, {2,2,0,0,0,5 ,-2}, {2,3,0,0,0,6 ,-2}, {2,4,0,0,0,7 ,-2},
    {3,1,0,0,0,8 ,-2}, {3,2,0,0,0,9 ,-2}, {3,3,0,0,0,10,-2}, {3,4,0,0,0,11,-2},
    {4,1,0,0,0,12,-2}, {4,2,0,0,0,13,-2}, {4,3,0,0,0,14,-2}, {4,4,0,0,0,15,-2}
};

//存储边的信息 共SideNum个边
struct Index In[SideNum] = {
    {0, 1 }, {1, 2 }, {2, 6 }, {3, 7 }, {4 , 5 }, {4 , 8}, {5 , 6}, {5 ,9 },
    {6, 7 }, {7, 11}, {8, 9 }, {8, 12}, {9 , 10}, {10,11}, {10,14}, {12,13},
    {13,14}, {14,15}
};

//OPEN, CLOSED集合中头结点不存数据,且设OPEN, CLOSED为指针类型的常量
//确保OPEN, CLOSED两全局指针不被意外修改。
struct    Gather *const OPEN   = new struct Gather;
struct    Gather *const CLOSED = new struct Gather;

//将结点加到CLOSED集合中
void    AddClosed(struct Gather *des)
{    
    des->next = CLOSED->next;
    CLOSED->next = des;
}

//部分初始化    
void    PartInit_Point(void)
{
    for (int i=0; i<PointNum; i++){
        P[i].H = (4 - P[i].x) + (4 - P[i].y);
    }
    P[0].D = 0;
    P[0].F = P[0].H + P[0].D;
    OPEN->next = NULL;
    CLOSED->next = NULL;
}

//将点加到OPEN集合中,插入,确保OPEN集合中的点是按照F值由小到大排序的
void    AddOpen(struct Point des)
{
    struct Gather    *q = OPEN,
                *r = NULL,
                *temp = new struct Gather;
    temp->pnode = des;

    while ((q->next != NULL) && (q->next->pnode.F < des.F)){
        q = q->next;
    }
    r = q->next;        
    temp->next = r;
    q->next = temp;    
}

/////////////////////////////////////////////////////////////////////////
//判断是否到达终点, 到达则返回 True
bool    Goal(struct Gather *n)
{
    if (n->pnode.index == 15) //该迷宫(课本)的目标结点编号是15[自定义]
        return true;
    else
        return false;
}


//判断Open集合是不是为空, 空则返回 True
bool    IsOpenEmpty(void)
{
    if (OPEN->next == NULL)
        return true;
    else
        return false;
}

//将des结点从OPEN集合中删除
void    Remove(struct Gather *des)
{
    struct  Gather *p = OPEN, *q = NULL;
    while ((p->next!=NULL) && (p->next->pnode.index!=des->pnode.index)){
        p = p->next;
    }
    if (p->next == NULL)
        cout << "Error occurs when delete node from Open!" << endl;
    else
    {
        q = p->next;
        p->next = q->next;
    }
}

//取OPEN集合中存的第一个结点 [ 注意:OPEN头结点未存数据 ]
struct Gather  *First(void)
{
    return    OPEN->next;
}

//判断点R在OPEN,CLOSED集合中,还是都不在
int    InOPENorCLOSED(struct Point R)
{
    for (struct Gather *p = OPEN; p->next!=NULL; p = p->next){
            if (p->next->pnode.index == R.index) return 0;//在OPEN中                    
        }
    for (p = CLOSED; p->next!=NULL ;p = p->next){
            if (p->next->pnode.index == R.index) return 1;//在CLOSED中                    
        }
    return  2; //都不在
}

//扩展结点遇到的三种情况处理
void  Process(struct Point *A, struct Gather *curr)
{
    (*A).D++;
    (*A).F = (*A).D + (*A).H;
    if (InOPENorCLOSED(*A) == 2)  //如果A不在OPEN,CLOSED集合中
    {
        AddOpen(*A);  //将A加到OPEN集合中                    
        (*A).pre = curr->pnode.index;  //标志指针(游标)                                  
    }
    if (InOPENorCLOSED(*A) == 0)  //如果A在OPEN集合中
    {
        struct    Gather *r = OPEN;
        while ((r->next != NULL) && (r->next->pnode.index != (*A).index))
        {
            r = r->next;
        }
        if ((*A).F < r->next->pnode.F)
        {
            r->next->pnode.F = (*A).F;  //修改OPEN集合中结点A的F值
            (*A).pre = curr->pnode.index;  //标志指针(游标)    
        }
    }
    if (InOPENorCLOSED(*A) == 1)  //如果A在CLOSED集合中
    {
        struct    Gather *r = CLOSED;
        while ((r->next != NULL) && (r->next->pnode.index != (*A).index))
        {
            r = r->next;
        }
        if ((*A).F < r->next->pnode.F)
        {
            (*A).pre = curr->pnode.index;  //标志指针(游标)    
            AddOpen(*A);  //将A重新放到OPEN集合中
        }
    }            
}

//扩展当前结点curr
void    Expand(struct Gather *curr)
{
    for (int i=0; i<SideNum; i++)
    {
        if (In[i].from == curr->pnode.index)
        {
            int    t = In[i].to;            
            Process(&P[t], curr);            
        }
        //由于是无向图,可以由点from扩展到点to; 同样可以由点to扩展到点from
        if (In[i].to == curr->pnode.index)
        {
            int    t = In[i].from;
            Process(&P[t], curr);        
        }
    }//end for
}

//画课本上的迷宫图
void    DrawMap(void)
{
    cout    << "The labyrinth is : " << endl << endl;
    cout    << "     _______________@" << endl
            << "          |    |    |" << endl
            << "     _____|    |____|" << endl
            << "     |    |    |    |" << endl
            << "     |    |____|    |" << endl
            << "     |    |    |    |" << endl
            << "    .|    |____|____|" << endl
            << endl;
}

void main()
{
    DrawMap();
    PartInit_Point();    
    struct Gather  *n = new struct Gather;    
    AddOpen(P[0]);    
LOOP:
    if (IsOpenEmpty()){
        cout << "Fail for Open is Null!" << endl;
        exit(0);
    }
    n = First();    
    if (Goal(n)){
        cout << "Succeed! The shortest route is: " <<endl<<endl;        
        int  i = n->pnode.index;
        do  {
            cout << "(" << P[i].x << "," << P[i].y << ")" << "   ";
            i = P[i].pre;
        }while (P[i].pre != -1);
        cout << "(" << P[i].x << ", " << P[i].y << ")" << endl;
        exit(1);
    }    
    Remove(n);
    AddClosed(n);
    Expand(n);
    goto    LOOP;
}

回复列表 (共11个回复)

沙发

顶.

板凳

跟着顶一个,虽然没看帖

3 楼


我拷回去编译不通过,请教怎么了[em18]

4 楼

我正在学严的数据结构,那本书上关于迷宫那块光有算法的大体描述,却没有具体细节,一共就10行左右,搞的我很诧异,现在看到楼主这程序这么长我更差异了,怎么大小差别这么大呢

5 楼

[quote]顶.我就是程序,程序就是我[/quote]
嫩无敌了啊!![em1]

6 楼

我喜欢算法,谢谢楼主分享

7 楼

[quote]
我拷回去编译不通过,请教怎么了[em18][/quote]

What I did?
1) Fixed the compile problem, mostly non-standard C++ problems.
2) Made the running result can be seen in dev-c++
3) All Chinese comments are gone, since my dev-c++ made them questionmark "?"s. Sorry!

Problems I considered in the code:
1) Hard coded input and part of the output
2) Using goto

Since I am not familar with A* algorithm, and no desire to learn it for now. No comments on the algorithm. I did this just for somebody is interested to learn A*.

However, the code works now...Enjoy![em1][em1][em1]

8 楼

[code=c]
#include <iostream>
using namespace std;
const int PointNum = 16;
const int SideNum  = 18;

struct Point{
  int x;
  int y;
  int F;
  int H;
  int D;
  int index;
  int pre;
};
struct Index{
  int from;
  int to;
};
struct Gather{
  struct Point  pnode;
  struct Gather *next;
};
struct Point P[PointNum] = {
  {1,1,0,0,0,0, -1}, {1,2,0,0,0,1 ,-2}, {1,3,0,0,0,2 ,-2}, {1,4,0,0,0,3 ,-2},
  {2,1,0,0,0,4 ,-2}, {2,2,0,0,0,5 ,-2}, {2,3,0,0,0,6 ,-2}, {2,4,0,0,0,7 ,-2},
  {3,1,0,0,0,8 ,-2}, {3,2,0,0,0,9 ,-2}, {3,3,0,0,0,10,-2}, {3,4,0,0,0,11,-2},
  {4,1,0,0,0,12,-2}, {4,2,0,0,0,13,-2}, {4,3,0,0,0,14,-2}, {4,4,0,0,0,15,-2}
};
struct Index In[SideNum] = {
  {0, 1 }, {1, 2 }, {2, 6 }, {3, 7 }, {4 , 5 }, {4 , 8}, {5 , 6}, {5 ,9 },
  {6, 7 }, {7, 11}, {8, 9 }, {8, 12}, {9 , 10}, {10,11}, {10,14}, {12,13},
  {13,14}, {14,15}
};
struct Gather *const OPEN   = new struct Gather;
struct Gather *const CLOSED = new struct Gather;
void AddClosed(struct Gather *des){
  des->next = CLOSED->next;
  CLOSED->next = des;
}
void PartInit_Point(void){
  for (int i=0; i<PointNum; i++){
    P[i].H = (4 - P[i].x) + (4 - P[i].y);
  }
  P[0].D = 0;
  P[0].F = P[0].H + P[0].D;
  OPEN->next = NULL;
  CLOSED->next = NULL;
}
void AddOpen(struct Point des){
  struct Gather *q = OPEN, *r = NULL, *temp = new struct Gather;
  temp->pnode = des;

  while ((q->next != NULL) && (q->next->pnode.F < des.F)){
    q = q->next;
  }
  r = q->next;
  temp->next = r;
  q->next = temp;
}
bool Goal(struct Gather *n){
  return (n->pnode.index == 15);
}
bool IsOpenEmpty(void){
  return (OPEN->next == NULL);
}
void Remove(struct Gather *des){
  struct  Gather *p = OPEN, *q = NULL;
  while ((p->next!=NULL) && (p->next->pnode.index!=des->pnode.index)){
    p = p->next;
  }
  if (p->next == NULL)
    cout<<"Error occurs when delete node from Open!"<<endl;
  else{
    q = p->next;
    p->next = q->next;
  }
}
struct Gather *First(void){
  return OPEN->next;
}
int InOPENorCLOSED(struct Point R){
  struct Gather *p = NULL;
  for (p = OPEN; p->next!=NULL; p = p->next){
    if (p->next->pnode.index == R.index) return 0;
  }
  for (p = CLOSED; p->next!=NULL ;p = p->next){
    if (p->next->pnode.index == R.index) return 1;
  }
  return 2;
}
void  Process(struct Point *A, struct Gather *curr){
  (*A).D++;
  (*A).F = (*A).D + (*A).H;
  if (InOPENorCLOSED(*A) == 2){
    AddOpen(*A);
    (*A).pre = curr->pnode.index;
  }
  if (InOPENorCLOSED(*A) == 0){
    struct    Gather *r = OPEN;
    while ((r->next != NULL) && (r->next->pnode.index != (*A).index)) {
      r = r->next;
    }
    if ((*A).F < r->next->pnode.F){
      r->next->pnode.F = (*A).F;
      (*A).pre = curr->pnode.index;
    }
  }
  if (InOPENorCLOSED(*A) == 1){
    struct    Gather *r = CLOSED;
    while ((r->next != NULL) && (r->next->pnode.index != (*A).index)){
        r = r->next;
    }
    if ((*A).F < r->next->pnode.F){
        (*A).pre = curr->pnode.index;
        AddOpen(*A);
    }
  }
}
void Expand(struct Gather *curr) {
  for (int i=0; i<SideNum; i++) {
    if (In[i].from == curr->pnode.index) {
      int    t = In[i].to;
      Process(&P[t], curr);
    }
    if (In[i].to == curr->pnode.index) {
      int t = In[i].from;
      Process(&P[t], curr);
    }
  }
}
void DrawMap(void){
cout<<"The labyrinth is : "<<endl<<endl;
cout<<"     _______________@"<<endl
  <<"          |    |    |"<<endl
  <<"     _____|    |____|"<<endl
  <<"     |    |    |    |"<<endl
  <<"     |    |____|    |"<<endl
  <<"     |    |    |    |"<<endl
  <<"    .|    |____|____|"<<endl
  <<endl;
}
int main(){
  DrawMap();
  PartInit_Point();
  struct Gather  *n = new struct Gather;
  AddOpen(P[0]);
LOOP:
  if (IsOpenEmpty()){
    cout<<"Fail for Open is Null!"<<endl;
    exit(0);
  }
  n = First();
  if (Goal(n)){
    cout<<"Succeed! The shortest route is: " <<endl<<endl;
    int  i = n->pnode.index;
    do  {
      cout<<"("<<P[i].x<<","<<P[i].y<<")"<<"   ";
      i = P[i].pre;
    }while (P[i].pre != -1);
    cout<<"("<<P[i].x<<", "<<P[i].y<<")"<<endl;
    goto FINISH;
  }
  Remove(n);
  AddClosed(n);
  Expand(n);
  goto    LOOP;
FINISH:
  system("pause");
  return 0;
}
[/code]

9 楼

I had to eliminated many spaces to make a less than 5000 chars program to fit the 10000 limit of the forum.
Don't know why.
Sigh!

10 楼

马姐重出江湖啦~~~~~

我来回复

您尚未登录,请登录后再回复。点此登录或注册