今天老师讲了图搜索算法,搞的我一头模糊,什么也听不懂.白白浪费了许多时间.现在我把这个程序放在这如果你会的话指导我一下啊.谢谢了
#include <stdio.h>
#include <math.h>
#define BOOL int
#define TRUE 1
#define FALSE 0
#define MAXN 80
struct node
{
int row;
int col;
struct node * parent;
struct node * next;
double g_value;
double f_value;
};
struct node *close, *open,*goal;
int m, n;
int succeed=0;
int map[MAXN][MAXN];
double heuristic( struct node *x)
{
/* 计算启发函数 */
double value;
value=(m-x->row)*(m-x->row)+(n-x->col)*(n-x->col);
value=sqrt(value);
return value;
}
BOOL pass(int x0, int y0, int x1, int y1)
{
int x,y;
int bef;
if ((x0==x1)||(y0==y1))
return TRUE; /*若在边上,则可通过*/
for(x=x0+1; x<=x1; ++x)
{
y=(x-x0)*(y1-y0)/(x1-x0)+y0;
if ((x-x0)*(y1-y0)%(x1-x0)!=0) y=y+1;
bef=(x-1-x0)*(y1-y0)/(x1-x0)+y0+1;
for (int j=bef; j<=y;++j)
if (map[x][j]) return FALSE;
}
return TRUE;
}
void search(struct node *x)
{
/*
将新扩展结点放入OPEN表中恰当位置,
该算法启发函数满足单调性,故不会出现重复扩展问题.
*/
struct node *p,*q;
if (open==NULL)
{
open=x;
x->next=NULL;
return;
}
if (open->f_value>=x->f_value)
{
x->next=open;
open=x;
p=x->next;
q=x;
}
else
{
p=open;
q=p;
while ((p!=NULL) && (p->f_value<x->f_value))
{
/*查找有比x值小的相同结点*/
if ((p->row==x->row)&&(p->col==x->col))
{
delete x;
return;
}
q=p;
p=p->next;
}
x->next=p;
q->next=x;
q=x;
}
/*继续查找有无与x相同的节点,有则删除该节点*/
while (p!=NULL)
{
if ((p->row==x->row)&&(p->col==x->col))
{
q->next=p->next;
delete p;
return;
}
q=p;
p=p->next;
}
}
void expend( )
{
/*从OPEN表中选取第一个结点进行扩展*/
struct node *p,*q;
while ((open!=NULL)&& (succeed==0))
{
p=open;
open=open->next;
p->next=close;
close=p;
/*测试是否是目标状态*/
if ((p->row==m)&&(p->col==n))
{
succeed=1;
goal=p;
}
else
/*对该节点进行扩展*/
for (int i=p->row;i<=m;++i)