八数码问题以及双向广度优先算法简述

tdzl2003

问题描述：
有一个3*3的棋盘，其中有0-8 9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态
1 2 3
4 5 6
7 8 0
到达目标状态步数最少的解。
输入方法：
例如：
input(从键盘):
1 2 3 7 4 5 8 0 6
output(向屏幕):
Step:1
1 2 3
4 5 6
7 8 0
Step:2
1 2 3
4 5 0
7 8 6
Step:3
1 2 3
4 0 5
7 8 6
Step:4
1 2 3
0 4 5
7 8 6
Step:5
1 2 3
7 4 5
0 8 6
Step:6
1 2 3
7 4 5
8 0 6


算法简述：

一、广度优先概述
一个每一步可能有多种操作的问题，当从起始状态到达目标状态，每一步操作有几种可能，但是只有正确的操作才能达到目标时（例如八数码问题），问题可以看做是一个树
如树：
1
/ \
2 3
/\ /\
4 5 6 7
如果按照1-2-4-5-3-6-7的顺序搜索，叫做深度优先，
如果按照1-2-3-4-5-6-7的顺序搜索，叫做广度优先，
(我也说不大清楚，大概的能理解吧-_-!)
广度优先的好处是得到的一定是最优解，缺点是占用空间巨大，难以处理复杂问题。
广度优先的具体算法是：
struct 类名 ar[可能结点数];
int h,r
main()
{
h=0;r=1;
while ((h<r)&&(r<可能结点数))
{
if (判断每一种可能性，如果某一种操作符合要求)
{
将ar[h]操作后记录于ar[r];
如果和目标一样，输出结果并中止程序;
r=r+1;
}
h=h+1;
}
表示没有结果。
}
二、双向广度优先概述
当一个树比较大时，广度优先占用的空间将会非常巨大
举个简单的例子，某一个问题A，大约需要20步才能解决，每一步大约有2种可能性，那么需要记录大约2^21个结点。这时候对空间和时间的要求就非常巨大，我们可以相应的优化我们的算法来解决空间和时间的需要。双向广度优先适用于那些操作可逆的广度优先问题。
当起始状态开始的每一步变化可以得到一个新的结点，相应的，从目标状态也可以得到一个新的结点，例如要从A到B，每步操作有2种可能，需要5步，则
A
/ \
C D
/ \ / \
E F G H
/ \ /\/\ /\
............
I J K L M N O B
则需要搜索近2^6个结点，然而我们如果在从起始结点向目标结点搜索的同时，也从目标结点向起始结点搜索，则会大大节省需要搜索结点的数目，空间和时间的需求都会大大减少。
A
/ \
C D
/ \ / \
E F G H
/ \
I J
||
K L
\/
M N
\/
B
那么，A-C-E-J(L)-M-B就是我们所求的最优路径。具体实现方法参见第三节。
三、本程序概述
将一个状态表示为一个数组，
为了方便起见，将
1 2 3
4 5 6
7 8 0
表示为 123456780 状态1.0
目标状态
1 2 3
7 4 5
8 0 6
表示为 123745806 状态2.0
由状态1.0（起始状态）可以得到以下几种：
123450786 状态1.1
123456708 状态1.2
由状态2.0（目标状态）可以得到以下几种：
123705846 状态2.1
123745086 状态2.2
123745860 状态2.3
由状态1.1可以得到以下几种：
.
.
.
由状态2.1可以得到以下几种：
.
.
.
.
.
.
由状态1.n可以得到以下几种：
...... 状态1.i
由状态2.n可以得到以下几种：
...... 状态2.j发现和状态2.i相同，找到结果。根据2.j和1.j的父树输出结果。

一、广度优先概述
一个每一步可能有多种操作的问题，当从起始状态到达目标状态，每一步操作有几种可能，但是只有正确的操作才能达到目标时（例如八数码问题），问题可以看做是一个树
如树：
1
/ \
2 3
/\ /\
4 5 6 7
如果按照1-2-4-5-3-6-7的顺序搜索，叫做深度优先，
如果按照1-2-3-4-5-6-7的顺序搜索，叫做广度优先，
(我也说不大清楚，大概的能理解吧-_-!)
广度优先的好处是得到的一定是最优解，缺点是占用空间巨大，难以处理复杂问题。
广度优先的具体算法是：
struct 类名 ar[可能结点数];
int h,r
main()
{
h=0;r=1;
while ((h<r)&&(r<可能结点数))
{
if (判断每一种可能性，如果某一种操作符合要求)
{
将ar[h]操作后记录于ar[r];
如果和目标一样，输出结果并中止程序;
r=r+1;
}
h=h+1;
}
表示没有结果。
}
二、双向广度优先概述
当一个树比较大时，广度优先占用的空间将会非常巨大
举个简单的例子，某一个问题A，大约需要20步才能解决，每一步大约有2种可能性，那么需要记录大约2^21个结点。这时候对空间和时间的要求就非常巨大，我们可以相应的优化我们的算法来解决空间和时间的需要。双向广度优先适用于那些操作可逆的广度优先问题。
当起始状态开始的每一步变化可以得到一个新的结点，相应的，从目标状态也可以得到一个新的结点，例如要从A到B，每步操作有2种可能，需要5步，则
A
/ \
C D
/ \ / \
E F G H
/ \ /\/\ /\
............
I J K L M N O B
则需要搜索近2^6个结点，然而我们如果在从起始结点向目标结点搜索的同时，也从目标结点向起始结点搜索，则会大大节省需要搜索结点的数目，空间和时间的需求都会大大减少。
A
/ \
C D
/ \ / \
E F G H
/ \
I J
||
K L
\/
M N
\/
B
那么，A-C-E-J(L)-M-B就是我们所求的最优路径。具体实现方法参见第三节。
三、本程序概述
将一个状态表示为一个数组，
为了方便起见，将
1 2 3
4 5 6
7 8 0
表示为 123456780 状态1.0
目标状态
1 2 3
7 4 5
8 0 6
表示为 123745806 状态2.0
由状态1.0（起始状态）可以得到以下几种：
123450786 状态1.1
123456708 状态1.2
由状态2.0（目标状态）可以得到以下几种：
123705846 状态2.1
123745086 状态2.2
123745860 状态2.3
由状态1.1可以得到以下几种：
.
.
.
由状态2.1可以得到以下几种：
.
.
.
.
.
.
由状态1.n可以得到以下几种：
...... 状态1.i
由状态2.n可以得到以下几种：
...... 状态2.j发现和状态2.i相同，找到结果。根据2.j和1.j的父树输出结果。

以下为我写的源程序，在TC++3.0下运行通过，在VC下运行需要稍做修改。（注：如果在VC下运行，还可以适当增加数组大小）