A* Algorithm and 8 Puzzle Problem

发表于 | 阅读次数

一 A* 算法

1.1 算法介绍

1.1.1 相关背景

广度优先搜索(Breadth-First-Search,BFS)、深度优先搜索(Depth-First-Search,DFS)以及由此延伸出来的双向广度优先搜索(DBFS)、双向深度优先搜索(DDFS)都属于盲目搜索，这在状态空间不大的情况下是很合适的算法，可是当状态空间十分庞大时，它们的效率实在太低，往往都是在搜索了大量无关的状态结点后才碰到解答，甚至更本不能碰到解答。搜索是一种试探性的查寻过程，为了减少搜索的盲目性引，增加试探的准确性，就要采用启发式搜索了。所谓启发式搜索就是在搜索中要对每一个搜索的位置进行评估，从中选择最好、可能容易到达目标的位置，再从这个位置向前进行搜索，这样就可以在搜索中省略大量无关的结点，提高了速度。

1.1.2 A*算法流程

A*算法是一种启发式搜索算法，可以看做是针对盲目搜索(BFS/DFS)的优化。相对于DFS，A*仅仅多了一个评估值H，使状态空间不那么盲目。在A*算法中，一个结点位置的好坏用估价函数(H)来对它进行评估。A*算法的估价函数可表示为：

其中，$F’(n)$ 是估价函数，$g’(n)$ 是从初始起点到当前节点$n$的最短路径值(也称为最小耗费或最小代价，在盲目搜索中对应搜索深度), $h’(n)$ 是当前节点$n$ 到目标节点的最短路径的启发值。由于这个$f’(n)$ 其实是无法预先知道的，所以实际上使用的是下面的估价函数：

其中$g(n)$ 是从初始结点到当前节点n的实际代价，$h(n)$ 是从当前结点n到目标结点的最佳路径的估计代价。在这里主要是$h(n)$ 体现了搜索的启发信息，因为$g(n)$ 是已知的。用$f(n)$ 作为$f’(n)$ 的近似，也就是用$g(n)$ 代替$g’(n)$ 、$h(n)$ 代替$h’(n)$ , 这样必须满足以下条件：

  1. $g(n)\ge g’(n)$ . 大多数情况下都是满足的，可以不用考虑。 $g(n)$ 必须保持单调递增。
  2. $h(n)$ 必须小于等于实际的从当前节点n到达目标节点的最小耗费,即$h(n)\le h’(n)$ , 可以证明应用这样的估价函数是可以找到最短路径的。

A*算法基本上与BFS相同。区别在于扩展出一个结点后，要计算它的估价函数(f)，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数(f)最小的结点。

具体步骤:

  1. 新建一个Open和Closed表，置空，将初始状态放入Open表中。
  2. 将Open表中最小F值状态取出放入Closed表中，若找到目标状态，则中断过程，此时状态的GG值就是最短路径（在八数码是最少步骤），否则生成其下一步所有能转移的状态集S
  3. 计算状态集S每个状态的F,G,H值，得出F=G+H值，这里的G可取前一个状态（父状态）的GG值加一，为了寻得最短路径，可将其指向父状态。
  4. 枚举状态集，按5, 6处理
  5. 若状态集S的状态在Closed表中，则不理会，否则6
  6. 若状态集S的状态在Open表中且其F值较小，则更新（因为有最优的路径啊当然要更新），否则不理会，若不在Open表中，则插入。
  7. 进入2

