mpboat.c

启发式A*算法解决传教士野人渡河问题！！！

/////////////////
//yuanchuan编写//
/////////////////
#include <stdio.h>
#include <stdlib.h>

#define MAXM 10
#define MAXC 5

typedef struct mc_state {
       int m_num;
       int c_num;
       int boat_state;
       int g;       
       int h;
       int f;
       struct mc_state *next;
       struct mc_state *parent;
       }mc_state;

mc_state *open;
mc_state *close;

mc_state boat[8]={{0,1,1,0,0,0,NULL,NULL},
                  {0,2,1,0,0,0,NULL,NULL},
                  {0,3,1,0,0,0,NULL,NULL},
                  {1,0,1,0,0,0,NULL,NULL},
                  {1,1,1,0,0,0,NULL,NULL},
                  {2,0,1,0,0,0,NULL,NULL},
                  {2,1,1,0,0,0,NULL,NULL},
                  {3,0,1,0,0,0,NULL,NULL}
                  };
/*建立一个新的状态结点*/
mc_state * new_mc_state(void)
{
    mc_state *p;
    p=(struct mc_state *)malloc(sizeof(struct mc_state));
    p->m_num=0;
    p->c_num=0;
    p->boat_state=1;
    p->g=0;
    p->h=0;
    p->f=0;
    p->next=NULL;
    p->parent=NULL;
}
/*显示open表,close表状态*/ 
int show(mc_state *p)
{   
    if(p==NULL)
    {
        printf("空表,没有元素!");
    }
    while(p!=NULL)
    {
        printf("( %d %d %d f=%d )\n",p->m_num,p->c_num,p->boat_state,p->f);
        p=p->next;
    }
    
}
/*判断是否存在于open或closed表中*/        
int exist(mc_state *p,mc_state *head)
{
    mc_state *q,*prior;
    q=head;
    if (q==NULL)
    {
        return 0;
    }
    else
    {
        while( q!=NULL)
        {
            if( (p->m_num == q->m_num) &&
                (p->c_num == q->c_num) &&
                (p->boat_state == q->boat_state))
            {
                return 1;
            }
            q=q->next;
        }
    return 0;
     }
}
     
/*open表添加*/ 
int add_open(mc_state *p)
{
    mc_state *q,*r;
    q=open;
    
    if (q==NULL)
    {
        open = p;
    }
    else 
    {   
        if( p->f <= q->f )
        {
            p->next = open;
            open = p;
        }
        else
        {
            r=q;
        
            while(q!=NULL && q->f < p->f)
            {
                r=q;
                q=q->next;
            }   
            q=r->next;
            r->next=p;
            p->next=q;
         }      
    }
    return 1;
}
/*open表删除*/ 
mc_state * del_open( )
{   
    mc_state *p;
    if(open==NULL)
    {
        return NULL;
    }
    else
    {
        p=open;
        open = p ->next;
        return p;
    }
}

/*close表添加*/ 
int add_close(mc_state *p)
{
    if(close==NULL)
    {
        close=p;
    }
    else
    {
        p->next=close;
        close=p;
    }
    return 1;
}
/*启发函数*/ 
int h(mc_state *p)
{
    return p->m_num+p->c_num-2*p->boat_state;
}
/*判断状态是否合法*/ 
int is_mc_state(mc_state *p)
{
    if ((p->m_num>MAXM)||
        (p->m_num<0)||
        (p->c_num>MAXC)||
        (p->c_num<0)) 
    {
        return 0;
    }
    else
    {   
        /*
        if ((p-> m_num==MAXM) ||
            (p-> m_num==0) ||
            (p-> m_num==p->c_num)) 
        {
            return 1;
        }
        */
        if (((p->m_num>=p->c_num)&&
             (MAXM - p->m_num >= MAXC - p->c_num)
             )||
            (p-> m_num==MAXM) ||
            (p-> m_num==0))
        {
            return 1;
        }
    }
    return 0;
}
        
/*扩展一个结点*/         
int expand(mc_state *p)
{
    mc_state *q,*r;
    char c;
    int i;
    r=del_open();
    printf("扩展:");
    printf("( %d %d %d )\n",p->m_num,p->c_num,p->boat_state);
    for(i=0;i<8;i++)
    {   
        q=new_mc_state();   
        if( p->boat_state  == 1)
        {
            q->m_num = p->m_num - boat[i].m_num;
            q->c_num = p->c_num - boat[i].c_num;
            q->boat_state=p->boat_state - boat[i].boat_state;
        }
        else
        {
            q->m_num = p->m_num + boat[i].m_num;
            q->c_num = p->c_num + boat[i].c_num;
            q->boat_state=p->boat_state + boat[i].boat_state;
        }
        
        q->g=p->g+1;
        q->h=h(q);
        q->f=q->g+q->h;
        q->parent=p;
        
       
        if (is_mc_state(q) &&
            (exist(q,open)==0) &&
            (exist(q,close)==0)) 
            
        {   
            printf("增加一个新状态:");
            printf("( %d %d %d )\n",q->m_num,q->c_num,q->boat_state);  
            add_open(q);
            /*open表中结点*/ 
            printf("----------OPEN----------------\n");
            show(open);
            printf("----------OPENEND-------------\n");
           // system("PAUSE");               
        }
        else
        {
            free(q);
        }
        
    }
    add_close(r);
    /*close表中的状态*/ 
    printf("----------CLOSED----------------\n");
    show(close);
    printf("----------CLOSEDEND-------------\n");
}
/*判断结点是目标状态吗?*/ 
int goal(mc_state *p)
{  
    if (p==NULL) 
    {
        return 0;
    }
    
    if ((p->m_num==0) &&
        (p->c_num==0) &&
        (p->boat_state==0))
    {   
        //printf("wuluke\n");
        return 1;
    }
    else
    {   
        
        return 0;
    }
}
/*解决mc问题函数*/ 
mc_state *mcp()
{    
     char c;
     mc_state *p;
     p=open;  
     while (p!=NULL)
     {
         
           
         if (goal(p)==1)
         {     
             return p;
         }
         else
         {   
             expand(p);
             
             //c=getchar();
         }
         p=open;
         
     }
     return NULL;
}    
/*得到最终状态后，显示状态转换路径*/   
int path(mc_state *p)
{
     printf("野人渡河问题的一个解:\n");
     mc_state *q;
     if (p==NULL) 
     {
         return 0;
     }
     else
     {  
        q=p;
        while(q!=NULL)
        {
            printf("( %d %d %d )\n",q->m_num,q->c_num,q->boat_state);
            q=q->parent;
        }
        return 1;
    }
}
                  

/*主程序*/ 
int main(int argc, char *argv[])
{ 
  mc_state *p;
  mc_state *q;
  /*初始状态*/ 
  p=new_mc_state( );
  p->m_num = MAXM;
  p->c_num = MAXC;
  p->boat_state = 1;
  p->g=0;
  p->h= h(p);
  p->f= p->g+p->h;
  /*open表只有一个状态*/ 
  open = p;
  printf("----------OPEN----------------\n");
  show(open);
  printf("----------OPENEND-------------\n");
  printf("----------CLOSED----------------\n");
  show(close);
  printf("----------CLOSEDEND-------------\n");
  q=mcp();
  if (q==NULL) //then
  {
    printf("该问题没有解决!\n");
  }
  else
  {        
    path(q);
  }
  system("PAUSE");	
  return 0;
}