遗传算法示例.docx
- 文档编号:3383974
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:33
- 大小:81.52KB
遗传算法示例.docx
《遗传算法示例.docx》由会员分享,可在线阅读,更多相关《遗传算法示例.docx(33页珍藏版)》请在冰点文库上搜索。
遗传算法示例
实验一、过河问题
一、问题描述
有三个牧师和三个野人过河,只有一条能装下两个人的船,在河的任何一方或者船上,如果野人的人数大于牧师的认输,那么牧师就会有危险.找出一种按的渡河方法。
将该问题转变为:
假如有n个牧师和n个野人准备渡河,但只有一条能容纳c个人的小船,为了防止野人侵犯牧师,要求无论在何处,牧师的人数不得少于野人的人数(除非牧师人数为0),且假定两种人都会划船,试设计一个算法,确定它们能否渡过河去,若能,则给出一只小船来回次数最少的最佳方案。
二、基本要求
输入:
牧师人数(即野人人数)n,小船一次至多载客人数c。
输出:
若问题无解,则显示“渡河失败”信息,否则,输出一组最佳方案,用三组(X1,X2,X3)表示渡河过程中的状态。
并用箭头输出这些状态之间的迁移:
目的状态<-<-中间状态<-<-初始状态。
例:
当n=2,c=2时,输出000<-021<-211<-110<-221
上述(X1,X1,X2)表示渡河过程中各个状态。
其中:
X1表示始岸上牧师人数,X2表示始岸上野人人数,
X3表示小船位置,(0-在目的岸,1-在起始岸)
三、算法描述
(1)算法基本思想的文字描述;
从初始状态S(n,n,1)出发,形成的有合法且未达状态S11、S12、……、Sli。
再分别从S11、S12、……、Sli出发形成所有合法而未达状态S111、S112、……、Sli1、Sli2、Sli……最终达到目标(0,0,0)(有解),或者找不到合法而未达状态(无解)。
若有解,则从目标返回找前趋状态,前趋状态的前趋状态……直到初始状态。
(2)判别(X1,X2,X3)为合法状态条件:
X1=0或X1=n或X1=X2。
(3)数据结构:
1已达
2未达
1栈STACK,记下“已达”状态及踪迹,并兼作队列。
2STATE[X1][X2]=
(4)算法基本思想的具体实现:
1初始化:
置STATE[N+1][N+1][2]中的有状态为“未达”
1未达目标
2已达到目标
置队列STACK空,cond为当前是否已达到目标:
cond=
cond置初值
2以S(n,n,1)为始点,置STATE为“已达”。
S入队列STACK
3while(队列STACK空且未达到目标时)
A{取出队头元素地址=>p1,队头元素出队列
Bwhile(未达到目标,且P1有可达、合法、且未到达过的相邻顶点Q)
if(Q=(000)则{cond=1,Q入队列}
否则{置QW为“已达”,Q入队列}
/*B可用函数COMBINE实现*/
4if(cond=1)则按队列中前趋指针指示的次序依次输出序列,否则输出“渡河失败”。
5COMBINE函数的功能等价于从数量不等的物品,分别选出1件、2件、……C件物品的所有组合,同时对每一种组合确定其合法性。
COMBINE()
{1栈SP初始化(SP存放已放入物品序号),NUM为已取出物品个数,NUM=0,i为准备取出物品序号,i<=1。
2do{
while(未达到目标,且所有物品还未取尽,且NUM {若该种物品已取尽,则取下一种,i++; 取出第i种物品中一件来,该物来序号(即i)进栈,NUM++; 判断该状态合法否? ! /*用函数dicision实现*/ } if(未达到目标,且栈SP不空) {则读栈SP=>i,将第种物品放回一件: NUM--: 退栈;i++;} }while(未达到目标,且并非所有情况均已列举完) } dicision() {if(当前状态(x1,x2,x3)合法且未达) 则(x1,x2,x3)及前趋指针入队列STACK; if((x1,x2,x3)==0,0,0))则cond=1; } 四、源程序 #include typedefstructnode { intnp;/*Thenormalpeople'snumberatstartshore.*/ intmp;/*Themadpeople'snumberatstartshore.*/ intshore;/*'0'=endshore,'1'=startshore*/ inttrack;/*Thetrackofthepoint*/ }NODE; NODEstack[80];/*Themassagefromstack[1]*/ intstate[80][80][2],n,c,front,back,cond; voiddicision(intt[]) { inta[4],i; for(i=0;i<4;i++)a[i]=t[i]; if(a[2]==1) { a[0]=n-a[0]; a[1]=n-a[1]; } if((a[0]==0||a[0]==n||a[0]==a[1])&&state[a[0]][a[1]][a[2]]==1) { back++; stack[back].np=a[0]; stack[back].mp=a[1]; stack[back].shore=a[2]; stack[back].track=front; } state[a[0]][a[1]][a[2]]=0; if(a[0]==0&&a[1]==0&&a[2]==0) cond=1; } voidcombine(intt[]) { intsp[80];/*Thestack*/ inttop;/*Thestacksp'stop*/ intall;/*Thepeople'snumberatstartshore*/ intnum;/*Thethingsnumberwhichallreadyget*/ inti; top=i=num=0;t[2]=! t[2];all=t[0]+t[1]; do { while(cond! =1&&num { if(t[i]==0) { if(i<1)i++; elsereturn; } t[i]--; sp[top++]=i; num++; all--; dicision(t); } if(cond! =1&&top>0) { i=sp[--top]; t[i]++;all++;num--;i++; } }while(cond! =1&&(top>0||(i<2&&all>0))); } voidput(NODEstack[]) { inti,j,m,b[80]; printf("\nStackNpMpShoreLastpoint\n"); for(i=1;i<=back;i++) printf("<%2d>%5d%5d%7d%10d\n",i,stack[i].np,stack[i].mp,stack[i].shore,stack[i].track); if(cond==1) { i=back;m=0; while(i! =0) { b[m++]=i;i=stack[i].track; } printf("Thecrosswayis: "); for(j=m-1;j>=0;j--) { printf("(%d,",stack[b[j]].np); printf("%d,",stack[b[j]].mp); printf("%d",stack[b[j]].shore); if(j! =0) printf(")->"); } printf(")\n"); printf("Thestackis: %d->",back); for(j=0;j { printf("%d",stack[b[j]].track);if(j! =m-2)printf("->"); } printf("\nSeccess! "); } elseprintf("Failure! "); printf("\n"); } voidmain() { inti,j,s,t[4]; printf("pleaseinputthenumberofpeople(n): ");scanf("%d",&n); printf("pleaseinputthecapacityofboat(c): ");scanf("%d",&c); for(i=0;i<80;i++) for(j=0;j<80;j++) for(s=0;s<2;s++) state[i][j][s]=1; front=back=0; cond=0; state[n][n][1]=0; back++; stack[back].np=n; stack[back].mp=n; stack[back].shore=1; stack[back].track=0; while(back>front&&cond! =1) { front++; t[0]=stack[front].np; t[1]=stack[front].mp; t[2]=stack[front].shore; t[3]=stack[front].track; if(t[2]==0) {t[0]=n-t[0];t[1]=n-t[1];} combine(t); } put(stack); } 五、运行结果 实验二、九宫重排 一、问题描述 利用A*算法实现八数码难题(九宫重排)的搜索。 二、算法描述 procedureheuristic_search open: =[start];closed: =[];f(s): =g(s)+h(s); whileopen! =[]do begin 从open表中删除第一个状态,称为n; ifn=目的状态thenreturn(success); 生成n的所有子状态; ifn没有任何子状态thencontinue; forn的每个子状态do case子状态isnotalreadyonopen表orclosed表: begin 计算该子状态的估价函数值; 将该子状态加到open表中; end; case子状态isalreadyonopen表: if该子状态是沿着一条比在open表已有的更短路径而到达 then记录更短路径走向及其估价函数值; case子状态isalreadyonclosed表: if该子状态是沿着一条比在closed表已有的更短路径而到达 begin 将该子状态从closed表移到open表中; 记录更短路径走向及其估价函数值; end; caseend; 将n放入closed表中; 根据估价函数值,从小到大重新派列open表; end; return(failure); end 应当注意: 定义h*(n)为状态n到目的状态的最优路径的代价。 则,估价函数f(n)中的h(n)应满足: h(n)≤h*(n) 三、程序如下 #include usingnamespacestd; constintN=3;//数组的维数 constintM=100;//open和close的大小 conststaticintgoal[N][N]={{1,2,3},//目标状态 {8,0,4}, {7,6,5}}; structstate//状态结点 { intarrState[N][N]; intvalue;//该结点的启发值f(n) intdepth;//所在的第几层 intparent;//父节点 intnID;//结点标记 public: state() { for(inti=0;i for(intj=0;j arrState[i][j]=-1; value=-1;//该结点的启发值f(n) depth=-1;//所在的第几层 parent=-1;//父节点 nID=-1;//结点标记 } state&operator=(states) { for(inti=0;i for(intj=0;j arrState[i][j]=s.arrState[i][j]; value=s.value; depth=s.depth; parent=s.parent; nID=s.nID; return*this; } booloperator==(states) { for(inti=0;i for(intj=0;j if(arrState[i][j]! =s.arrState[i][j]) returnfalse; returntrue; } booloperator! =(states) { return! (*this==s); } }; classEight { private: stateopen[M];//open表 intopenIndex;//open表的元素个数 stateclosed[M];//close表 intclosedIndex;//closed表的元素个数 intstart[N][N];//开始的状态 intnAutoIncrease; public: Eight(); Eight(ints[][N]); voidinit();//初始化open和close intf(states); intw(ints[N][N]); voidsortOpen();//对Open表进行排序 voidmoveToClosed(states); //voidmoveToOpen(states); voidgenToOpen(states); voidfindZeroPostion(int&x,int&y,states);//查找0的位置进行上下左右移动 boolcompare(states);//当前的状态与目标状态比较 voidgenNewState(stateoldState); voidheuristicSearch();//查找路径 boolIsInOpen(states); boolIsInClosed(states); voidmove(statedes,statesrc); boolIsCanSolve(ints[N][N]); voidfindPath(); voidshow(states); }; Eight: : Eight() { start[0][0]=2; start[0][1]=8; start[0][2]=3; start[1][0]=1; start[1][1]=6; start[1][2]=4; start[2][0]=7; start[2][1]=0; start[2][2]=5; nAutoIncrease=1; openIndex=-1; closedIndex=-1; } Eight: : Eight(ints[][N]) { for(inti=0;i for(intj=0;j start[i][j]=s[i][j]; nAutoIncrease=1; openIndex=-1; closedIndex=-1; } voidEight: : init() { for(inti=0;i for(intj=0;j open[0].arrState[i][j]=start[i][j]; open[0].nID=0; open[0].depth=0; open[0].parent=0; open[0].value=w(start)+0;//f(0)=w(0)+d(0) openIndex=0; closedIndex=-1; } //////////////////// voidEight: : show(states) { for(inti=0;i { cout<<"\t"; for(intj=0;j cout< cout< } cout< //cout<<"fn="< "< "< "< } //////////////// //启发值f(n)=depth+w(n) intEight: : f(states) { returns.depth+w(s.arrState); } ////////////// //计算不在位w(n)的值 intEight: : w(ints[N][N]) { intcount=0; for(inti=0;i for(intj=0;j { if(s[i][j]==0)//不考虑0的位置 continue; if(s[i][j]! =goal[i][j]) count++; } returncount; } /////////////////////////// //sortforOpentable voidEight: : sortOpen() { statetemp; for(inti=0;i for(intj=i+1;j if(open[i].value>open[j].value) { temp=open[i]; open[i]=open[j]; open[j]=temp; } } /////////////////////////// //findcurrentstate'0'postion voidEight: : findZeroPostion(int&x,int&y,states) { for(inti=0;i for(intj=0;j if(s.arrState[i][j]==0) { x=i;//保持行坐标 y=j;//保存列坐标 return; } } /////////////////////////// //thetwostatesexchange voidEight: : move(statedes,statesrc) { for(introw=0;row for(intcol=0;col des.arrState[row][col]=src.arrState[row][col]; des.depth=src.depth; des.parent=src.parent; des.value=src.value; } ///////////////////////// //extendotherstates voidEight: : genNewState(stateoldState) { introw,col; inttemp;//保存状态转换数组中的值 statenewState; findZeroPostion(row,col,oldState);//findzeroposition if(row+1 { //move(newState,oldState); newState=oldState; newState.depth=oldState.depth+1; newState.parent=oldState.nID; newState.nID=nAutoIncrease++;//对ID自动编号 //switch temp=newState.arrState[row][col]; newState.arrState[row][col]=newState.arrState[row+1][col]; newState.arrState[row+1][col]=temp; newState.value=w(newState.arrState)+newState.depth; //newState.value=f(newState); //pushnewStatetoopen genToOpen(newState); } if(row-1>-1)//0向上移动 { newState=oldState; newState.d
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 示例