伪代码：(源自wiki) 有错误 见我的博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function A*(start,goal)
    closedset := the empty set                 //已经被估算的节点集合
    openset := set containing the initial node //将要被估算的节点集合，初始只包含start
    came_from := empty map
    g_score[start] := 0                        //g(n)
    h_score[start] := heuristic_estimate_of_distance(start, goal)    //通过估计函数 估计h(start)
    f_score[start] := h_score[start]            //f(n)=h(n)+g(n)，由于g(n)=0，所以省略
    while openset is not empty                 //当将被估算的节点存在时，执行循环
        x := the node in openset having the lowest f_score[] value   //在将被估计的集合中找到f(x)最小的节点
        if x = goal            //若x为终点，执行
            return reconstruct_path(came_from,goal)   //返回到x的最佳路径
        remove x from openset      //将x节点从将被估算的节点中删除
        add x to closedset      //将x节点插入已经被估算的节点
        for each y in neighbor_nodes(x)  //循环遍历与x相邻节点
            if y in closedset           //若y已被估值，跳过
                continue
            tentative_g_score := g_score[x] + dist_between(x,y)    //从起点到节点y的距离
            if y not in openset          //若y不是将被估算的节点
                add y to openset         //将y插入将被估算的节点中
                tentative_is_better := true     //暂时判断为更好
            elseif tentative_g_score < g_score[y]         //如果起点到y的距离小于y的实际距离
                tentative_is_better := true         //暂时判断为更好
            else
                tentative_is_better := false           //否则判断为更差
            if tentative_is_better = true            //如果判断为更好
                came_from[y] := x                  //将y设为x的子节点
                g_score[y] := tentative_g_score    //更新y到原点的距离
                h_score[y] := heuristic_estimate_of_distance(y, goal) //估计y到终点的距离
                f_score[y] := g_score[y] + h_score[y]
    return failure
function reconstruct_path(came_from,current_node)
    if came_from[current_node] is set
        p = reconstruct_path(came_from,came_from[current_node])
        return (p + current_node)
    else
        return current_node

1.1.3 其他

  • 如果$g(n)$ 为0，即只计算任意顶点$n$ 到目标的评估函数$h(n)$ ，而不计算起点到顶点$n$ 的距离，则算法转化为使用贪心策略的Best-First Search，速度最快，但可能得不出最优解；
  • 如果$h(n)$ 不高于实际到目标顶点的距离，则一定可以求出最优解，而且$h(n)$ 越小，需要计算的节点越多，算法效率越低，常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离；
  • 如果$h(n)$ 为0，即只需求出起点到任意顶点$n$的最短路径 ，而不计算任何评估函数$h(n)$ ，则转化为单源最短路径问题，即Dijkstra算法，此时需要计算最多的定点；

1.2 C++实现

1.2.1 数据结构

A*算法主要数据结构为Open表和Close表。其中，Open 表有取最小值、查找、插入、删除操作，Close 表有查找、插入操作。比较好的实现方案是Open 表用优先队列（最小堆） 来实现，Close 表用排序二叉树 来实现。

表中元素的类型取决于具体问题。但该类型的成员应该能(唯一的)表示状态、父节点、g值、h值。且应当定义该类型的拓展子节点(extend)方法、相等判断(operator==)方法、大小比较等。

1.2.2 实现

由于具体问题不可预知，故使用模板类型T作为接口。由于时间仓促，使用std::vector 作为Open、Close表载体。

所有源码见AStar.h 文件。以下只给出主要类、函数声明及含义。

Class Configure :用于设置T类型的相关操作，取决于具体问题。

1
2
3
4
5
6
7
8
9
10
11
template<typename T> class Configure  
	{
		double(*H)(const T  &, const T   &);  //H估值函数，用来衡量当前节点到目标节点的距离
		double(*G)(const T &);  // G估值函数，衡量初始节点到当前节点的距离
		std::vector<T>(*EXPEND)(T);
		//以下函数若已在T类中写成重载运算函数，可省略。
		bool(*EQUAL)(const T &, const T &); //判断是否相等
		bool(*LESS)(const T &, const T &); //判断是否小于
		//其他在生成子节点后需要进行的操作。
		void(*OTHERS)(T &);
	}

Class Status: 状态节点。更新操作(Update)依赖于Configure 类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<typename T> class Status
	{
	public:
		T t;
		double h, g,f;
		Status(T s){	t = s;	}
		void Update(Configure<T> C,Status<T> S)
		{
          h = C.Calculate_H(*this, S);
          g = C.Calculate_G(*this);
          f = h + g;
          C.OTHERS(this->t);
		}
		bool operator==(Status<T> S2){return t == S2.t;}
		bool operator==(T S2){return t == S2;}
		bool operator<(Status<T> S2){return t < S2.t;}
		bool operator<(T S2){return t < S2;}
	};

