贪心算法 --- 马踏棋盘(C)
admin
2024-03-16 00:18:06
0

五大常用算法之一,好高大上的东西,决定了把这五大算法给搞了,第一个贪心算法,百度一下它的概念,贴过了来了:

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

贪婪算法是一种改进了的分级处理方法。其核心是根据题意选取一种量度标准。然后将这多个输入排成这种量度标准所要求的顺序,按这种顺序依次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个 可行解,则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。

对于一个给定的问题,往往可能有好几种量度标准。初看起来,这些量度标准似乎都是可取的,但实际上,用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解,而是次优解。因此,选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。

一般情况下,要选出最优量度标准并不是一件容易的事,但对某问题能选择出最优量度标准后,用贪婪算法求解则特别有效。 最优解可以通过一系列局部最优的选择即贪婪选择来达到,根据当前状态做出在当前看来是最好的选择,即局部最优解选择,然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题,最终可得到问题的一个整体最优解。

看完了概念,好像还是有点模糊,用一个例子来更深层次的理解下吧。

马踏棋盘问题:

思路:首先将棋盘当做一个二维数组,然后将数组的每一个值赋值为0,将马的起始地址设为1,比如说是5,6,然后判断当前马所能够到达的地方,找出这些点,通过一个数组,数组中的值记录马下一个位置和当前位置之间的差值,然后遍历一遍数组,检测其下一个位置是否还在棋盘之中,是否走过该位置,然后将其走过的点记录下来,将所获得的这些点的记录进行遍历,遍历每一个点,看一下这些点是否还可以继续向下走,然后将这些点可以向下走的位置有几个记录下来,找到路径最少的一个点,然后将这个点设为初始点,进入下一次遍历,这里个一个问题就是为什么要找剩余路径最少的点呢?而不是去找路径多的,或者是随机的呢,原因就是路劲少的点,到达它的点就少了,如果这次没有选择这个点的话,下次再来这个点就会变得困难,甚至是不可以走了。开始写的一个老是走到一半就会停止了,不能够继续前进了,不知道是什么原因,搞了一晚上的时间,有种把电脑砸了的冲动,最终发现原因竟然是那么简单的,很基础的一点关于c的问题,看来c好久不看,确实是不可以了。

实现代码实例:

