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

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é)點(diǎn)狀態(tài) int s33; /當(dāng)前8數(shù)碼的狀態(tài) int i_0; /當(dāng)前空格所在行號(hào) int j_0; /當(dāng)前空格所在列號(hào) int f; /當(dāng)前代價(jià)值 int d; /當(dāng)前節(jié)點(diǎn)深度 int h; /啟發(fā)信息，采用數(shù)

3、碼"不在位"距離和 struct node *father; /指向解路徑上該節(jié)點(diǎn)的父節(jié)點(diǎn) struct node *next; /指向所在open或closed表中的下一個(gè)元素 ;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; /定義目標(biāo)狀態(tài)struct node *open=NULL; /建立open表指針struct node *closed=NULL; /建立closed表指針int

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

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

6、_0-1=n->j_0) /新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)相同 ; else /新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)不同，或其父節(jié)點(diǎn)為起始節(jié)點(diǎn) temp=(struct node *)malloc(sizeof(struct node); /給新節(jié)點(diǎn)分配空間 Copy_node(n,temp); /拷貝n指向的節(jié)點(diǎn)狀態(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é)點(diǎn)的代價(jià)值 temp->father=n; /新節(jié)點(diǎn)指向其父節(jié)點(diǎn) if(same=Search_A(closed,temp) /在closed表中找到與新節(jié)點(diǎn)狀態(tài)相同的節(jié)點(diǎn) if(temp->f<same->f) /temp指向的節(jié)點(diǎn),其代價(jià)比closed表中相同狀態(tài)節(jié)點(diǎn)代價(jià)小，加入open表 Remove_p(closed,same); /從closed表中刪除與temp指向節(jié)點(diǎn)狀態(tài)相同的節(jié)點(diǎn) Add_to_open(temp); sum_node+; else; else if(same=Search_A

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

9、ther; if(temp!=NULL&&temp->i_0=n->i_0&&temp->j_0+1=n->j_0) /新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)相同 ; else /新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)不同，或其父節(jié)點(diǎn)為起始節(jié)點(diǎn) temp=(struct node *)malloc(sizeof(struct node); /給新節(jié)點(diǎn)分配空間 Copy_node(n,temp); /拷貝p指向的節(jié)點(diǎn)狀態(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é)點(diǎn)的代價(jià)值 temp->father=n; /新節(jié)點(diǎn)指向其父節(jié)點(diǎn) if(same=Search_A(closed,temp) /在closed表中找到與新節(jié)點(diǎn)狀態(tài)相同的節(jié)點(diǎn) if(temp->f<same->f) /temp指向的節(jié)點(diǎn),其代價(jià)比closed表中相同狀態(tài)節(jié)點(diǎn)代價(jià)小，加入open表 Remove_p(closed,same); /從closed表中刪除與te

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

12、p); sum_node+;/end右移 if(n->i_0>=1) /空格所在列號(hào)不小于1,上移 temp=n->father; if(temp!=NULL&&temp->i_0=n->i_0-1&&temp->j_0=n->j_0) /新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)相同 ; else /新節(jié)點(diǎn)與其祖父節(jié)點(diǎn)不同，或其父節(jié)點(diǎn)為起始節(jié)點(diǎn) temp=(struct node *)malloc(sizeof(struct node); /給新節(jié)點(diǎn)分配空間 Copy_node(n,temp); /拷貝p指向的節(jié)點(diǎn)狀態(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é)點(diǎn)的代價(jià)值 temp->father=n; /新節(jié)點(diǎn)指向其父節(jié)點(diǎn) if(same=Search_A(closed,temp) /在closed表中找到與新節(jié)點(diǎn)狀態(tài)相同的節(jié)點(diǎn) if(temp->f<same->f) /temp指向的節(jié)點(diǎn)

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

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

16、of(struct node); /給新節(jié)點(diǎn)分配空間 Copy_node(n,temp); /拷貝p指向的節(jié)點(diǎn)狀態(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é)點(diǎn)的代價(jià)值 temp->father=n; /新節(jié)點(diǎn)指向其父節(jié)點(diǎn) if(same=Search_A(closed,

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

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

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

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

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

22、中搜索和temp指向的節(jié)點(diǎn)相同的節(jié)點(diǎn) */* */*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é)點(diǎn)，返回該節(jié)點(diǎn)地址 return p1; else p1=p1->next; return NULL;/*/* */* 判斷兩個(gè)節(jié)點(diǎn)狀態(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é)點(diǎn) */* */*void Remove_p(struct node *name,struct node *p) struct node *p1,*p2; p1=NULL; p2=NULL; if(name=NULL) /如果name指向的鏈表為空

24、，則不需要進(jìn)行刪除 return; else if(Test_A_B(name,p)&&name->f=p->f) /指定節(jié)點(diǎn)為name指向的鏈表的第一個(gè)元素 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é)點(diǎn) p2->next=p1->next; return; else p2=p1; /p2始終指向p1指向的前一個(gè)元素 p1

25、=p1->next; return; /*/* */* 將p1指向的節(jié)點(diǎn)狀態(tài)拷貝到p2指向的節(jié)點(diǎn)中 */* */*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;/*/* */* 輸出結(jié)果 */* */*void Print_result(struct node *p) struct node *path100; struct node *temp,*temp_father; int i,