AStar : A*算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template<typename T> T AStar(const T & start, const T & target, Configure<T> C) 
{
	std::vector<Status<T>> Open, Close;
	Status<T> START(start);
	Status<T> TARGET(target);
	START.Update(C, TARGET);
	Open.push_back(START);
	int step = 0;
	while (Open.size())
	{
//std::cout << " fun:" << step++ << "  Size of Open:" << Open.size() <<std::endl;
		Status<T> tem = *Open.begin();
		//if (C.IS_EAQUE(tem.t, target))
		if(tem.t==target)
			return tem.t;
		Close.push_back(tem);
		std::vector<Status<T>> nex = C.EXPEND_S(tem);
 		for (std::vector<Status<T>>::iterator it = nex.begin(); it != nex.end(); it++)
		{
			it->Update(C, TARGET);
			std::vector<Status<T>>::iterator index_Open = C.Find(Open, *it);
			std::vector<Status<T>>::iterator index_Close = C.Find(Close, *it);
			if (index_Open != Open.end() || index_Close != Close.end())
			{				
				if (index_Open != Open.end() && it->f < index_Open->f)//属于Open;
					index_Open->f = it->f;
			}
			else
				Open.push_back(*it);
		}
		nex.clear();
		Open.erase(Open.begin());
		std::sort(Open.begin(), Open.end(),comp<T>);
	}
	return start;//表示没找到结果
}

二 八数码问题

2.1问题介绍

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。

要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤（下文称为路径）。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

2.2 分析

初步分析得出如下结论：

  • 考虑到除了8数码问题，还有15数码等问题，可以拓展成$N^2-1$ 数码问题。

  • 拓展子节点只与空格位置有关；故下文用u d l r 分别代表空格的上下左右移动。

  • 把$N \times N$ 的二维棋盘“拉伸”成一维数组(下文记为$a_1,a_2, a_3 \cdots a_{n*n}$ )，便于处理。

  • 有些资料中以”1234678X”为目标状态，而另外一些则采用螺旋形”1238X4765”为目标状态。考虑到算法通用性，目标状态不应局限于以上两种。

  • 最终求解的是最短路径，且任意节点可由路径推断出父节点、祖父节点……故使用一个成员变量记录路径之后便不需要再用指针指向父节点

为保证算法正常工作，还必须证明算法的收敛性和可解性。补充如下数学定理。

2.2.1 判断是否有解

逆序对：对于一个排列$a_1, a_2, a_3 \cdots a_n$ , 如果有$ja_i$ ，那么$a_i$和$a_j$ 构成一个逆序对。

定义排列$a_1, a_2 \cdots a_n$ 的逆序数为该所有元素的逆序数总和。

结论：两种状态可以相互到达的条件为一维序列的逆序数奇偶性相同(N为奇数时)；奇偶性相反(N为偶数时)。其中，空格不参与逆序数计算。

先证明3个引理：

引理1：如果左右交换一次棋子，则排列的逆序数奇偶性改变。

证明：不失一般性，设$ a_{i+1}> a_i$ .序列{$a_i , a_{i+1}$} 的逆序数为0. 现在将两者交换，显然对于$a_j$ ($ji+1$ )的逆序数不会改变。而交换之后的序列{ $ a_{i+1},a_i ,$ } 逆序数为1，故总序列的逆序数奇偶性发生改变。

引理2：如果空格与左右交换一次，则排列的逆序数奇偶性不变。

证明：因为不表示空格，所以原排列不变，即证引理成立。

引理3：如果空格与上下交换了一次，则排列的逆序数奇偶性不变。

证明：

若N为奇数，不失一般性设N=3, 则考虑序列$12345678X$ 与下面的空格交换了一次，变为$123450786$ 。该过程可以分解为若干次空格连续左移和若干次被换对象(数字6)连续和右边的数交换：$123456780$ →$123456708$ →$123456078$→$123450678$ （空格左移完成）→$123450768$ →$123450786$ （数字6右移完成）。由引理1知数字6移动两次，不改变奇偶性；由定理2知空格左右移动不影响奇偶性；

