返回首页
当前位置: 主页 > 网络编程 > 其他实例教程 >

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

时间:2011-05-20 21:07来源:知行网www.zhixing123.cn 编辑:麦田守望者

 

问题描述:

有一个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的顺序搜索,叫做广度优先,
(我也说不大清楚,大概的能理解吧-_-!)
广度优先的好处是得到的一定是最优解,缺点是占用空间巨大,难以处理复杂问题。
广度优先的具体算法是:
1.struct /*类名*/ ar[/*可能结点数*/]; 2.int h,r 3.main() 4.{ 5. h=0;r=1; 6. while ((h<r)&&(r</*可能结点数*/)) 7. { 8. if (/*判断每一种可能性,如果某一种操作符合要求*/) 9. { 10. //将ar[h]操作后记录于ar[r]; 11. //如果和目标一样,输出结果并中止程序; 12. r=r+1; 13. } 14. h=h+1; 15. } 16. //表示没有结果。 17.}

二、双向广度优先概述

当一个树比较大时,广度优先占用的空间将会非常巨大
举个简单的例子,某一个问题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的父树输出结果。
 

 

------分隔线----------------------------
标签(Tag):人工智能 人机交互技术
------分隔线----------------------------
推荐内容
猜你感兴趣
博聚网