问题描述： 将8-魔方的起始状态在有限移动步骤内，转换为目标状态，如下图所示。  算法思路： 通过优先队列实现相似度比对，当相似度为9，即当前状态与目标状态一致时，返回当前路径。 源码： ~~~ /* 8-cube problem-Best-First algorithm 15S103182 Ethan 2015.12.21 */ #include <iostream> #include <vector> #include <queue> #include <fstream> #include <sstream> using namespace std ; class cube{ public: vector<vector<int> > m; int similarity; int x;// 0::i int y;// 0::j vector<string> path;//up down left right cube(vector<vector<int> > a,int b):m(a),similarity(b){} void pos(){//0-position for(int i=0;i<m.size();i++){ for(int j=0;j<m[i].size();j++){ if(m[i][j]==0){ x = i; y = j; return ; } } } } }; bool operator < (const cube& a,const cube& b){ return a.similarity<=b.similarity; } int stringToInt(string i){ stringstream sf; int score=0; sf<<i; sf>>score; return score; } cube openFile(const char* dataset){ fstream file; file.open(dataset,ios::in); vector<vector<int> > data; while(!file.eof()){ vector<int> tv; char temp[8]; file.getline(temp,6); tv.push_back(temp[0]-48); tv.push_back(temp[2]-48); tv.push_back(temp[4]-48); data.push_back(tv) ; } file.close(); cube res(data,0); return res; } void output(vector<vector<int> > m){ for(int i=0;i<m.size();i++){ for(int j=0;j<m[i].size();j++){ cout<<m[i][j]<<"\t"; } cout<<endl; } } int calSimilarity(cube a,cube t){ int s = 0; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(a.m[i][j]==t.m[i][j]) s++; } } return s; } vector<cube> move(const cube& v){ vector<cube> res; if(v.x>0){ cube a(v); a.m[a.x][a.y] = a.m[a.x-1][a.y]; a.m[a.x-1][a.y] = 0; a.x--; a.path.push_back("down"); res.push_back(a); } if(v.x<2){ cube a(v); a.m[a.x][a.y] = a.m[a.x+1][a.y]; a.m[a.x+1][a.y] = 0; a.x++; a.path.push_back("up"); res.push_back(a); } if(v.y>0){ cube a(v); a.m[a.x][a.y] = a.m[a.x][a.y-1]; a.m[a.x][a.y-1] = 0; a.y--; a.path.push_back("right"); res.push_back(a); } if(v.y<2){ cube a(v); a.m[a.x][a.y] = a.m[a.x][a.y+1]; a.m[a.x][a.y+1] = 0; a.y++; a.path.push_back("left"); res.push_back(a); } return res; } void eightCube(cube orginal,cube target){ priority_queue<cube,vector<cube>,less<cube> > pq; vector<cube> copy; orginal.similarity = calSimilarity(orginal,target); orginal.pos(); pq.push(orginal); copy.push_back(orginal); while(!pq.empty()){//best-first cube v = pq.top(); pq.pop(); vector<cube> ms = move(v); for(int i=0;i<ms.size();i++){ ms[i].similarity = calSimilarity(ms[i],target); ms[i].pos(); int flag = 1; for(int j=copy.size()-1;j>=0;j--){ if(calSimilarity(ms[i],copy[j])==9){ flag = 0; break; } } if(flag){ if(ms[i].similarity==9){ cout<<"Path:"<<endl; cout<<"orginal --> "; for(int k=0;k<ms[i].path.size();k++){ cout<<ms[i].path[k]<<" --> "; } cout<<"target"<<endl; return ; } pq.push(ms[i]); copy.push_back(ms[i]); } } } } int main() { eightCube(openFile("original.txt"),openFile("target.txt")); } ~~~ 测试： 起始状态： 5     6     7 2     0     3 1     4     8 目标状态： 1     2     3 4     5     6 7     8     0 移动路径：