第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
基于A星算法的8数码问题程序源代码.doc
#include "Stdio.h"
#include "Conio.h"
#include "stdlib.h"
#include "math.h"
void Copy_node(struct node *p1,struct node *p2);
void Calculate_f(int deepth,struct node *p);
void Add_to_open(struct node *p);
void Add_to_closed(struct node *p);
void Remove_p(struct node *name,struct node *p);
int Test_A_B(struct node *p1,struct node *p2);
struct node * Solution_Astar(struct node *p);
void Expand_n(struct node *p);
struct node * Search_A(struct node *name,struct node *temp);
void Print_result(struct node *p);
/* 定义 8 数码的节点状态 */
typedef struct node
{
int s[3][3]; //当前 8 数码的状态
//当前空格所在行号
int i_0;
//当前空格所在列号
int j_0;
int f;
//当前代价值
//当前节点深度
int d;
int h;
//启发信息，采用数码“不在位”距离和
struct node *father; //指向解路径上该节点的父节点
struct node *next;
//指向所在 open 或 closed 表中的下一个元素
};
struct node s_0={{3,8,2,1,0,5,7,6,4},1,1,0,0,0,NULL,NULL}; //定义初始状态
struct node s_g={{1,2,3,8,0,4,7,6,5},1,1,0,0,0,NULL,NULL}; //定义目标状态
struct node *open=NULL;
struct node *closed=NULL;
int sum_node=0;
//建立 open 表指针
//建立 closed 表指针
//用于记录扩展节点总数
int main(void)
{
struct node s,*target;
Copy_node(&s_0,&s);
Calculate_f(0,&s);
target=Solution_Astar(&s);
if(target) Print_result(target);
else printf("问题求解失败！");
//拷贝 8 数码初始状态，初始化代价值
//求解主程序
//输出解路径
getch();
return 0;
}
/******************************************/
/*
*/
/******************************************/
struct node * Solution_Astar(struct node *p)
{
A*算法
struct node *n,*temp;
Add_to_open(p);
while(open!=NULL)
//将 s_0 放入 open 表
//只要 open 表中还有元素，就继续对代价最小的节点进行扩展
{
}
n=open;
temp=open->next;
Add_to_closed(n);
open=temp;
if(Test_A_B(n,&s_g))
return n;
Expand_n(n);
return NULL;
//n 指向 open 表中当前要扩展的元素
//当前 n 指向节点为目标时，跳出程序结束；否则，继续下面的步骤
//扩展节点 n
生成当前节点 n 通过走步可以得到的所有状态
}
/*******************************************************/
/*
*/
/*******************************************************/
void Expand_n(struct node *p)
{
struct node *temp,*same;
if(p->j_0>=1)
//空格所在列号不小于 1,可左移
{
temp=p->father;
if(temp!=NULL&&temp->i_0==p->i_0&&temp->j_0-1==p->j_0)
//新节点与其祖父节点相同
;
else
{
//新节点与其祖父节点不同，或其父节点为起始节点
//给新节点分配空间
//空格左移
temp=(struct node *)malloc(sizeof(struct node));
Copy_node(p,temp);
//拷贝 p 指向的节点状态
temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0][temp->j_0-1];
temp->s[temp->i_0][temp->j_0-1]=0;
temp->j_0--;
temp->d++;
Calculate_f(temp->d,temp);
temp->father=p;
if(same=Search_A(closed,temp))
//修改新节点的代价值
//新节点指向其父节点
//在 closed 表中找到与新节点状态相同的节点
{
}
if(temp->ff)
//temp 指向的节点,其代价比 closed 表中相同状态节点代价小，加入 open 表
//从 closed 表中删除与 temp 指向节点状态相同的节点
Remove_p(closed,same);
Add_to_open(temp);
sum_node++;
{
}
else;
else if(same=Search_A(open,temp))
//在 open 表中找到与新节点状态相同的节点
{
}
else
{
}
}
}//end 左移
if(p->j_0<=1)
{
if(temp->ff)
//temp 指向的节点,其代价比 open 表中相同状态节点代价小，加入 open 表
//从 open 表中删除与 temp 指向节点状态相同的节点
{
Remove_p(open,same);
Add_to_open(temp);
sum_node++;
}
else ;
//新节点为完全不同的新节点，加入 open 表
Add_to_open(temp);
sum_node++;
//空格所在列号不大于 1,可右移
temp=p->father;
if(temp!=NULL&&temp->i_0==p->i_0&&temp->j_0+1==p->j_0)
//新节点与其祖父节点相同
;
else
{
//新节点与其祖父节点不同，或其父节点为起始节点
//给新节点分配空间
//空格右移
temp=(struct node *)malloc(sizeof(struct node));
Copy_node(p,temp);
//拷贝 p 指向的节点状态
temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0][temp->j_0+1];
temp->s[temp->i_0][temp->j_0+1]=0;
temp->j_0++;
temp->d++;
Calculate_f(temp->d,temp);
temp->father=p;
if(same=Search_A(closed,temp))
//修改新节点的代价值
//新节点指向其父节点
//在 closed 表中找到与新节点状态相同的节点
{
if(temp->ff)
//temp 指向的节点,其代价比 closed 表中相同状态节点代价小，加入 open 表
//从 closed 表中删除与 temp 指向节点状态相同的节点
Remove_p(closed,same);
Add_to_open(temp);
sum_node++;
{
}
else;
}
else if(same=Search_A(open,temp))
//在 open 表中找到与新节点状态相同的节点
{
}
else
{
if(temp->ff)
//temp 指向的节点,其代价比 open 表中相同状态节点代价小，加入 open 表
//从 open 表中删除与 temp 指向节点状态相同的节点
{
Remove_p(open,same);
Add_to_open(temp);
sum_node++;
}
else ;
//新节点为完全不同的新节点，加入 open 表
Add_to_open(temp);
sum_node++;
}
}
}//end 右移
if(p->i_0>=1)
{
//空格所在列号不小于 1,上移
temp=p->father;
if(temp!=NULL&&temp->i_0==p->i_0-1&&temp->j_0==p->j_0)
//新节点与其祖父节点相同
;
else
{
//新节点与其祖父节点不同，或其父节点为起始节点
//给新节点分配空间
//空格上移
temp=(struct node *)malloc(sizeof(struct node));
Copy_node(p,temp);
//拷贝 p 指向的节点状态
temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0-1][temp->j_0];
temp->s[temp->i_0-1][temp->j_0]=0;
temp->i_0--;
temp->d++;
Calculate_f(temp->d,temp);
temp->father=p;
if(same=Search_A(closed,temp))
//修改新节点的代价值
//新节点指向其父节点
//在 closed 表中找到与新节点状态相同的节点
{
if(temp->ff)
//temp 指向的节点,其代价比 closed 表中相同状态节点代价小，加入 open 表
{
Remove_p(closed,same);
//从 closed 表中删除与 temp 指向节点状态相同的节点
Add_to_open(temp);
sum_node++;
}
else;
}
else if(same=Search_A(open,temp))
//在 open 表中找到与新节点状态相同的节点
{
}
else
{
if(temp->ff)
//temp 指向的节点,其代价比 open 表中相同状态节点代价小，加入 open 表
//从 open 表中删除与 temp 指向节点状态相同的节点
{
Remove_p(open,same);
Add_to_open(temp);
sum_node++;
}
else ;
//新节点为完全不同的新节点，加入 open 表
Add_to_open(temp);
sum_node++;
}
}
}//end 上移
if(p->i_0<=1)
{
//空格所在列号不大于 1,下移
temp=p->father;
if(temp!=NULL&&temp->i_0==p->i_0+1&&temp->j_0==p->j_0)
//新节点与其祖父节点相同
;
else
{
//新节点与其祖父节点不同，或其父节点为起始节点
//给新节点分配空间
//空格下移
temp=(struct node *)malloc(sizeof(struct node));
Copy_node(p,temp);
//拷贝 p 指向的节点状态
temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0+1][temp->j_0];
temp->s[temp->i_0+1][temp->j_0]=0;
temp->i_0++;
temp->d++;
Calculate_f(temp->d,temp);
temp->father=p;
if(same=Search_A(closed,temp))
//修改新节点的代价值
//新节点指向其父节点
//在 closed 表中找到与新节点状态相同的节点
{
if(temp->ff)
//temp 指向的节点,其代价比 closed 表中相同状态节点代价小，加入 open 表
{
Remove_p(closed,same);
Add_to_open(temp);
sum_node++;
//从 closed 表中删除与 temp 指向节点状态相同的节点
}
else;
}
else if(same=Search_A(open,temp))
//在 open 表中找到与新节点状态相同的节点
{
}
else
{
if(temp->ff)
//temp 指向的节点,其代价比 open 表中相同状态节点代价小，加入 open 表
//从 open 表中删除与 temp 指向节点状态相同的节点
{
Remove_p(open,same);
Add_to_open(temp);
sum_node++;
}
else ;
//新节点为完全不同的新节点，加入 open 表
Add_to_open(temp);
sum_node++;
}
}
}//end 下移
}
/*******************************************************/
/*
*/
/*******************************************************/
void Add_to_open(struct node *p)
{
添加 p 指向的节点到 open 表中
struct node *p1,*p2;
p1=open;
p2=NULL;
if(open==NULL)
p->next=NULL;
open=p;
{
}
else
{
//初始时 p1 指向 open 表首部
//open 表为空时，待插入节点即为 open 表第一个元素，open 指向该元素
//open 表不为空时，添加待插入节点，并保证 open 表代价递增的排序
while(p1!=NULL&&p->f>p1->f)
{
}
p2=p1;
p1=p1->next;
//p2 始终指向 p1 指向的前一个元素
if(p2==NULL)
//待插入节点为当前 open 表最小
{
p->next=open;
open=p;
}
else if(p1==NULL)
//待插入节点为当前 open 表最大
p->next=NULL;
p2->next=p;
p2->next=p;
p->next=p1;
{
}
else
{
}
}
//待插入节点介于 p2、p1 之间
}
/*******************************************************/
/*
*/
/*******************************************************/
void Add_to_closed(struct node *p)
{
添加 p 指向的节点到 closed 表中
if(closed==NULL)
//closed 表为空时，p 指向节点为 closed 表第一个元素，closed 指向该元素
{
}
else
{
}
p->next=NULL;
closed=p;
p->next=closed;
closed=p;
//closed 表不为空时，直接放到 closed 表首部
}
/**************************************************************/
/* 在 open 表或 closed 表中搜索与 temp 指向节点状态相同的节点， */
/*
*/
/**************************************************************/
struct node * Search_A(struct node *name,struct node *temp)
{
返回搜索到的节点地址
struct node *p1;
p1=name;
while(p1!=NULL)
{
//p1 指向 open 表或 closed 表
if(Test_A_B(p1,temp))
//找到相同的节点，返回该节点地址
return p1;
else
p1=p1->next;
}
return NULL;
}
/**********************************************************/
/* 判断两个节点 A、B 状态是否相同，相同则返回 1，否则返回 0
/**********************************************************/
int Test_A_B(struct node *p1,struct node *p2)
{
*/
int i,j,flag;
flag=1;
for(i=0;i<=2;i++)
for(j=0;j<=2;j++)
{
}
if((p2->s[i][j])!=(p1->s[i][j])) { flag=0; return flag; }
else ;
return flag;
}
/*******************************************************/
/*
*/
/*******************************************************/
void Remove_p(struct node *name,struct node *p)
{
从 open 表或 closed 表删除指定节点
struct node *p1,*p2;
p1=NULL;
p2=NULL;
if(name==NULL)
return;
//如果 name 指向的链表为空，则不需要进行删除
else if(Test_A_B(name,p)&&name->f==p->f)
//指定节点为 name 指向的链表的第一个元素
{
}
else
{
open=name->next;
name->next=NULL;
return;
p2=name;
p1=p2->next;
while(p1)
{
if(Test_A_B(p1,p)&&p1->f==p->f)
//找到指定节点
{
p2->next=p1->next;
return;
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