# include 
# include 
# include 
# define ROWS 8
# define COLS 8
int cheesboard [ROWS] [COLS];
const int moveX [8] = {-2,-1,1,2,2,1,-1,-2};
const int moveY [8] = {1,2,2,1,-1,-2,-2,-1};
//初始化棋盘,将棋盘所有的位置赋值为0
void initBoard (int board[][COLS]){int i ,j;for(i = 0; i < 8; i ++){for( j = 0; j < 8; j ++){board[i][j] = 0;}}
}
//从待选的下一个点的集合中路径最短的一个
int getMinPath (int a[],int num){//定义下标为int i = 0,index=0;//定义最小的值为a【0】,找到最小的值,而且大于0的值int min= a[0];for(i = 0 ; i< num; i++){if(a[i] >0){min = a[i];index = i;break;}}for(i = index + 1; i < num ;  i++){if(a[i] > 0 && min > a[i]){min = a[i];index = i;}}if(a[index] > 0)return index;return -1;
}
// 打印路径
void printPath (int board[][COLS]){int i,j;for (i = 0; i < ROWS; i++){for ( j = 0; j < COLS; j++){printf("%d\t",board[i][j]);}printf("\n\n");}
}
// 获得马行走的路径
void getPath (int board [][COLS], int startX, int startY){//下一个可行位置的数目int next = 0;//路径最短的可行位置在数组中的位置int min;//下一个可行位置的可行位置数目int nextNext;//将棋盘初始化initBoard (board);// 存放下一个位置对应的下一个位置的数目int nextNum[8] = {0,0,0,0,0,0,0,0};//下一个位置的在二维数组中对应位置,初始为0int nextX[8] = {0,0,0,0,0,0,0,0};int nextY[8] = {0,0,0,0,0,0,0,0};//第一个位置赋值为1board [startX] [startY] = 1;int m,i,j;//走完所有的点要循环63次for ( m = 1; m < 64; m++){//当前点其后面可行的位置设为0next = 0;//通过循环来判断该位置是否还可以向下面位置移动for ( i =  0; i < 8; i++){if(startX + moveX[i] < 0 || startX + moveX[i] >= ROWS|| startY + moveY[i] < 0 || startY + moveY[i] >= COLS|| board[startX+moveX[i]][startY+moveY[i]] != 0){continue;}//如果可以向下一个位置移动的话,通过next数组保存下来,通过next记录下有多少个nextX [next] = startX + moveX[i];nextY [next] = startY + moveY[i];next ++;}//循环结束之后,对next的值进行判断,当为1的时候if (next == 1){//让min=0,表示现在所需要的位置是在我们的保存next数组中的第一位min = 0;//设置初始点goto set_nextpoint;}//无法向下一个位置移动了else if (next == 0){printf("没有路径可走了\n");goto print_path;}else {/*当有多个路径可以走的时候,检测每一个点还可不可以继续向下走然后记录下来该点有几个点可以向下走,找到最少的一个但是不为0的哪一个*/for (i = 0; i=0 && nextX[i] + moveX[j] < ROWS&& nextY[i] + moveY[j] >= 0 && nextY[i] + moveY[j] =0 ){goto set_nextpoint;}else{printf("没有路径可走了\n");goto print_path;}}
set_nextpoint:startX = nextX[min];startY = nextY[min];board[startX][startY] = m+1;}
print_path:printPath(board);}
int main (){int i, j;//获得最开始的位置printf ("请输入第一个棋子所在位置\n");scanf ("%d%d" , & i , & j);printf("%d,%d",i,j);//调用该函数获取路径getPath(cheesboard, i, j);return 0;
}

相关内容

热门资讯

怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...
安卓系统手写%怎样调出,具体实... 你有没有遇到过这种情况:在使用安卓手机的时候,突然想用手写输入法来记录一些灵感或者重要信息,可是怎么...
安卓手机重置 系统设置,轻松恢... 手机用久了是不是感觉卡顿得厉害?别急,今天就来教你怎么给安卓手机来个大变身——重置系统设置!想象你的...
win如何安装安卓系统,Win... 哇,你有没有想过,让你的Win系统也能玩转安卓应用?没错,就是那种在手机上轻松自如的安卓系统,现在也...
苹果qq和安卓系统,跨平台体验... 你有没有发现,现在手机市场上,苹果和安卓的较量可是越来越激烈了呢!咱们就来聊聊这个话题,看看苹果QQ...
显示最好的安卓系统,探索最新旗... 你有没有想过,为什么安卓系统那么受欢迎呢?它就像一个魔法盒子,里面装满了各种神奇的魔法。今天,就让我...
安卓app怎么降级系统,系统版... 你有没有发现,有时候安卓手机的系统更新后,新功能虽然炫酷,但老系统用起来更顺手呢?别急,今天就来教你...
雷军脱离安卓系统,引领科技变革... 你知道吗?最近科技圈可是炸开了锅,因为我们的雷军大大竟然宣布要脱离安卓系统,这可真是让人大跌眼镜啊!...
安卓系统自动开网络,安卓系统自... 你有没有发现,手机里的安卓系统有时候会自动开启网络连接,这可真是让人又爱又恨啊!有时候,你正专心致志...
安卓系统怎样控制后台,因为服务... 手机里的安卓系统是不是感觉越来越卡了?后台程序太多,不仅耗电还影响性能。别急,今天就来教你怎么巧妙地...
安卓系统打游戏推荐,一触即达! 你有没有发现,现在手机游戏越来越好玩了?不管是休闲小游戏还是大型MMORPG,都能在手机上畅玩。但是...