若N为偶数，则在数字交换时需要交换$N-1$ 次，则根据引理1，总序列奇偶性发生改变。

由以上可知：N为偶数时，两个序列逆序数奇偶性相反才可互相到达；N为奇数时，两个序列逆序数奇偶性相同才可互相到达。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int reverse_nums(int a[SIZE*SIZE])
{
	int counter = 0;
	for (int i = 0; i < SIZE*SIZE; i++)
	{
		if (*(a + i) == 0)
			continue;
		for (int j = SIZE*SIZE - 1; j >i; j--)
		{
			if (*(a + i) < *(a + j))
				counter++;
		}
	}
	return counter;
}
bool valid_case(int a[SIZE*SIZE], int b[SIZE*SIZE],int N)
{	
   if (N % 2 )
	  return reverse_nums(a) % 2 == reverse_nums(b) % 2 ? true : false;
   else
      return reverse_nums(a) % 2 == reverse_nums(b) % 2 ? false : true;
}

2.2.2 判断是否有多个最优解

首先可以发现唯一解、对称二解、多解等情况都是存在的。

我尝试在数学上进行分析，但暂时失败了。

暴力枚举证明见我的博客(不定时更新)

2.3 实现

根据1.2 C++实现 , 我们只需要定义八数码问题的状态、H、G、拓展方式等即可代入使用。以下是部分代码。完整代码见AStar.cpp

状态类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct status
{
	int m[SIZE*SIZE];
	int x, y;
	string path = " ";
	status()
	{
		memset(m, 0, sizeof(int) * SIZE*SIZE);
	}
	status(int *p)
	{
		memcpy(m, p, sizeof(int) * SIZE*SIZE);
	}
	void operator= (initializer_list<int> p)
	{	std::copy(p.begin(), p.end(), m);	}
	bool operator==(const status &b)
	{
		for (int i = 0; i < SIZE*SIZE; i++)
			if (*(this->m + i) != *(b.m + i))
				return false;
		return true;
	}
};

G(n):

1
2
3
4
double g(const status  & s)
{
	return s.path.size()-1;
}

生成子节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
status  Move(status s, char direction)
vector<status> Generate_Next(const status a)
{
	vector<status> Nex;
	status tem;
	tem = Move(a, 'l');
	if (tem.x != -1)
		Nex.push_back(tem);
	tem = Move(a, 'r');
	if (tem.x != -1)
		Nex.push_back(tem);
	tem = Move(a, 'u');
	if (tem.x != -1)
		Nex.push_back(tem);
	tem = Move(a, 'd');
	if (tem.x != -1)
		Nex.push_back(tem);
	return Nex;
}

H(n)：待定 见下一章。

三 不同估价函数H的对比

3.1 介绍

本章比较了四种不同估价函数H，分别是：

  1. 简单曼哈顿距离。仅统计棋盘各位置上数字不对应的个数
  2. 一维曼哈顿距离。统计各数字到正确位置的一维距离之和
  3. 二维曼哈顿距离。统计各数字到正确位置的二维距离之和
  4. 恒为0；算法蜕化为BFS。

3.1.1 H=Manhattan distance (Simple)

1
2
3
4
5
6
7
8
double h(const status & s, const status  & TARGET)
{
	int h = 0, i = 0;
	for (i = 0; i < SIZE*SIZE; i++)
		if (*(s.m + i) != *(TARGET.m + i))
			h++;
	return h;
}

3.1.2 H=Manhattan distance (One-dimensional)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int find_num(int target,const int * array)
{
	for (int i = 0; i < SIZE*SIZE; i++)
		if (*(array + i) == target)
			return i;
}
double h1(const status & s, const status  & TARGET)
{
	int h = 0, i = 0;
	for (i = 0; i < SIZE*SIZE; i++)
		h += abs(i - find_num(*(s.m+i),TARGET.m));
	return h;
}

