人工智能A星算法解決八數(shù)碼難題程序代碼(共13頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上#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(s

2、truct node *name,struct node *p);int Test_A_B(struct node *p1,struct node *p2);struct node * Search_A(struct node *name,struct node *temp);void Print_result(struct node *p);struct node / 定義8數(shù)碼的節(jié)點狀態(tài) int s33; /當前8數(shù)碼的狀態(tài) int i_0; /當前空格所在行號 int j_0; /當前空格所在列號 int f; /當前代價值 int d; /當前節(jié)點深度 int h; /啟發(fā)信息，采用數(shù)

3、碼"不在位"距離和 struct node *father; /指向解路徑上該節(jié)點的父節(jié)點 struct node *next; /指向所在open或closed表中的下一個元素 ;struct node s_0=2,8,3,1,6,4,7,0,5,2,1,0,0,0,NULL,NULL; /定義初始狀態(tài)struct node s_g=1,2,3,8,0,4,7,6,5,1,1,0,0,0,NULL,NULL; /定義目標狀態(tài)struct node *open=NULL; /建立open表指針struct node *closed=NULL; /建立closed表指針int

4、 sum_node=0; /用于記錄擴展節(jié)點總數(shù)/*/* */* 主函數(shù)開始 */* */*void main() int bingo=0; /定義查找成功標志，bingo=1，成功 struct node s; /定義頭結點s struct node *target,*n,*ls,*temp,*same; /定義結構體指針 Copy_node(&s_0,&s); /復制初始狀s_0態(tài)給頭結點s Calculate_f(0,&s); /計算頭結點的代價值 Add_to_open(&s); /將頭結點s放入open表 while(open!=NULL) /只要op

