A星算法和深度优先.docx

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; 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) 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!=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.insertAtBack(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-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; 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(=); else return; public static void main(String args) Eight e=new Eight(); List open =new List(); List closed =new List(); open.insertAtBack(e); while(true) if(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(); System.out.println(closed表为：); closed.print(); List 代码是：class ListNode public 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 node public Eight getEight() return data; public ListNode getnext() return next; public class List public ListNode firstNode; public ListNode lastNode; public int length; private String name; / String like list used in printing public List(String s) name=s; firstNode=lastNode=null; length=0; /Constructor: Constructor an empty List with List as the name public 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,否则返回false. firstNode=lastNode=new ListNode(insertItem); else firstNode=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 insertItem) if(isEmpty() firstNode=lastNode=new ListNode(insertItem); else lastNode=lastNode.next=new ListNode(insertItem); length+; / Remove the first node from the List. public Eight removeFromFront() throws EmptyListException Eight removeItem=null; if(isEmpty() throw new EmptyListException(name); removeItem=firstNode.data; /retrieve the data reset the firstNode and lastNode references if(firstNode.equals(lastNode) firstNode=lastNode=null; else firstNode=firstNode.next; length-; return removeItem; /Remove the last node from the List public Eight removeFromBack() throws EmptyListException Eight removeItem=null; if(isEmpty() throw new EmptyListException(name); removeItem=lastNode.data; /retrieve the data reset the firstNode and lastNode references if(firstNode.equals(lastNode) firstNode=lastNode=null; else ListNode current=firstNode; while(current.next !=lastNode) current=current.next; lastNode=current; current.next=null; length-; return removeItem; /Return true if the List is empty. public boolean isEmpty() return firstNode=null; /Output the List contents public void print() if(isEmpty() System.out.println(Empty ); return; ListNode current=firstNode; do current.data.print(); System.out.println(f:+current.data.f(); System.out.println(=); current=current.next; while(current !=null); / Class EmptyListException definitionclass EmptyListException extends RuntimeException public EmptyListException(String name) super(The + name + is empty); 程序截图如下：深度优先算法#include #include iostream.h#include stdio.h#include stdlib.h#include time.h#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;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 = 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(int 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(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 = 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 = 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); do p1=OPEN.top(); OPEN.pop(); if(IsSuccess(p1,Target) T=p1; return T; if(p1-step=dm) CLOSED.push(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 = 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 5 Target.cell00 = 1; Target.cell01 = 2; Target.cell02 = 3; Target.cell10 = 8; Target.cell11 = 0; Target.cell12 = 4; Target.cell20 = 7; Target.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-