<html>
<head>
<title></title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<style type="text/css">
<!--
body { font-family: "宋体_GB2312"; font-size: 14pt; font-style: normal; color: #000000}
-->
</style>
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p><font size="5">2.1状态空间图</font><a name=1></a></p>
<p>通过例子引入状态图的概念:</p>
<p>一个简单的例子:</p>
<p>设有三枚钱币,其排列处在“正,正,反”状态,现允许每次可翻动其中任意一个钱币,问只允许操作三次的情况下,如何翻动钱币使其变成“正,正,正”或“反,反,反”状态。</p>
<p><font color="#FF0000">若“正面”用“1”表示,“反面”用“0”表示,则问题化成求解从初始状态(1,1,0)到目标状态(1,1,1)或(0,0,0)的路径问题,且该路径的长度为3。</font></p>
<p><font color="#FF0000">(1,1,0)--------->(1,1,1)或(1,1,0)--------->(0,0,0)</font></p>
<p>另一个例子--八数码问题(8-puzzle problem)</p>
<p> 在一个3*3的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一个格,且有一个空格。这些数码可在棋盘上移动,其移动规则是:与空格相邻的数码方可移入空格。现在的问题是对于给定的初始棋局和目标棋局(如下图),给出移动的序列。</p>
<table width="48%" border="0" align="center">
<tr>
<td height="181">
<table width="75%" border="1" align="center">
<tr>
<td>
<div align="center">2</div>
</td>
<td>
<div align="center">8</div>
</td>
<td>
<div align="center">3</div>
</td>
</tr>
<tr>
<td>
<div align="center">1</div>
</td>
<td>
<div align="center"></div>
</td>
<td>
<div align="center">4</div>
</td>
</tr>
<tr>
<td>
<div align="center">7</div>
</td>
<td>
<div align="center">6</div>
</td>
<td>
<div align="center">5</div>
</td>
</tr>
</table> <p align="center">初始棋局S0</p>
</td>
<td height="181">
<table width="75%" border="1" align="center">
<tr>
<td>
<div align="center">8</div>
</td>
<td>
<div align="center">1</div>
</td>
<td>
<div align="center">3</div>
</td>
</tr>
<tr>
<td>
<div align="center">2</div>
</td>
<td>
<div align="center"></div>
</td>
<td>
<div align="center">4</div>
</td>
</tr>
<tr>
<td>
<div align="center">7</div>
</td>
<td>
<div align="center">6</div>
</td>
<td>
<div align="center">5</div>
</td>
</tr>
</table> <p align="center">目标棋局Sg</p>
</td>
</tr>
</table>
<div align="center"></div>
<p>以上两问题虽然内容不同,但抽象地来看,它们都是在某个有向图中寻找目标或路径的问题。人工智能科学中,把这种描述问题的有向图称为状态空间图,简称<font color="#FF0000">状态图</font>(state
diagram)。因为图中的一个<font color="#FF0000">结点(node)</font>代表问题中的一种格局或状态;边表示两个结点之间的某种联系(某种操作、规则、变换、算子、通道或关系)。在状态图中,从初始结点到目标结点的一条<font color="#FF0000">路径</font>或者所找到的<font color="#FF0000">目标结点</font>就是相应的一个<font color="#FF0000">解。</font></p>
<p><font color="#FF0000">许多智力问题(Hanoi塔,旅行商问题,N皇后问题,农夫过河问题)都可以归结成状态图问题。</font></p>
<p>例子一的状态图:</p>
<p align="center"><img src="money.jpg" tppabs="http://star.aust.edu.cn/~xjfang/p-ai/images/money.jpg" width="648" height="217"></p>
<p align="left">例子二的部分状态图:</p>
<p align="center"><img src="searchtree.jpg" tppabs="http://star.aust.edu.cn/~xjfang/p-ai/images/searchtree.jpg" width="415" height="470"></p>
<p align="left"><b><font color="#0000FF">练习:N皇后问题就是在N*N的棋盘上放置N个皇后的方法解,满足每行、每列和对角线上只允许出现一个皇后,例如以下是8皇后问题的解。要求画出4皇后问题的状态空间图,然后求解目标。</font></b></p>
<table width="29%" border="1" align="center" cellspacing="1" cellpadding="0" bordercolor="#000000">
<tr>
<td>
<div align="center">Q</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x </div>
</td>
<td>
<div align="center">x </div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
</tr>
<tr>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">Q</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
</tr>
<tr>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">Q</div>
</td>
</tr>
<tr>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">Q</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
</tr>
<tr>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">Q</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
</tr>
<tr>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">Q</div>
</td>
<td>
<div align="center">x</div>
</td>
</tr>
<tr>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">Q</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
</tr>
<tr>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">Q</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
<td>
<div align="center">x</div>
</td>
</tr>
</table>
<p><font size="5">2.2盲目式搜索算法</font><a name=2></a></p>
<p><font color="#FF0000">搜索</font>的概念:从初始结点出发沿着与之相连的边试探地