高中信息技术 浙教版选修5 5.3启发式搜索(共13张PPT)

启发式搜索 1 启发函数的作用 在启发式搜索中，通常用_______来表示启发信息。 启发函数 3 在重排九宫问题中，如果把当前棋盘状态与棋盘目标状态所对应的棋子逐一进行比较，可得到位置不同的棋子个数，把这个数值作为当前棋盘状态与棋盘目标状态的差距。我们把该差距作为重排九宫问题的启发函数，并用H(x)表示，即： H(x)=节点x的棋盘状态与目标棋盘状态的差距 4 例如，下图画出了当前棋盘状态C3和棋盘目标状态Sg。我们把这两个棋盘状态的对应棋子相比较，可看到有两个对应棋子的位置不同（棋子1和棋子8），因此，棋盘状态C3的启发函数值是2，即： H(C3)=2 一个棋盘状态的启发函数值的求法 5 可以看出，H(x)值越小，节点x就越接近目标节点，如果H(x)=0，则节点x为目标节点。 因此，选择这个启发函数指导搜索时，为了缩小搜索范围，加快找到目标节点的速度，可选择启发函数值最小的分支节点进行搜索。 6 2 重排九宫问题的启 发式搜索过程 观摩 打开演示光盘，运行“\第四章\搜索过程\pfs.ppt”，观摩右图所示的重排九宫问题树的一种启发式搜索过程： 标有启发函数值的重排 九宫问题状态树 8 （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，便结束搜索过程。 9 3 启发函数的选择 用启发函数H(x)(H(x)=节点x的棋盘状态与目标棋盘状态的差距）指导搜索，得到的搜索路径不一定是最短的，我们还可以选择其他更好的启发函数。因此，选择启发函数是启发式搜索一个关键而复杂的问题。 11 练习 在表中写出基本搜索、启发式搜索的特点。 基本搜索 启发式搜索 12 THE END $$