Best-First求解八数码问题
最后更新于：2022-04-01 20:31:33
问题描述：
将8-魔方的起始状态在有限移动步骤内，转换为目标状态，如下图所示。
算法思路：
通过优先队列实现相似度比对，当相似度为9，即当前状态与目标状态一致时，返回当前路径。
源码：
~~~
/*
8-cube problem-Best-First algorithm
15S103182
Ethan
2015.12.21
*/
#include
#include
#include
#include
#include
using namespace std ;
class cube{
public:
vector > m;
int similarity;
int x;// 0::i
int y;// 0::j
vector path;//up down left right
cube(vector > a,int b):m(a),similarity(b){}
void pos(){//0-position
for(int i=0;i>score;
return score;
}
cube openFile(const char* dataset){
fstream file;
file.open(dataset,ios::in);
vector > data;
while(!file.eof()){
vector 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 > m){
for(int i=0;i move(const cube& v){
vector 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,less > pq;
vector 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 ms = move(v);
for(int i=0;i=0;j--){
if(calSimilarity(ms[i],copy[j])==9){
flag = 0;
break;
}
}
if(flag){
if(ms[i].similarity==9){
cout<<"Path:"< ";
for(int k=0;k ";
}
cout<<"target"<
';