回溯算法解决智能拼图的最小步骤的问题
文章目录题目描述分析代码的完整实现题目描述要求输入一个拼图的初始状态，返回拼图的成功所经过的最小的步数,例如：
初始状态：123456708成功的状态123456780输出步数：10号可以与相邻的数字进行交换，要求最后的状态0号位于右下方，其余位置按上面的顺序排列
分析这和我们常见的迷宫求解的题目有些差别，迷宫求解的过程中可以标记走过的路，以防止重复同样的步骤，但这里不能通过标记走过的位置了，因为一个要达到最终的状态，可能一个位置要重复地走很多遍才能达到成功的状态。虽然不能标记拼图中单独的位置，我们可以把整个地图的状态保存下来，当0位置改变的时候，我们判断改变后的拼图是否已经出现过，如果出现过，0位置不改变，否则才改变。这里我们采用递归的分析方式，函数findCount（x,y）返回当0位于（x,y）位置时到达成功状态所经过的最小的步数，每次0号位置都有四种移动方案向上、向下、向左、向右，只要统计出经过四个方向到达成功状态的最小步数，转换成代码就是
findCount(x,y)=min(findCount(x-1,y),findCount(x,y-1),findCount(x+1,y),findCount(x,y+1));只要找到递归的公式，递归的代码比较容易了。
这里还有一个问题就是怎样保存整个拼图，这个方法有很多，我用了一种hash的方式
//传入保存拼图的数组intfun(vector&vec){inttmp=0;introw=vec.size();for(inti=0;iinta=vec[i][j]+(i*row+j);//求解拼图中各个位加上一定的对应的数值后，再向右移动相应的位数，//这里要尽量保证不同的拼图状态求出的hash值不相同tmp+=(ainttmp=0;introw=vec.size();for(inti=0;iinta=vec[i][j]+(i*row+j);tmp+=(a//初始化方向H[0]=1;V[0]=0;H[1]=0;V[1]=-1;H[2]=-1;V[2]=0;H[3]=0;V[3]=1;//初始化_nums;给出一个成功的状态，求出hash值保存，以便比较intk=1;for(inti=0;itmp.push_back(k++);}_nums.push_back(tmp);tmp.clear();}_nums[row-1][col-1]=0;//初始化_endStat;_endStat=_hash.fun(_nums);}//交换数组中的两个元素voidswap(inti,intj,inttmpx,inttmpy);//查找最少的次数intfindCount(intx,inty);//设置数组的初始状态vectorsetNums();private:vector_nums;unordered_map_map;//保存已经遍历过的状态//map_map;//保存已经遍历过的状态int_endStat;//成功状态;CHash_hash;intH[4];intV[4];};//移动0后交换两个数值voidSolution::swap(intx,inty,inttmpx,inttmpy){_nums[x][y]=_nums[x][y]^_nums[tmpx][tmpy];_nums[tmpx][tmpy]=_nums[x][y]^_nums[tmpx][tmpy];_nums[x][y]=_nums[x][y]^_nums[tmpx][tmpy];}//设置初始化的拼图的值，并返回0的位置vectorSolution::setNums(){introw=_nums.size();intcol=_nums[0].size();vectortmp;for(inti=0;iintdata;//键盘终端获取最初的拼图的状态cin>>data;if(data==0){tmp.push_back(i);tmp.push_back(j);}_nums[i][j]=data;}}returntmp;}intSolution::findCount(intx,inty){if(_hash.fun(_nums)==_endStat){return0;}else{intm=INF;for(inti=0;i//交换位置swap(x,y,tmpx,tmpy);//求交换后的hash值inthashNums=_hash.fun(_nums);//判断交换后的状态是否出现过autoit=_map.find(hashNums);//没有出现过则添加if(it==_map.end()){_map[hashNums]++;//此时0号位置改变，求改变后最少经过多少步能达到成功状态//求出count后，count+1就是改变前到达成功状态所经过的步数intcount=findCount(tmpx,tmpy);//如果到不了成功状态，返回值>INF(前面的宏定义)//m记录的是达到成功状态经过的最少步数，//把一些确定不可能到达目的状态的或者到达目的状态较长的路径剪掉if(countm=count;}}//回溯到交换之前的状态，进入下一个方向的选择swap(x,y,tmpx,tmpy);}}returnm+1;//最小步数加一也就是当前位置的最小步数}}intmain(){introw,col;coutrow>>col;Solutions(row,col);vectorvec=s.setNums();cout自动解决智能拼图，A*算法
拼图游戏可解性判断，自动生成可解拼图yyjnz:把真确的拼图不停的无规律的移动，打乱后的拼图并不需要进行游戏无解判断
自动解决智能拼图，A*算法Cpp初学者:学写了，研究了一下，发现这个启发算法guessCost这里用guessCost+=abs(yM-yD)+abs(xM-xD);也行，甚至会更加高效，添加到openList的少了很多。但是我还发现，如果把这个guessCost权重加大，比如guessCost+=(abs(yM-yD)+abs(xM-xD))*100;也能得出正确结果，但是有的图步数会增加。如果不加大权重，用guessCost+=abs(yM-yD)+abs(xM-xD);暂时还没有发现步数增加的情况，看起来是高效了，不知道会不会有什么我没有一发现问题？综合上面，我想问一下，这个值到底应该怎么取？才能保证绝对最少步数又最高效？楼主给出的这个guessCost+=sqrt(1.0*(yM-yD)*(yM-yD)+(xM-xD)*(xM-xD));有什么依据呢？会不会在有的图里（扩展到4*45*5），也出现步数不是最少的情况？
拼图游戏可解性判断，自动生成可解拼图wei.yinfu:您这答案好像是错误的,4*4的拼图目标状态逆序数为奇数.
机器学习笔记：线性规划，梯度下降fuzzybug:总结的很全面。同样也在看ng的公开课。随机梯度下降在实际应用中确实是收敛的。另外，公开课的笔记中对J的求法，似乎少了一个m的均值，这样在样本数目不多并且特征x不多的情况下还是可以适应的。
自动解决智能拼图，A*算法机器智能:OK！