马踏棋盘的贪心算法实现
问题描述：
将马放到国际象棋8*8棋盘的某个方格上，马按照“马走日”的规则移动。为马寻找一条走遍棋盘每一格并且只经过一次的路径，并将数字1、2、3、、、、64依次填入到8*8的方格中。
问题分析：
国际象棋中 \马\的移动规则叫做\马走日\。 它下一步可移动的位置有8个，但是如果\马\位于棋盘的边界附近，它下一步可移动到的位置就不一定有8个了，因为要保证\马\每一步都走在棋盘中。
马踏棋盘的问题其实就是要将1，2，?，64填入到一个8*8的矩阵中，要求相邻的两个数按照\马\的移动规则放置在矩阵中。将矩阵填满并输出。这样在矩阵中从1，2?遍历到64就得到了马踏棋盘的行走路线。因此本题的最终目的是输出一个8*8的矩阵，在该矩阵中填有1，2?64这64个数字，相邻数字之间遵照\马走日\的规则。
假设最开始\马\位于棋盘的(0,0)的位置，接下来\马\有两处位置可走，即(1,2)和(2,1)。这时\马\是无法确定走2的位置最终是正确的，还是走3的位置最终是正确的。因此\马\只能任意先从一个路径走下去（例如从2的位置）。如果这条路是正确的，那当然是幸运的，如果不正确，则\马\要退回到第一步，继续从3的位置走下去。以后\马\走的每一步行走都遵循这个规则。这个过程就是一种深度搜索的过程，同时也是一种具有重复性操作的递归过程。
\马\的行走过程实际上就是一个深度探索的过程。\探索树\的根结点为\马\在棋盘中的初始位置（这里用4*4的棋盘示意）。接下来\马\有两种行走方式，于是根结点派生出两个分支。而再往下一步行走，根结点的两个孩子又能够分别派生出其他不同的\行走路线\分支，如此派生下去，就得到了\马\的所有可能的走步状态。探索树的叶子结点只可能有两种状态：一是该结点不能再派生出其他的\走步\分支了，也就是\马\走不通了；二是棋盘中的每个方格都被走到，即\马\踏遍棋盘。于是从该探索树的根结点到第二种情况的叶结点构成的路径就是马踏棋盘的行走过程。
贪心算法描述：
在此对上述方法进行改进。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法就是贪心算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。
主要代码：
void Horse::sort(Node * node,int len) {
for(int i=0;i if(node[i].value>node[j].value) { Node temp=node[i]; node[i]=node[j]; node[j]=temp; } } } //计算节点的出口数(估值) void Horse::ways_out(Node & node) { int m,n; for(int i=0;i<8;++i) { m=node.x+nx[i]; n=node.y+ny[i]; if(m<0||n<0||m>=width||n>=height) continue; if(borad[m][n]==0) node.value++; } } bool Horse::dfs(int m,int n,int step) { if(borad[m][n]!=0) return false; borad[m][n]=step; if(step==size) throw 1; int newx,newy; Node node[8]; int len=0; for(int i=0;i<8;++i) { newx=m+nx[i]; newy=n+ny[i]; if(newx<0||newy<0||newx>=width||newy>=height) continue; node[len].x=newx; node[len].y=newy; node[len].value=0; ways_out(node[len]); len++; //dfs(newx,newy,step+1); } sort(node,len); for(int i=0;i dfs(node[i].x,node[i].y,step+1); borad[m][n]=0; backcount++;//回塑次数 return false;
马踏棋盘贪心算法
