粤教版选修5 人工智能初步第四章问题求解4.3 启发式搜索精品ppt课件

展开

这是一份粤教版选修5 人工智能初步第四章问题求解4.3 启发式搜索精品ppt课件，共12页。PPT课件主要包含了启发函数的作用，启发函数的选择等内容，欢迎下载使用。

在启发式搜索中，通常用_______来表示启发信息。
在重排九宫问题中，如果把当前棋盘状态与棋盘目标状态所对应的棋子逐一进行比较，可得到位置不同的棋子个数，把这个数值作为当前棋盘状态与棋盘目标状态的差距。我们把该差距作为重排九宫问题的启发函数，并用H(x)表示，即： H(x)=节点x的棋盘状态与目标棋盘状态的差距
例如，下图画出了当前棋盘状态C3和棋盘目标状态Sg。我们把这两个棋盘状态的对应棋子相比较，可看到有两个对应棋子的位置不同（棋子1和棋子8），因此，棋盘状态C3的启发函数值是2，即： H(C3)=2
一个棋盘状态的启发函数值的求法
可以看出，H(x)值越小，节点x就越接近目标节点，如果H(x)=0，则节点x为目标节点。因此，选择这个启发函数指导搜索时，为了缩小搜索范围，加快找到目标节点的速度，可选择启发函数值最小的分支节点进行搜索。
重排九宫问题的启发式搜索过程
打开演示光盘，运行“\第四章\搜索过程\pfs.ppt”，观摩右图所示的重排九宫问题树的一种启发式搜索过程：
标有启发函数值的重排九宫问题状态树
（1）搜索从棋盘初始状态SO开始，SO不是目标状态，考察它的子节点。（2）SO的子节点B1、B2、B3、B4都不是目标状态，从这四个节点中，选择出一个启发函数值最小的节点，继续考察它的子节点。这里，B1和B2的启发函数值都最小，因此B1和B2都可选，假如我们选择B1，继续考察B1的子节点。（3）B1的子节点C1、C2还不是目标状态，选择启发函数值最小的C1，继续考察C1的子节点。（4）C1的子节点只有D1，并且D1不是目标状态，继续考察D1的子节点。如此继续，直到找到目标节点Sg，便结束搜索过程。
用启发函数H(x)(H(x)=节点x的棋盘状态与目标棋盘状态的差距）指导搜索，得到的搜索路径不一定是最短的，我们还可以选择其他更好的启发函数。因此，选择启发函数是启发式搜索一个关键而复杂的问题。