3.1.3 H=Manhattan distance (Two-dimensional)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
std::vector<int> find_xy(int target, const int * array)
{
	for (int i = 0; i < SIZE*SIZE; i++)
		if (*(array + i) == target)
			return vector<int>{i / SIZE, i%SIZE};
}
double h2(const status & s, const status  & TARGET)
{
	int h = 0, i = 0;
	int x,y;
	for (i = 0; i < SIZE*SIZE; i++)
	{
		x = i / SIZE; y = i%SIZE;
		std::vector<int> tem = find_xy(*(s.m + i), TARGET.m);
		h += (abs(tem[0] - x) + abs(tem[1] - y));
	}
	return h;
}

3.1.4 H≡0 （BFS)

1
double h_bfs() { return 0; }

3.2 性能分析

为公平全面地评价以上4个H的性能，需要在不同情况、不同深度的图进行测试。

设计如下样本生成器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
status Generate_Case(status start, int depth)
{
	int tem;
	status t;
	while (depth)
	{
		 tem = random(1, 1000);
		switch (tem % 4)
		{
		case 0: t = Move(start, 'l'); break;
		case 1: t = Move(start, 'r'); break;
		case 2: t = Move(start, 'u'); break;
		case 3: t = Move(start, 'd'); break;
		}
		if (t.x!=-1)
		{
			start = t;
			update(start);
			depth--;
		}
	}
	return start;
}
std::vector<status> Generate_Cases(const status target, int depth)
{
	std::vector<status> output;
	std::srand(unsigned(std::time(0)));
	while (depth--)
		output.push_back(Generate_Case(target, depth));
	return output;
}

测试函数：(由于数据结构优化尚未完成，该测试程序需要运行较长时间(20分钟左右))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
void Test(const status & target)
{
	Astar::Configure<status> C(h, g, ifsame, Generate_Next, update);
	Astar::Configure<status> C1(h1, g, ifsame, Generate_Next, update);
	Astar::Configure<status> C2(h2, g, ifsame, Generate_Next, update);
	Astar::Configure<status> C_BFS(h_bfs, g, ifsame, Generate_Next, update);
	std::vector<status> cases = Generate_Cases(target, 20);
	double Time[4][20] = { 0 };
	int Open[4][20] = { 0 };
	int Close[4][20] = { 0 };
	int Extended[4][20] = { 0 };
	string path[4][20];
	std::ofstream outfile;
	outfile.open("test.txt", std::ios::out);
	outfile << "TEST CASES:" << endl;
	std::clock_t  st;
	for (int i=0;i<20;i++)
	{
		//cout << cases[i];
		 st = std::clock();
		auto tem=Astar::AStar<status>(cases[i], target, C,Open[0][i],Close[0][i],Extended[0][i]);
		path[0][i] = tem.path;
		Time[0][i] = std::clock() - st;
		st = std::clock();;
		tem = Astar::AStar<status>(cases[i], target, C1, Open[1][i], Close[1][i], Extended[1][i]);
		path[1][i] = tem.path;
		Time[1][i] = std::clock() - st;
		 st = std::clock();
		 tem = Astar::AStar<status>(cases[i], target, C2, Open[2][i], Close[2][i], Extended[2][i]);
		path[2][i] = tem.path;
		Time[2][i] = std::clock() - st;
		  st = std::clock();
		  tem = Astar::AStar<status>(cases[i], target, C_BFS, Open[3][i], Close[3][i], Extended[3][i]);
		path[3][i] = tem.path;
		Time[3][i] = std::clock() - st;
	}
	for (auto i:cases)
		outfile <<i << " " << i.path << endl;
	outfile << "Open:[";
	for (int i = 0; i < 4; i++)
	{
		outfile << 'H' << i << ':' << endl<<'[';
		for (int j = 0; j < 20; j++)
			outfile << Open[i][j]<<' ';
		outfile << ']' << endl;
	}
	outfile << "Close:[";
	for (int i = 0; i < 4; i++)
	{
		outfile << 'H' << i << ':' << endl<<'[';
		for (int j = 0; j < 20; j++)
			outfile << Close[i][j]<<' ';
		outfile << ']' << endl;
	}
	outfile << "Extended:[";
	for (int i = 0; i < 4; i++)
	{
		outfile << 'H' << i << ':' << endl << '[';
		for (int j = 0; j < 20; j++)
			outfile << Extended[i][j] << ' ';
		outfile << ']' << endl;
	}
	outfile << "Time:[";
	for (int i = 0; i < 4; i++)
	{
		outfile << 'H' << i << ':' << endl << '[';
		for (int j = 0; j < 20; j++)
			outfile << Time[i][j] << ' ';
		outfile << ']' << endl;
	}
	outfile << "Path:[";
	for (int i = 0; i < 4; i++)
	{
		outfile << 'H' << i << ':' << endl << '[';
		for (int j = 0; j < 20; j++)
			outfile << path[i][j] << ' ';
		outfile << ']' << endl;
	}
	outfile << "Length:[";
	for (int i = 0; i < 4; i++)
	{
		outfile << 'H' << i << ':' << endl << '[';
		for (int j = 0; j < 20; j++)
			outfile << path[i][j].length()-1 << ' ';
		outfile << ']' << endl;
	}
	outfile.close();
}

