Java编程

贪心启发算法

而更好的做法是运用“贪心策略”。

[贪心算法]

贪心算法(也叫贪婪算法)不是某种特定的算法,而是一类抽象的算法,或者说只是一种思想,它的具体表现在,对解空间进行搜索时,不是机械地搜索,而是对局部进行择优选取,贪心算法的目的不是为了找到全部解,也当然找不出最优解,而只是找出一种可行解,这样就会得到惊人的高效性。因此,贪心算法也叫启发式搜索,这种启发就是所谓的“贪心策略”。

贪心启发算法

以马踏棋盘问题为例,问题描述:在国际象棋的棋盘上指定一个初始马位置,一匹马从这个位置出发,经过不重复的走动,直到踏遍整个棋盘,输出一种可行路径。

对8×8的棋盘来说,马踏棋盘的解是一个天文数字,相当之多,而采用蛮干算法,求一个解的时候会非常吃力,因此采用贪心算法。这里选取的贪心策略是,在某个马位置顶点的后继顶点(子结点)中,择优选取那些出口更小的顶点进行搜索,出口的意思就是这个点能跳到的可行位置的路径数,这样的贪心策略是容易被人接受的,一开始往出口少的点跳,则往后出口多的点就多,能跳通的可能性就大,而事实也证明了,如果采用这样的策略在求一个解时几乎不需要回溯,对于更大的棋盘也如此。

#include "stdio.h"class horse{public: horse(int,int); ~horse(); void solve(int,int);protected: void dfs(int,int,int); int **data; int *head; int width; int height; int size; int count;};struct hnode{ int x; int y; int weight;};horse::horse(int n,int m){ width=n; height=m; size=n*m; head=new int[size]; data=new int*[m]; for(int i=0;i m;++i) { data[i]=head+i*n; for(int j=0;j n;++j) data[i][j]=0; }}horse::~horse(){ delete[] data; delete[] head;}void horse::solve(int x,int y){ try { count=0; dfs(x,y,1); printf("无解!\n回溯%d次\n",count); } catch(int) { for(int i=0;i height;++i) { printf("\n"); for(int j=0;j width;++j) printf(" %02d",data[i][j]); } printf("\n回溯%d次\n",count); }}void horse::dfs(int x,int y,int c){ static int dx[8]={-1,-1,1,1,-2,-2,2,2}; static int dy[8]={-2,2,-2,2,-1,1,-1,1}; hnode hn[8]; data[y][x]=c; if(c==size)throw(1); for(int i=0;i 8;++i) { int tx,ty; hn[i].x=tx=x+dx[i]; hn[i].y=ty=y+dy[i]; if(tx 0
tx =width
ty =height
data[ty][tx] 0) { hn[i].weight=-1;continue; } hn[i].weight=0; for(int j=0;j 8;++j) { int mx,my; mx=tx+dx[j]; my=ty+dy[j]; if(mx =0&&mx width&&my =0&&my height&&data[my][mx]==0) hn[i].weight++; } if(hn[i].weight==0) hn[i].weight=9; } for(i=0;i 7;++i) for(int j=i+1;j 8;++j) if(hn[i].weight hn[j].weight) { hnode temp=hn[i]; hn[i]=hn[j]; hn[j]=temp; } for(i=0;i 8;++i) if(hn[i].weight 0) dfs(hn[i].x,hn[i].y,c+1); data[y][x]=0; ++count;//回溯次数}void main(){ horse a(8,9);//width=8 * height=9的盘棋 a.solve(0,0);//初始棋子位置}

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注