《A星算法和深度优先.docx》由会员分享，可在线阅读，更多相关《A星算法和深度优先.docx（21页珍藏版）》请在三一办公上搜索。
1、A*算法程序public class Eightint g;int e = 2,8,3,1,6,4,7,0,5;int zi,zj; /0 的位置Eight former;public Eight()g=0;zi=-1;zj=-1;former=null;public Eight(Eight other)for(int i = 0; i3; i+)for(int j=0 ;j3; j+)eij = other.eij;zi=other.zi;zj=other.zj;former=other.former;public void setFormer(Eight e) this.former=e;
2、public void listAll( Eight e )System.out.println(最优路径为：);List l=new List();l.insertAtFront(e);while( e.former != null )l.insertAtFront(e.former);e = new Eight(e.former);while(!l.isEmpty()e=l.getFirstNode();e.print();l.removeFromFront();return ;public boolean equals(Eight a)int i=0;int j=0;if(a=null)
3、return false;else for( i = 0; i3; i+)for(j=0;j3; j+)if(a.eij != this.eij) return false;return true;public void Swap(int i,int j,int m,int n)int temp;temp = this.eij;this.eij = this.emn;this.emn = temp;public int h()int dest口口 = 1,2,3,8,0,4,7,6,5;int h =0,i,j;for(i=0;i3;i+)for(j=0;j3;j+)if(this.eij!=
4、destij & eij!=0) h+;return h;public int f()return g+h();public Eight ex()List e =new List(); int i=0,j=0,k=0; int m,n;boolean flag = true;for(i=0;i3&flag;i+)for(j=0;j=0)Eight a=new Eight(this);m=i-1;a.Swap(m,j,i,j);e.insertAtBack(a);+k;if(i+1=0)Eight a=new Eight(this);n=j-1;a.Swap(i,n,i,j);e.insertA
5、tBack(a);+k;if(j+13)Eight a=new Eight(this);n=j+1;a.Swap(i,n,i,j);e.insertAtBack(a);+k;Eight b=new Eightk;for(int x=0;xb.length;x+) bx=e.getFirstNode(); bx.setFormer(this);bx.g=this.g+1;e.removeFromFront();return b;static void sort(Eight a)(Eight temp;for(int i=0;ii;j-)if(aj.f()aj-1.f()temp=aj-1;aj-
6、1=aj;aj=temp;static void listSort(List l)Eight a=new Eightl.length;for(int i=0;ia.length;i+)ai=l.getFirstNode();l.removeFromFront();sort(a);for (int i=0;ia.length;i+)l.insertAtBack(ai);public boolean hasIt(List l)ListNode s=l.firstNode;boolean b=false;while(s!=null)if(this.equals(s.data)b=true;break
7、;s=s.next;return b;public void print()if(this!=null)for(int i=0;i3;i+)for(int j=0;j3;j+)System.out.print(eij);System.out.println();System.out.println(=);elsereturn; public static void main(String args)Eight e=new Eight();List open =new List();List closed =new List();open.insertAtBack(e);while(true)i
8、f(open.isEmpty()break;Eight a=open.getFirstNode();if (a.h()=0)e=a;break;open.removeFromFront();a.ex();closed.insertAtBack(a);for(int i=0;ia.ex().length;i+)if(!a.ex()i.hasIt(open) & !a.ex()i.hasIt(closed) open.insertAtBack(a.ex()i);listSort(open);e.listAll(e);System.out.println(open 表为：)； open.print(
9、);System.out.println(closed 表为：”)； closed.print();List代码是：class ListNodepublic Eight data;public ListNode next;public ListNode()next=null;public ListNode(Eight o)data=o;next=null;public ListNode(Eight o,ListNode nextNode)data=o;next=nextNode;/ Return the Eight in this nodepublic Eight getEight()retu
10、rn data;public ListNode getnext()return next;public class Listpublic ListNode firstNode;public ListNode lastNode;public int length;private String name;/ String like list used inprintingpublic List(String s)name=s;firstNode=lastNode=null;length=0;/Constructor: Constructor an empty List with List as t
11、he namepublic List()this(list);public Eight getFirstNode()return firstNode.data;/Insert an Eight at the front of the List If List is empty, firstNode/and lastNode refer to same Eight. Otherwise,firstNode refers to new node.public void insertAtFront(Eight insertItem)if(isEmpty()/如果链表为空，返回true,否则返回fal
12、se.firstNode=lastNode=new ListNode(insertltem);elsefirstNode=new ListNode(insertItem,firstNode);length+;/Insert an Eight at the end of the List If List is empty, firstNode and/lastNode refer to same Eight. Otherwise, lastNodes next instance variable refers to new node.public void insertAtBack(Eight
13、insertitem)if(isEmpty()firstNode=lastNode=new ListNode(insertItem);elselastNode=lastNode.next=new ListNode(insertItem);length+;/ Remove the first node from the List.public Eight removeFromFront() throws EmptyListExceptionEight removeItem=null;if(isEmpty()throw new EmptyListException(name);removeItem
14、=firstNode.data; /retrieve the data reset the firstNode and lastNode referencesif(firstNode.equals(lastNode)firstNode=lastNode=null;elsefirstNode=firstNode.next;length-;return removeItem;/Remove the last node from the Listpublic Eight removeFromBack() throws EmptyListExceptionEight removeItem=null;i
15、f(isEmpty()throw new EmptyListException(name);removeItem=lastNode.data; /retrieve the data reset thefirstNode and lastNode referencesif(firstNode.equals(lastNode)firstNode=lastNode=null;elseListNode current=firstNode;while(current.next !=lastNode)current=current.next;lastNode=current;current.next=nu
16、ll;length-;return removeItem;/Return true if the List is empty.public boolean isEmpty()(return firstNode=null;/Output the List contentspublic void print()if(isEmpty()(System.out.println(Empty );return;ListNode current=firstNode;docurrent.data.print();System.out.println(f :+currentdata.f();System.out
17、.println(=);current=current.next;while(current !=null);/ Class EmptyListException definitionclass EmptyListException extends RuntimeExceptionpublic EmptyListException(String name)super(The + name + is empty);程 序 截图如 下深度优先算法#include #include iostream.h#include stdio.h#include stdlib.h#include time.h#
18、include string.h#include #include using namespace std;const int N = 3;/3*3 图enum DirectionNone,Up,Down,Left,Right;/ 方向static int n=0;struct Map/图int cellNN;/ 数码数组Direction BelockDirec;/ 所屏蔽方向int step;struct Map * Parent;/ 父节点;/打印图void PrintMap(struct Map *map)cout*endl;for(int i=0;iN;i+)for(int j=0;
19、jN;j+)coutcellij” ”;coutendl;cout*endl;/移动图struct Map * MoveMap(struct Map * map,Direction Direct,bool CreateNewMap) struct Map * NewMap;/获取空闲格位置int i,j;for(i = 0; i N; i+)bool HasGetBlankCell = false;for(j = 0; j cellij = 0)HasGetBlankCell = true;break;if(HasGetBlankCell)break;/移动数字int t_i = i,t_j
20、= j;bool AbleMove = true;switch(Direct)/判断沿direct所指方向移动数字是否被允许case Down:t_i+;if(t_i = N)AbleMove=false;break;case Up:t_i-;if(t_i 0)AbleMove=false;break;case Left:t_j-;if(t_j = N)AbleMove=false;break;if(!AbleMove)/不可以移动则返回原节点 return map;if(CreateNewMap)NewMap = new Map();for(int x = 0; x N; x+)for(in
21、t y = 0; y cellxy = map-cellxy;else NewMap = map;NewMap-cellij = NewMap-cellt_it_j;NewMap-cellt_it_j = 0;return NewMap;/初始化一个初始图/由目标图生成初始图，保证可以获得结果struct Map * RandomMap(const struct Map * map)int M = 30;/随机移动图步数struct Map * NewMap;NewMap = new Map();memcpy(NewMap,map,sizeof(Map);srand(unsigned)time
22、(NULL);for(int i = 0; i M; i+)int Direct = rand()%4;NewMap = MoveMap(NewMap,(Direction)Direct,false);return NewMap;初始图的另种生成方式，随机生成各位置的数此方式生成的图在有限次搜索中若深度超过5则多数无解struct Map * RandomMap()int a9;struct Map * NewMap;NewMap = new Map();srand(unsigned)time(NULL);for(int k = 0; k 9; k+)bool Isre = false;ak
23、= rand()%9;for (int l = 0; l k; l+)if (ak = al)Isre = true;break;if(Isre)k = k - 1;continue;for(int i = 0; i N; i+)for (int j = 0; j cellij = ai*3+j;NewMap-Parent = NULL;NewMap-BelockDirec = None;return NewMap;判断是否搜索成功bool IsSuccess(struct Map * map,struct Map * Target)bool IsSuc = true;for(int i =
24、0; i N; i+)for(int j = 0; j cellij != Target-cellij)IsSuc = false;break;if(!IsSuc)break;return IsSuc;struct Map * DNF_Search(struct Map * begin,struct Map * Target,int dm) struct Map * p1, *p2,*T=NULL;stack OPEN;stack CLOSED;OPEN.push(begin);dop1=OPENtop();OPEN.pop();if(IsSuccess(p1,Target)T=p1;retu
25、rn T;if(p1-step=dm)CLOSEDpush(p1);continue;for (int i = 1; i BelockDirec)/ 跳过屏蔽方向continue;p2 = MoveMap(p1,Direct,true);if(p2 != p1)/数码是否可以移动p2-Parent = p1;p2-step = p1-step + 1;switch(Direct)/设置屏蔽方向，防止往回推case Up:p2-BelockDirec = Down;break;case Down:p2-BelockDirec = Up;break;case Left:p2-BelockDirec
26、 = Right;break;case Right:p2-BelockDirec = Left;break;OPEN.push(p2);n+;while(!OPEN.empty();return T;void main()Map Target;Map *begin,*T;int step=1;/设定目标图1 2 3,8 0 4,7 6 5Target.cell00 = 1;Target.cell01 = 2;Target.cell02 = 3;Target.cell10 = 8;Target.cell11 = 0;Target.cell12 = 4;Target.cell20 = 7;Targ
27、et.cell21 = 6;Target.cell22 = 5;Target.step = 0;/*begin = new Map();begin-cell00 = 2;begin-cell01 = 8;begin-cell02 = 3;begin-cell10 = 1;begin-cell11 = 0;begin-cell12 = 4;begin-cell20 = 7;begin-cell21 = 6;begin-cell22 = 5;Target.step = 0;*/begin = RandomMap();/ begin = RandomMap(&Target);begin-cell00
28、=6;begin-cell01=3;begin-cell02=2;begin-cell10=1;begin-cell11=4;begin-cell12=8;begin-cell20=7;begin-cell21=5;begin-cell22=0;/* begin-cell00=2;begin-cell01=1;begin-cell02=6;begin-cell10=4;begin-cell11=0;begin-cell12=8;begin-cell20=7;begin-cell21=5;begin-cell22=3;*/begin = RandomMap(&Target);begin-Pare
29、nt = NULL;begin-BelockDirec = None;begin-step = 0;cout目标图:endl;PrintMap(&Target);cout ”起始图:endl;PrintMap(begin);/图搜索int dm;/搜索路劲深度coutdm;T=DNF_Search(begin,&Target,dm);/打印if(T != NULL)把路径倒序Map *p=T;stack Stackl;while(p-Parent != NULL)Stack1.push(p);p = p-Parent;StackLpush(begin);cout搜索结果:endl;while(!Stack1.empty()cout第step+步：endl;PrintMap(Stack1.top();Stack1.pop();coutn 完成!;cout生成节点的个数：nendl;else cout达到了指定的搜索路径长度未搜到目标input;程序截图如下：串1涉134A 82765，* 部17步：第2S步,弟21步,
