八数码问题——双向广度优先搜索解决

小灰灰 2022-08-04 05:04 174阅读 0赞

八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

![Center][]

![Center 1][]

![Center 2][]

搜索顺序有两种：

（1）两个方向交替进行扩展

（2）每次选择节点少的那个扩展

一般来说方法（2）可以克服两端生长不平衡的现象

// eight.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<vector>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    
    #define N 3
    #define SIZE 9
    typedef unsigned char BYTE;
    /*const int src[N][N] = { { 2, 5, 4 },
    { 3, 0, 7 },
    { 1, 8, 6 } };*/
    const int src[N][N] = { { 8, 7, 1 },
    { 5, 2, 6 },
    { 3, 4, 0 } };
    
    /*const int dst[N][N] = { { 1, 2, 3 },
    { 8, 0, 4 },
    { 7, 6, 5 } };*/
    const int dst[N][N] = { { 1, 2, 3 },
    { 4, 5, 6 },
    { 7, 8, 0 } };
    
    struct Code
    {
    	BYTE value[SIZE];
    	bool operator== (const Code &a) const
    	{
    		for (int i = 0; i < SIZE;i++)
    		if( a.value[i] !=value[i])
    			return false;
    		return true;
    	}
    	Code& operator=(const Code& a)
    	{
    		for (int i = 0; i < SIZE; i++)
    		value[i] = a.value[i];
    		return *this;
    	}
    };
    
    Code up(Code a)
    {
    	int ii=-1;
    	for (int i = 0; i < SIZE; i++)
    		if (a.value[i] == 0)
    		{
    		ii = i;
    		break;
    		}
    	if (ii > 2)
    	{
    		BYTE temp = a.value[ii - 3];
    		a.value[ii - 3] = 0;
    		a.value[ii] = temp;
    	}
    	return a;
    }
    
    Code right(Code a)
    {
    	int ii = -1;
    	for (int i = 0; i < SIZE; i++)
    		if (a.value[i] == 0)
    		{
    		ii = i;
    		break;
    		}
    	if (ii>=0&&(ii+1)%3!=0)
    	{
    		BYTE temp = a.value[ii +1];
    		a.value[ii +1] = 0;
    		a.value[ii] = temp;
    	}
    	return a;
    }
    Code down(Code a)
    {
    	int ii = -1;
    	for (int i = 0; i < SIZE; i++)
    		if (a.value[i] == 0)
    		{
    		ii = i;
    		break;
    		}
    	if (ii>=0&&ii <6)
    	{
    		BYTE temp = a.value[ii + 3];
    		a.value[ii + 3] = 0;
    		a.value[ii] = temp;
    	}
    	return a;
    }
    
    
    Code left(Code a)
    {
    	int ii = -1;
    	for (int i = 0; i < SIZE; i++)
    		if (a.value[i] == 0)
    		{
    		ii = i;
    		break;
    		}
    	if (ii >= 0&&ii%3!=0)
    	{
    		BYTE temp = a.value[ii - 1];
    		a.value[ii - 1] = 0;
    		a.value[ii] = temp;
    	}
    	return a;
    }
    
    vector<Code>solution;
    
    bool expand(vector<vector<Code>>&tobeexpanded, vector<vector<Code>>&a_b, vector<Code>&front_tobeexpanded, vector<Code>&front_a_b)
    {
    	vector<vector<Code>>bbb;
    	vector<Code>::iterator it;
    	front_tobeexpanded.clear();
    	for (int i = 0; i < tobeexpanded.size(); i++)
    	{
    		if (!(up(tobeexpanded[i].back()) == tobeexpanded[i].back()) && find(tobeexpanded[i].begin(), tobeexpanded[i].end(), up(tobeexpanded[i].back())) == tobeexpanded[i].end())
    		{
    			it = find(front_a_b.begin(), front_a_b.end(), up(tobeexpanded[i].back()));
    			if (it != front_a_b.end())
    			{
    				solution = a_b[it - front_a_b.begin()];
    				reverse(tobeexpanded[i].begin(), tobeexpanded[i].end());
    				solution.insert(solution.end(), tobeexpanded[i].begin(), tobeexpanded[i].end());
    				return true;
    			}
    			front_tobeexpanded.push_back(up(tobeexpanded[i].back()));
    			bbb.push_back(tobeexpanded[i]);
    			bbb.back().push_back(up(tobeexpanded[i].back()));
    		}
    		if (!(right(tobeexpanded[i].back()) == tobeexpanded[i].back()) && find(tobeexpanded[i].begin(), tobeexpanded[i].end(), right(tobeexpanded[i].back())) == tobeexpanded[i].end())
    		{
    			it = find(front_a_b.begin(), front_a_b.end(), right(tobeexpanded[i].back()));
    			if (it != front_a_b.end())
    			{
    				solution = a_b[it - front_a_b.begin()];
    				reverse(tobeexpanded[i].begin(), tobeexpanded[i].end());
    				solution.insert(solution.end(), tobeexpanded[i].begin(), tobeexpanded[i].end());
    				return true;
    			}
    			front_tobeexpanded.push_back(right(tobeexpanded[i].back()));
    			bbb.push_back(tobeexpanded[i]);
    			bbb.back().push_back(right(tobeexpanded[i].back()));
    		}
    		if (!(down(tobeexpanded[i].back()) == tobeexpanded[i].back()) && find(tobeexpanded[i].begin(), tobeexpanded[i].end(), down(tobeexpanded[i].back())) == tobeexpanded[i].end())
    		{
    			it = find(front_a_b.begin(), front_a_b.end(), down(tobeexpanded[i].back()));
    			if (it != front_a_b.end())
    			{
    				solution = a_b[it - front_a_b.begin()];
    				reverse(tobeexpanded[i].begin(), tobeexpanded[i].end());
    				solution.insert(solution.end(), tobeexpanded[i].begin(), tobeexpanded[i].end());
    				return true;
    			}
    			front_tobeexpanded.push_back(down(tobeexpanded[i].back()));
    			bbb.push_back(tobeexpanded[i]);
    			bbb.back().push_back(down(tobeexpanded[i].back()));
    		}
    		if (!(left(tobeexpanded[i].back()) == tobeexpanded[i].back()) && find(tobeexpanded[i].begin(), tobeexpanded[i].end(), left(tobeexpanded[i].back())) == tobeexpanded[i].end())
    		{
    			it = find(front_a_b.begin(), front_a_b.end(), left(tobeexpanded[i].back()));
    			if (it != front_a_b.end())
    			{
    				solution = a_b[it - front_a_b.begin()];
    				reverse(tobeexpanded[i].begin(), tobeexpanded[i].end());
    				solution.insert(solution.end(), tobeexpanded[i].begin(), tobeexpanded[i].end());
    				return true;
    			}
    			front_tobeexpanded.push_back(left(tobeexpanded[i].back()));
    			bbb.push_back(tobeexpanded[i]);
    			bbb.back().push_back(left(tobeexpanded[i].back()));
    		}
    	}
    	tobeexpanded = bbb;
    	return false;
    }
    void DBFS()
    {
    	vector<vector<Code>>aa,bb;
    	Code start, ending;
    	for (int i = 0; i < SIZE; i++)
    	{
    		start.value[i] = src[i / 3][i % 3];
    		ending.value[i] = dst[i / 3][i % 3];
    	}
    	vector<Code>a1, b1;
    	a1.push_back(start);
    	b1.push_back(ending);
    	aa.push_back(a1);
    	bb.push_back(b1);
    	vector<Code>front_a, front_b;
    	front_a.push_back(start);
    	front_b.push_back(ending);
    	while (true)
    	{
    		if (aa.size()>bb.size())
    		{
    			if(expand(bb, aa, front_b, front_a))
    				return;
    		}
    		else
    		{
    			if(expand(aa, bb, front_a, front_b))
    				return;
    		}
    	}
    }
    
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    
    	DBFS();
    
    	system("pause");
    	return 0;
    }

题目来源：NOIP2002提高组试题  
描述 Description  
已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:  
A1$ -> B1$  
A2$ -> B2$  
规则的含义为：在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。  
例如：A$='abcd'　B$='xyz'  
变换规则为：  
‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’  
则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：  
‘abcd’->‘xud’->‘xy’->‘xyz’  
共进行了三次变换，使得 A$ 变换为B$。  
输入格式 Input Format  
A$ B$  
A1$ B1$ \\  
A2$ B2$ |-> 变换规则  
... ... /  
所有字符串长度的上限为 20。  
输出格式 Output Format  
若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；  
否则输出"NO ANSWER!"  
样例输入：  
abcd xyz  
abc xu  
ud y  
y yz  
样例输出：  
3  
题目类型：双向广搜

[Center]: /images/20220731/786678b9e0e84a7d99f581f2a7d31445.png
[Center 1]: /images/20220731/e214dc0367574cfa90da26b716e8962e.png
[Center 2]: /images/20220731/dd8ff5aeb1cb4c548bde946774289611.png