广度优先搜索：八数码问题
问题描述
问题分析
状态空间
广度优先搜索
用队列保存待扩展的节点
从队首队取出节点， 扩展出的新节点放入队尾，直到队首出现目标节点（问题的解）
BFS()
{
初始化队列；
while(队列不为空且未找到目标节点)
{
取队首节点扩展，并将扩展出的非重复节点放入队尾；
必要时要记住每个节点的父节点；
}
}
关键问题
新扩展出的节点如果和以前扩展出的节点相同，则该新节点就不必再考虑
如何判重？
状态数目巨大，如何存储？
怎样才能较快判断一个状态是否重复？
要用合理的编码表示“状态”，减小存储代价
方案1
每个状态用一个字符串存储,
要9个字节, 太浪费了！！！
方案2
方案3
方案4
时间与空间的权衡
对于状态数较小的问题，可以用最直接的方式编码以空间换时间
对于状态数太大的问题，需要利用好的编码方法以时间换空间
具体问题具体分析
输入输出
八数码问题有解性的判定
程序实现
#include<iostream>
#include<cstring>
#include<bitset>
using namespace std;
int goalPermutationID;
struct Node
{
int permutationID;//***
int father;//父序列在队列中的下标
char pMove;//父序列到当前序列所做的移动
Node(int p, int f, char pM): permutationID(p), father(f), pMove(pM) {}
Node() {}
};
bitset<362880> Flags;//9!,序列长度固定为9
const int MAXS = 400000;
int factorial[9];//存放0-8的阶乘
Node myQueue[MAXS];
int qHead, qTail;
char res[MAXS];//存放路径上的移动方式
char moves[5] = "udrl";
int GetIDForIntPermutation(int* intPer)
{
//输入整数序列得到***
int id = 0;
bool used[9];
memset(used, 0, 9 * sizeof(bool));
for(int i = 0; i < 9; i++)
{
int n = 0;
for(int j = 0; j < intPer[i] ; j++)
if(!used[j])
n++;
id += n * factorial[8 - i];
used[intPer[i]] = true;
}
return id;
}
template<class T>
int GetIDForPermutation(T s1, T s2)
{
//[s1,s1+9)为0号序列
//[s2,s2+9)为要求序号的序列
//序列不限制为整数序列
int intPer[9];//存放[s2,s2+9)转换得的整数序列
int i, j;
for(i = 0; i < 9; i++)
for(j = 0; j < 9; j++)
if(*(s2 + i) == *(s1 + j))
{
intPer[i] = j;
break;
}
int id = GetIDForIntPermutation(intPer);
return id;
}
template<class T>
void GetPermutationByID(T s1, T s2, int id)
{
int intPer[9];
bool used[9];
memset(used, 0, 9 * sizeof(bool));
int i, j;
for(i = 0; i < 9; i++)
{
for(j = 0; j < 9; j++)
if(!used[j])
{
if(factorial[8 - i] >= id + 1) break;
id -= factorial[8 - i];
}
intPer[i] = j;
used[j] = true;
}
for(i = 0; i < 9; i++)
*(s2 + i) = *(s1 + intPer[i]);
}
int StrStatusToIntStatus(const char* strStatus)
{
return GetIDForPermutation("012345678", strStatus);
}
void IntStatusToStrStatus(char* strStatus, int id)
{
GetPermutationByID((char*) "012345678", strStatus, id);
}
int NewIntStatus(int nowIntStatus, int nowMove)
{
int newIntStatus;
char tmp[9];
IntStatusToStrStatus(tmp, nowIntStatus);
int zeroPos;
for(int i = 0; i < 9; i++)
if(tmp[i] == '0')
{
zeroPos = i;
break;
}
switch(nowMove)
{
case'u':
if(zeroPos - 3 < 0) return -1; //此移动方式不行
else
{
tmp[zeroPos] = tmp[zeroPos - 3];
tmp[zeroPos - 3] = '0';
}
break;
case'd':
if(zeroPos + 3 > 9) return -1; //此移动方式不行
else
{
tmp[zeroPos] = tmp[zeroPos + 3];
tmp[zeroPos + 3] = '0';
}
break;
case'l':
if(zeroPos % 3 == 0) return -1; //此移动方式不行
else
{
tmp[zeroPos] = tmp[zeroPos - 1];
tmp[zeroPos - 1] = '0';
}
break;
case'r':
if(zeroPos % 3 == 2) return -1; //此移动方式不行
else
{
tmp[zeroPos] = tmp[zeroPos + 1];
tmp[zeroPos + 1] = '0';
}
break;
}
return StrStatusToIntStatus(tmp);
}
bool BFS(int nowIntStatus)
{
Flags.reset();//标志置零
qHead = 0;
qTail = 1; //指向队列最后一个元素的后面
myQueue[qHead] = Node(nowIntStatus, -1, 0);
while(qHead != qTail)
{
nowIntStatus = myQueue[qHead].permutationID;
if(nowIntStatus == goalPermutationID) return true;
for(int i = 0; i < 4; i++)
{
int newIntStatus = NewIntStatus(nowIntStatus, moves[i]);
if(newIntStatus == -1)
continue;
if(Flags[newIntStatus])
continue;
myQueue[qTail++] = Node(newIntStatus, qHead, moves[i]);
Flags.set(newIntStatus, true);
}
qHead++;
}
return false;
}
int SumPermutation(const char* strStatus)
{
//计算顺序总数
int n = 0;
for(int i = 0; i < 9; i++)
{
if(*(strStatus + i) != '0')
for(int j = 0; j < i; j++)
if(* (strStatus + j) != '0' and * (strStatus + j) < * (strStatus + i))
n++;
}
return n;
}
int main()
{
factorial[0] = factorial[1] = 1;
int i, j;
for(i = 2; i < 9; i++)
factorial[i] = i * factorial[i - 1];
goalPermutationID = StrStatusToIntStatus("123456780");
char tmp1[50];
char tmp2[20];
while(cin.getline(tmp1, 48))
{
j = 0;
for(i = 0; tmp1[i]; i++)
if(tmp1[i] != ' ')
tmp2[j++] = tmp1[i];
tmp2[j] = 0;
int sumGoal = SumPermutation("123456780");
int sumOri = SumPermutation(tmp2);
if(sumGoal % 2 != sumOri % 2)
{
cout << "unsolvable!" << endl;
continue;
}
if(BFS(StrStatusToIntStatus(tmp2)))
{
int nMoves = 0;
int nPos = qHead;
do
{
res[nMoves++] = myQueue[nPos].pMove;
nPos = myQueue[nPos].father;
}
while(nPos > 0);
for(int i = nMoves - 1; i >= 0; i--)
cout << res[i];
}
else cout << "unsolvable!" << endl;
}
}
运行结果
如何加快速度
广搜VS深搜
双向广搜
程序实现
#include<iostream>
#include<cstring>
#include<bitset>
#include<algorithm>
using namespace std;
int goalPermutationID;
struct Node
{
int permutationID;//***
int father;//父序列在队列中的下标
char pMove;//父序列到当前序列所做的移动
Node(int p, int f, char pM): permutationID(p), father(f), pMove(pM) {}
Node() {}
};
bitset<362880> Flags[2];//9!,序列长度固定为9
const int MAXS = 400000;
int factorial[9];//存放0-8的阶乘
Node myQueue[2][MAXS];
int qHead[2], qTail[2];
char res[MAXS];//存放路径上的移动方式
char moves[5] = "udrl";
int matchingPos;//存放两队列相遇时的状态序列
int queueID;//存放两队列有交点时在扩展的队列序号
int GetIDForIntPermutation(int* intPer)
{
//输入整数序列得到***
int id = 0;
bool used[9];
memset(used, 0, 9 * sizeof(bool));
for(int i = 0; i < 9; i++)
{
int n = 0;
for(int j = 0; j < intPer[i] ; j++)
if(!used[j])
n++;
id += n * factorial[8 - i];
used[intPer[i]] = true;
}
return id;
}
template<class T>
int GetIDForPermutation(T s1, T s2)
{
//[s1,s1+9)为0号序列
//[s2,s2+9)为要求序号的序列
//序列不限制为整数序列
int intPer[9];//存放[s2,s2+9)转换得的整数序列
int i, j;
for(i = 0; i < 9; i++)
for(j = 0; j < 9; j++)
if(*(s2 + i) == *(s1 + j))
{
intPer[i] = j;
break;
}
int id = GetIDForIntPermutation(intPer);
return id;
}
template<class T>
void GetPermutationByID(T s1, T s2, int id)
{
int intPer[9];
bool used[9];
memset(used, 0, 9 * sizeof(bool));
int i, j;
for(i = 0; i < 9; i++)
{
for(j = 0; j < 9; j++)
if(!used[j])
{
if(factorial[8 - i] >= id + 1) break;
id -= factorial[8 - i];
}
intPer[i] = j;
used[j] = true;
}
for(i = 0; i < 9; i++)
*(s2 + i) = *(s1 + intPer[i]);
}
int StrStatusToIntStatus(const char* strStatus)
{
return GetIDForPermutation("012345678", strStatus);
}
void IntStatusToStrStatus(char* strStatus, int id)
{
GetPermutationByID((char*) "012345678", strStatus, id);
}
int GetNewIntStatus(int nowIntStatus, int nowMove)
{
int newIntStatus;
char tmp[9];
IntStatusToStrStatus(tmp, nowIntStatus);
int zeroPos;
for(int i = 0; i < 9; i++)
if(tmp[i] == '0')
{
zeroPos = i;
break;
}
switch(nowMove)
{
case'u':
if(zeroPos - 3 < 0) return -1; //此移动方式不行
else
{
tmp[zeroPos] = tmp[zeroPos - 3];
tmp[zeroPos - 3] = '0';
}
break;
case'd':
if(zeroPos + 3 > 9) return -1; //此移动方式不行
else
{
tmp[zeroPos] = tmp[zeroPos + 3];
tmp[zeroPos + 3] = '0';
}
break;
case'l':
if(zeroPos % 3 == 0) return -1; //此移动方式不行
else
{
tmp[zeroPos] = tmp[zeroPos - 1];
tmp[zeroPos - 1] = '0';
}
break;
case'r':
if(zeroPos % 3 == 2) return -1; //此移动方式不行
else
{
tmp[zeroPos] = tmp[zeroPos + 1];
tmp[zeroPos + 1] = '0';
}
break;
}
return StrStatusToIntStatus(tmp);
}
bool DBFS(int nowIntStatus)
{
for(int i = 0; i < 2; i++)
{
Flags[i].reset();//标志置零
qHead[i] = 0;
qTail[i] = 1; //指向队列最后一个元素的后面
}
myQueue[0][qHead[0]] = Node(nowIntStatus, -1, 0);
myQueue[1][qHead[1]] = Node(goalPermutationID, -1, 0);
Flags[0].set(nowIntStatus, true);
Flags[1].set(goalPermutationID, true);
int nowQueueID = 0;
while((qHead[0] != qTail[0] || qHead[1] != qTail[1]))
{
if(qHead[nowQueueID] == qTail[nowQueueID])
{
//当前队列为空,扩展另一队列
nowQueueID = 1 - nowQueueID;
}
if(qTail[nowQueueID] - qHead[nowQueueID] > qTail[1 - nowQueueID] - qHead[1 - nowQueueID])
{
//当前队列长度较长,扩展另一队列
nowQueueID = 1 - nowQueueID;
}
nowIntStatus = myQueue[nowQueueID][qHead[nowQueueID]].permutationID;
if(Flags[1 - nowQueueID][nowIntStatus])
{
queueID = nowQueueID;
for(int i = qTail[1 - nowQueueID] - 1; i >= 0; i--)
if(myQueue[1 - nowQueueID][i].permutationID == nowIntStatus)
matchingPos = i;
return true;
}
for(int j = 0; j < 4; j++)
{
int newIntStatus = GetNewIntStatus(nowIntStatus, moves[j]);
if(newIntStatus == -1) continue;
if(Flags[nowQueueID][newIntStatus]) continue;
myQueue[nowQueueID][qTail[nowQueueID]++] = Node(newIntStatus, qHead[nowQueueID], moves[j]);
Flags[nowQueueID].set(newIntStatus, true);
}
qHead[nowQueueID]++;
}
return false;
}
int SumPermutation(const char* strStatus)
{
//计算顺序总数
int n = 0;
for(int i = 0; i < 9; i++)
{
if(*(strStatus + i) != '0')
for(int j = 0; j < i; j++)
if(* (strStatus + j) != '0' and * (strStatus + j) < * (strStatus + i))
n++;
}
return n;
}
char ReverseMove(char nMove)
{
switch(nMove)
{
case'u':
return 'd';
case'd':
return 'u';
case'l':
return 'r';
case'r':
return 'l';
}
return 0;
}
int main()
{
factorial[0] = factorial[1] = 1;
int i, j;
for(i = 2; i < 9; i++)
factorial[i] = i * factorial[i - 1];
goalPermutationID = StrStatusToIntStatus("123456780");
char tmp1[50];
char tmp2[20];
while(cin.getline(tmp1, 48))
{
j = 0;
for(i = 0; tmp1[i]; i++)
if(tmp1[i] != ' ')
tmp2[j++] = tmp1[i];
tmp2[j] = 0;
int sumGoal = SumPermutation("123456780");
int sumOri = SumPermutation(tmp2);
if(sumGoal % 2 != sumOri % 2)
{
cout << "unsolvable!" << endl;
continue;
}
if(DBFS(StrStatusToIntStatus(tmp2)))
{
int nMoves = 0;
int nPos = qHead[queueID];
do
{
res[nMoves++] = myQueue[queueID][nPos].pMove;
nPos = myQueue[queueID][nPos].father;
}
while(nPos > 0);
reverse(res, res + nMoves);
for(int i = matchingPos; i > 0;)
{
res[nMoves++] = ReverseMove(myQueue[1 - queueID][i].pMove);
i = myQueue[1 - queueID][i].father;
}
if(queueID == 1)
reverse(res, res + nMoves);
for(int i = 0; i < nMoves ; i++)
cout << res[i];
}
else cout << "unsolvable!" << endl;
}
}