5、en表不為空，進行以下循環(huán) n=open; /n指向open表中當前要擴展的元素 ls=open->next; Add_to_closed(n); open=ls; /將n指向的節(jié)點放入closed表中 if(Test_A_B(n,&s_g) /當前n指向節(jié)點為目標時，跳出程序結束；否則，繼續(xù)下面的步驟 bingo=1; break; elseif(n->j_0>=1) /空格所在列號不小于1,可左移 temp=n->father; if(temp!=NULL&&temp->i_0=n->i_0&&temp->j

6、_0-1=n->j_0) /新節(jié)點與其祖父節(jié)點相同 ; else /新節(jié)點與其祖父節(jié)點不同，或其父節(jié)點為起始節(jié)點 temp=(struct node *)malloc(sizeof(struct node); /給新節(jié)點分配空間 Copy_node(n,temp); /拷貝n指向的節(jié)點狀態(tài) temp->stemp->i_0temp->j_0=temp->stemp->i_0temp->j_0-1; /空格左移 temp->stemp->i_0temp->j_0-1=0; temp->j_0-; temp->d+; Calc

7、ulate_f(temp->d,temp); /修改新節(jié)點的代價值 temp->father=n; /新節(jié)點指向其父節(jié)點 if(same=Search_A(closed,temp) /在closed表中找到與新節(jié)點狀態(tài)相同的節(jié)點 if(temp->f<same->f) /temp指向的節(jié)點,其代價比closed表中相同狀態(tài)節(jié)點代價小，加入open表 Remove_p(closed,same); /從closed表中刪除與temp指向節(jié)點狀態(tài)相同的節(jié)點 Add_to_open(temp); sum_node+; else; else if(same=Search_A

8、(open,temp) /在open表中找到與新節(jié)點狀態(tài)相同的節(jié)點 if(temp->f<same->f) /temp指向的節(jié)點,其代價比open表中相同狀態(tài)節(jié)點代價小，加入open表 Remove_p(open,same); /從open表中刪除與temp指向節(jié)點狀態(tài)相同的節(jié)點 Add_to_open(temp); sum_node+; else ; else /新節(jié)點為完全不同的新節(jié)點，加入open表 Add_to_open(temp); sum_node+; /end左移 if(n->j_0<=1) /空格所在列號不大于1,可右移 temp=n->fa

9、ther; if(temp!=NULL&&temp->i_0=n->i_0&&temp->j_0+1=n->j_0) /新節(jié)點與其祖父節(jié)點相同 ; else /新節(jié)點與其祖父節(jié)點不同，或其父節(jié)點為起始節(jié)點 temp=(struct node *)malloc(sizeof(struct node); /給新節(jié)點分配空間 Copy_node(n,temp); /拷貝p指向的節(jié)點狀態(tài) temp->stemp->i_0temp->j_0=temp->stemp->i_0temp->j_0+1; /空格右移 t

10、emp->stemp->i_0temp->j_0+1=0; temp->j_0+; temp->d+; Calculate_f(temp->d,temp); /修改新節(jié)點的代價值 temp->father=n; /新節(jié)點指向其父節(jié)點 if(same=Search_A(closed,temp) /在closed表中找到與新節(jié)點狀態(tài)相同的節(jié)點 if(temp->f<same->f) /temp指向的節(jié)點,其代價比closed表中相同狀態(tài)節(jié)點代價小，加入open表 Remove_p(closed,same); /從closed表中刪除與te

11、mp指向節(jié)點狀態(tài)相同的節(jié)點 Add_to_open(temp); sum_node+; else; else if(same=Search_A(open,temp) /在open表中找到與新節(jié)點狀態(tài)相同的節(jié)點 if(temp->f<same->f) /temp指向的節(jié)點,其代價比open表中相同狀態(tài)節(jié)點代價小，加入open表 Remove_p(open,same); /從open表中刪除與temp指向節(jié)點狀態(tài)相同的節(jié)點 Add_to_open(temp); sum_node+; else ; else /新節(jié)點為完全不同的新節(jié)點，加入open表 Add_to_open(tem

12、p); sum_node+;/end右移 if(n->i_0>=1) /空格所在列號不小于1,上移 temp=n->father; if(temp!=NULL&&temp->i_0=n->i_0-1&&temp->j_0=n->j_0) /新節(jié)點與其祖父節(jié)點相同 ; else /新節(jié)點與其祖父節(jié)點不同，或其父節(jié)點為起始節(jié)點 temp=(struct node *)malloc(sizeof(struct node); /給新節(jié)點分配空間 Copy_node(n,temp); /拷貝p指向的節(jié)點狀態(tài) temp->st

13、emp->i_0temp->j_0=temp->stemp->i_0-1temp->j_0; /空格上移 temp->stemp->i_0-1temp->j_0=0; temp->i_0-; temp->d+; Calculate_f(temp->d,temp); /修改新節(jié)點的代價值 temp->father=n; /新節(jié)點指向其父節(jié)點 if(same=Search_A(closed,temp) /在closed表中找到與新節(jié)點狀態(tài)相同的節(jié)點 if(temp->f<same->f) /temp指向的節(jié)點

14、,其代價比closed表中相同狀態(tài)節(jié)點代價小，加入open表 Remove_p(closed,same); /從closed表中刪除與temp指向節(jié)點狀態(tài)相同的節(jié)點 Add_to_open(temp); sum_node+; else; else if(same=Search_A(open,temp) /在open表中找到與新節(jié)點狀態(tài)相同的節(jié)點 if(temp->f<same->f) /temp指向的節(jié)點,其代價比open表中相同狀態(tài)節(jié)點代價小，加入open表 Remove_p(open,same); /從open表中刪除與temp指向節(jié)點狀態(tài)相同的節(jié)點 Add_to_ope

15、n(temp); sum_node+; else ; else /新節(jié)點為完全不同的新節(jié)點，加入open表 Add_to_open(temp); sum_node+;/end上移 if(n->i_0<=1) /空格所在列號不大于1,下移 temp=n->father; if(temp!=NULL&&temp->i_0=n->i_0+1&&temp->j_0=n->j_0) /新節(jié)點與其祖父節(jié)點相同 ; else /新節(jié)點與其祖父節(jié)點不同，或其父節(jié)點為起始節(jié)點 temp=(struct node *)malloc(size

16、of(struct node); /給新節(jié)點分配空間 Copy_node(n,temp); /拷貝p指向的節(jié)點狀態(tài) temp->stemp->i_0temp->j_0=temp->stemp->i_0+1temp->j_0; /空格下移 temp->stemp->i_0+1temp->j_0=0; temp->i_0+; temp->d+; Calculate_f(temp->d,temp); /修改新節(jié)點的代價值 temp->father=n; /新節(jié)點指向其父節(jié)點 if(same=Search_A(closed,

17、temp) /在closed表中找到與新節(jié)點狀態(tài)相同的節(jié)點 if(temp->f<same->f) /temp指向的節(jié)點,其代價比closed表中相同狀態(tài)節(jié)點代價小，加入open表 Remove_p(closed,same); /從closed表中刪除與temp指向節(jié)點狀態(tài)相同的節(jié)點 Add_to_open(temp); sum_node+; else; else if(same=Search_A(open,temp) /在open表中找到與新節(jié)點狀態(tài)相同的節(jié)點 if(temp->f<same->f) /temp指向的節(jié)點,其代價比open表中相同狀態(tài)節(jié)點代

18、價小，加入open表 Remove_p(open,same); /從open表中刪除與temp指向節(jié)點狀態(tài)相同的節(jié)點 Add_to_open(temp); sum_node+; else ; else /新節(jié)點為完全不同的新節(jié)點，加入open表 Add_to_open(temp); sum_node+; /end下移 if(bingo=1) Print_result(n); /輸出解路徑 else printf("問題求解失敗！");/主函數(shù)結束/*/* */* 計算某個節(jié)點狀態(tài)的代價值 */* */*void Calculate_f(int deepth,struct n

19、ode *p) int i,j,temp; temp=0; for(i=0;i<=2;i+) /計算所有"不在位"數(shù)碼的距離和 for(j=0;j<=2;j+) if(p->sij)!=(s_g.sij) temp+; p->h=temp; p->f=deepth+p->h;/*/* */* 添加p指向的節(jié)點到open表中 */* */* void Add_to_open(struct node *p) struct node *p1,*p2; p1=open; /初始時p1指向open表首部 p2=NULL; if(open=NULL)

20、 /open表為空時，待插入節(jié)點即為open表第一個元素，open指向該元素 p->next=NULL; open=p; else /open表不為空時，添加待插入節(jié)點，并保證open表代價遞增的排序 while(p1!=NULL&&p->f>p1->f) p2=p1; /p2始終指向p1指向的前一個元素 p1=p1->next; if(p2=NULL) /待插入節(jié)點為當前open表最小 p->next=open; open=p; else if(p1=NULL) /待插入節(jié)點為當前open表最大 p->next=NULL; p2-&g

21、t;next=p; else /待插入節(jié)點介于p2、p1之間 p2->next=p; p->next=p1; /*/* */* 添加p指向的節(jié)點到closed表中 */* */*void Add_to_closed(struct node *p) if(closed=NULL) /closed表為空時，p指向節(jié)點為closed表第一個元素，closed指向該元素 p->next=NULL; closed=p; else /closed表不為空時，直接放到closed表首部 p->next=closed; closed=p; /*/* */* 在open表或closed表

22、中搜索和temp指向的節(jié)點相同的節(jié)點 */* */*struct node * Search_A(struct node *name,struct node *temp) struct node *p1; p1=name; /p1指向open表或closed表 while(p1!=NULL) if(Test_A_B(p1,temp) /找到相同的節(jié)點，返回該節(jié)點地址 return p1; else p1=p1->next; return NULL;/*/* */* 判斷兩個節(jié)點狀態(tài)是否相同，相同則返回1，否則返回0 */* */*int Test_A_B(struct node *p1,

23、struct node *p2) int i,j,flag; flag=1; for(i=0;i<=2;i+) for(j=0;j<=2;j+) if(p2->sij)!=(p1->sij) flag=0; return flag; else ; return flag;/*/* */* 從open表或closed表刪除指定節(jié)點 */* */*void Remove_p(struct node *name,struct node *p) struct node *p1,*p2; p1=NULL; p2=NULL; if(name=NULL) /如果name指向的鏈表為空

24、，則不需要進行刪除 return; else if(Test_A_B(name,p)&&name->f=p->f) /指定節(jié)點為name指向的鏈表的第一個元素 open=name->next; name->next=NULL; return; else p2=name; p1=p2->next; while(p1) if(Test_A_B(p1,p)&&p1->f=p->f) /找到指定節(jié)點 p2->next=p1->next; return; else p2=p1; /p2始終指向p1指向的前一個元素 p1

25、=p1->next; return; /*/* */* 將p1指向的節(jié)點狀態(tài)拷貝到p2指向的節(jié)點中 */* */*void Copy_node(struct node *p1,struct node *p2) int i,j; for(i=0;i<=2;i+) for(j=0;j<=2;j+) p2->sij=p1->sij; p2->i_0=p1->i_0; p2->j_0=p1->j_0; p2->f=p1->f; p2->d=p1->d; p2->h=p1->h; p2->next=p1->next; p2->father=p1->father;/*/* */* 輸出結果 */* */*void Print_result(struct node *p) struct node *path100; struct node *temp,*temp_father; int i,