以下为测试结果：

H=Manhattan distance (Simple)

生成序列 起始状态 Open Extemd(Close) Sum 花费时间(ms) 解序列 解序列长度
urddlluurrddlurdllur 345607182 2506 3825 6331 1099 ldrruulldrdruuldldru 20
urddlulurddluurrddl 845326107 1550 2205 3755 247 ruullddrrululdrruld 19
rulldrdlururddllur 823105647 1473 2101 3674 227 ldrruuldldrulurrdl 18
ruldldrurdlluruld 312045768 756 1084 1840 42 urdldrrulurdldlur 17
rdlurdlurdlurull 012843765 6 5 11 0 rrdl 4
urdldluurrddlul 342015867 286 386 672 6 rdruullddruruld 15
ruldrdllurdrul 142307865 237 326 563 5 rdluldrrulurdl 14
lurrddluurdld 245183706 144 191 335 2 urulddruulldr 13
ldrurdlluurr 230145768 97 116 213 1 llddrruldlur 12
urdlldrruul 103784652 71 83 154 0 rddllurruld 11
uldruldrur 230184765 6 5 11 0 lldr 4
urdldluur 304162875 21 21 42 0 ldruruld 9
dlururdl 134602875 19 20 39 0 ldruruld 8
ruldlur 402183765 17 16 33 0 ldrurdl 7
ruldlu 042183765 12 11 23 0 drurdl 6
lurdl 283014765 10 9 19 0 drurdl 5

H=Manhattan distance (One-dimensional)

生成序列 起始状态 Open Extemd(Close) Sum 花费时间(ms) 解序列 解序列长度
urddlluurrddlurdllur 345607182 96 111 207 2 ldruuldrrdluruldldrrul 22
urddlulurddluurrddl 845326107 124 146 270 3 ruuldlurdldrruulldr 19
rulldrdlururddllur 823105647 527 640 1167 41 ldrruuldldrulurrdl 18
ruldldrurdlluruld 312045768 562 733 1295 58 urdldrrulurdldlur 17
rdlurdlurdlurull 012843765 4 4 8 0 rrdl 4
urdldluurrddlul 342015867 611 801 1412 66 rdruullddruruld 15
ruldrdllurdrul 142307865 119 154 273 1 rdluldrrulurdl 14
lurrddluurdld 245183706 22 23 45 0 urulddruulldr 13
ldrurdlluurr 230145768 51 59 110 0 llddrruldlur 12
urdlldrruul 103784652 34 37 71 0 rddllurruld 11
uldruldrur 230184765 6 5 11 0 lldr 4
urdldluur 304162875 9 9 18 0 lddruruld 9
dlururdl 134602875 11 10 21 0 ldruruld 8
ruldlur 402183765 16 14 30 0 ldrurdl 7
ruldlu 042183765 8 7 15 0 drurdl 6
lurdl 283014765 8 6 14 1 ruldr 5

H=Manhattan distance (Two-dimensional)

