建模培训7.13下午动态贪心算法

1、【贪心算法】贪心算法（也叫贪婪算法）不是某种特定的算法，而是一类抽象的算法，或者说只是一种，它的具体表现在，对解空间进行搜索时，不是机械地搜索，而是对局部进行择优选取，贪心算法的目的不是为了找到全部解，也当然找不出最优解，而只是找出一种可行解，这样就会得到惊人的高效性。因此，贪心算法也叫启发式搜索，这种启发就是所谓的“贪心策略”。以棋盘问题为例，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。对 88 的棋盘来说，棋盘的解是一个天文数字，相当之多，而采用蛮干算法，求一个解的时候会非常吃力，因此采用贪心算法。这里选取的贪

2、心策略是，在某个马位置顶点的后继顶点（子结点）中，择优选取那些出口更小的顶点进行搜索，出口的意思就是这个点能跳到的可行位置的路径数，这样的贪心策略是容易接受的，一开始往出口少的点跳，则往后出口多的点就多，能跳通的可能性就大，而事实也证明了，如果采用这样的策略在求一个解时几乎不需要回溯，对于更大的棋盘也如此。C+代码：在（VC6 上调试通过）#include stdio.h class horsepublic:horse( , );horse();void solve( , ); protected:void dfs( ,*data;*head; width; height; size; cou

3、nt;,);struct hnodex;y; weight;horse:horse(width=n; height=m; size=n*m;n,m)head=newsize; data=new*m; for(i=0;im;+i)datai=head+i*n; for(j=0;jn;+j)dataij=0;horse:horse()delete data; delete head;void horse:solve(x,trycount=0; dfs(x,y,1);y)pr f(无解!n 回溯%d 次n,count);catch(for(pr)i=0;iheight;+i)f(n);for(j=0

4、;jwidth;+j)pr f( %02d,dataij);pr f(n 回溯%d 次n,count);void horse:dfs(x,y,c)s ics icdx8=-1,-1,1,1,-2,-2,2,2;dy8=-2,2,-2,2,-1,1,-1,1;hnode hn8; datayx=c; if(c=size)throw(1); for(i=0;i8;+i)tx,ty; hni.x=tx=x+dxi;hni.y=ty=y+dyi; if(tx=width|ty=height|daytx0)hni.weight=-1;continue;hni.weight=0; for(j=0;j=0&mx=0&myheight&datamymx=0) hni.weight+;if(hni.weight=0) hni.weight=9;for(i=0;i7;+i)for(j=i+1;jhnj.weight)hnode temp=hni; hni=hnj; hnj=temp;for(i=0;i0)dfs(hni.x,hni.y,c+1); datayx=0;+count;