第3章囹搜索与问题求解 8 8 3 1a4今|2 5 6 5 初始棋局 目标棋局 图3-3八数码问题示例
第 3 章 图搜索与问题求解 图 3-3 八数码问题示例
第3章图搜索与问题求解 3.1.2状态图搜索 1.搜索方式 用计算机来实现状态图的搜索,有两种最基本的方式 树式搜索和线式搜索。 所谓树式搜索,形象地讲就是以“画树”的方式进行搜索。 即从树根(初始节点)岀发,一笔一笔地描出一棵树来。准确地 讲,树式搜索就是在搜索过程中记录所经过的所有节点和边。 所以,树式搜索所记录的轨迹始终是一棵“树”,这棵树也就 是搜索过程中所产生的搜索树
第 3 章 图搜索与问题求解 3.1.2 状态图搜索 1. 用计算机来实现状态图的搜索, 有两种最基本的方式： 树式搜索和线式搜索。 所谓树式搜索, 形象地讲就是以“画树”的方式进行搜索。 即从树根(初始节点)出发, 一笔一笔地描出一棵树来。准确地 讲, 树式搜索就是在搜索过程中记录所经过的所有节点和边。 所以, 树式搜索所记录的轨迹始终是一棵“树” , 这棵树也就 是搜索过程中所产生的搜索树
第3章囹搜索与问题求解 所谓线式搜索,形象地讲就是以“画线”的方式进行搜索。 准确地讲,线式搜索在搜索过程中只记录那些当前认为是处在 所找路径上的节点和边。所以,线式搜索所记录的轨迹始终是 条“线”(折线)
第 3 章 图搜索与问题求解 所谓线式搜索, 形象地讲就是以“画线”的方式进行搜索。 准确地讲, 线式搜索在搜索过程中只记录那些当前认为是处在 所找路径上的节点和边。所以,线式搜索所记录的轨迹始终是 一条“线”(折线)
第3章囹搜索与问题求解 线式搜索的基本方式又可分为不回溯的和可回溯的两种。 不回溯的线式搜索就是每到一个“叉路口”仅沿一条路继续前 进,即对每一个节点始终都仅生成一个子节点(如果有子节点 的话)。生成一个节点的子节点也称对该节点进行扩展。这样, 如果扩展到某一个节点,该节点恰好就是目标节点,则搜索成 功;如果直到不能再扩展时,还未找到目标节点,则搜索失败。 可回溯的线式搜索也是对每一个节点都仅扩展一条边,但当不 能再扩展时,则退回一个节点,然后再扩展另一条边(如果有 的话)。这样,要么最终找到了目标节点,搜索成功;要么 直回溯到初始节点也未找到目标节点,则搜索失败
第 3 章 图搜索与问题求解 线式搜索的基本方式又可分为不回溯的和可回溯的两种。 不回溯的线式搜索就是每到一个“叉路口”仅沿一条路继续前 进, 即对每一个节点始终都仅生成一个子节点(如果有子节点 的话)。 生成一个节点的子节点也称对该节点进行扩展。这样, 如果扩展到某一个节点, 该节点恰好就是目标节点,则搜索成 功；如果直到不能再扩展时, 还未找到目标节点,则搜索失败。 可回溯的线式搜索也是对每一个节点都仅扩展一条边,但当不 能再扩展时, 则退回一个节点, 然后再扩展另一条边(如果有 的话)。 这样, 要么最终找到了目标节点, 搜索成功；要么一 直回溯到初始节点也未找到目标节点, 则搜索失败
第3章囹搜索与问题求解 由上所述可以看出,树式搜索成功后,还需再从搜索树中 找出所求路径,而线式搜索只要搜索成功,则“搜索线”就是 所找的路径,即问题的解。 那么,又怎样从搜索树中找出所求路径呢?这只需在扩 展节点时记住节点间的父子关系即可。这样,当搜索成功时, 从目标节点反向沿搜索树按所作标记追溯回去一直到初始节点, 便得到一条从初始节点到目标节点的路径,即问题的一个解
第 3 章 图搜索与问题求解 由上所述可以看出, 树式搜索成功后, 还需再从搜索树中 找出所求路径, 而线式搜索只要搜索成功, 则“搜索线”就是 所找的路径, 即问题的解。 那么, 又怎样从搜索树中找出所求路径呢？ 这只需在扩 展节点时记住节点间的父子关系即可。 这样, 当搜索成功时, 从目标节点反向沿搜索树按所作标记追溯回去一直到初始节点, 便得到一条从初始节点到目标节点的路径, 即问题的一个解