生成序列 起始状态 Open Extemd(Close) Sum 花费时间(ms) 解序列 解序列长度
urddlluurrddlurdllur 345607182 160 202 362 3 ldrruulldrdruuldldru 20
urddlulurddluurrddl 845326107 145 184 329 3 ruullddrrululdrruld 19
rulldrdlururddllur 823105647 376 515 891 12 ldrruuldldrulurrdl 18
ruldldrurdlluruld 312045768 149 198 347 2 urdldrrulurdldlur 17
rdlurdlurdlurull 012843765 4 4 8 0 rrdl 4
urdldluurrddlul 342015867 77 100 177 1 rdruullddruruld 15
ruldrdllurdrul 142307865 62 73 135 0 rdluldrrulurdl 14
lurrddluurdld 245183706 56 62 118 0 urulddruulldr 13
ldrurdlluurr 230145768 40 41 81 0 llddrruldlur 12
urdlldrruul 103784652 31 30 61 1 rddllurruld 11
uldruldrur 230184765 4 4 8 0 lldr 4
urdldluur 304162875 13 11 24 0 lddruruld 9
dlururdl 134602875 15 13 28 0 ldruruld 8
ruldlur 402183765 11 10 21 1 ldrurdl 7
ruldlu 042183765 7 6 13 0 drurdl 6
lurdl 283014765 7 5 12 0 ruldr 5

H=0 BFS

生成序列 起始状态 Open Extemd(Close) Sum 花费时间(ms) 解序列 解序列长度
urddlluurrddlurdllur 345607182 18765 48740 67505 299365 ldrruldruullddrruuld 20
urddlulurddluurrddl 845326107 14725 35674 50399 155379 ruulldrulddrruulldr 19
rulldrdlururddllur 823105647 11465 23696 31561 72430 ldrruuldldrulurrdl 18
ruldldrurdlluruld 312045768 8304 17363 25667 36628 urdldrrulurdldlur 17
rdlurdlurdlurull 012843765 16 15 31 0 rrdl 4
urdldluurrddlul 342015867 3758 6836 10594 4907 rdruullddruruld 15
ruldrdllurdrul 142307865 2734 4771 7505 1474 rdluldrrulurdl 14
lurrddluurdld 245183706 1708 3049 4754 255 urulddruulldr 13
ldrurdlluurr 230145768 794 1198 1992 44 llddrruldlur 12
urdlldrruul 103784652 615 999 1614 30 rddllurruld 11
uldruldrur 230184765 16 15 31 0 lldr 4
urdldluur 304162875 216 339 555 4 lddruruld 9
dlururdl 134602875 149 230 379 2 ldruruld 8
ruldlur 402183765 84 108 192 0 ldrurdl 7
ruldlu 042183765 55 76 131 0 drurdl 6
lurdl 283014765 32 37 69 0 ruldr 5

在Matlab中画图比较如下：

time

rom

Open

Close

可以看到四种H评估函数都基本能得到最优解。

但是在时间上，二维曼哈顿和一维曼哈顿表现比较好。

空间上，同样是二维曼哈顿和一维曼哈顿表现较好。

BFS时间和空间都随着深度而近似指数增加，效率太低。

三 其他

1

本报告相关内容将发表在我的博客上(不定期更新)：

维基百科A-算法的错误

A-Algorithm-and-8-Puzzle-Problem

八数码最优解是否唯一判定

代码(不定时更新)：https://github.com/Vast-Stars/Algorithm/tree/master/8digit

2

八数码相关的游戏：

拼图：

图片名称

https://github.com/netcan/SlidePuzzle

华容道：

图片名称

3

有个小问题：维基百科上的A*算法流程中，若子节点出现在Close表中，则不采取任何操作，这和书上更新F值相矛盾，为什么？

维基百科A-算法的错误

Reference

http://www.cnblogs.com/luxiaoxun/archive/2012/08/05/2624115.html

八数码问题有解的条件及其推广

解决八数码问题之A-算法

http://lucienwang.leanote.com/post/八数码——回顾BFS、双向广搜与A

https://www.cs.princeton.edu/courses/archive/fall12/cos226/assignments/8puzzle.html

http://www.cs.cmu.edu/afs/cs/Web/People/adamchik/15-121/labs/HW-7%20Slide%20Puzzle/lab.html

https://en.wikipedia.org/wiki/A*_search_algorithm