实验项目二 搜索策略 一、 知识点 搜索就是要寻找一个操作序列,使问题从初始状态转换到目标状态。这个操作序列就是目标的解。换言之,就是根据问题的实际情况,按照一定的策略或规则,从知识库中寻找可利用的知识,从而构造一条使问题获得解决的推理路线的过程。 本次实验设计实现经典的盲目搜索策略。盲目搜索策略的一个共同特点是它们的搜索路线是已经决定好的,没有利用被求解问题的任何特征信息,在决定要被扩展的节点时,并没有考虑该节点到底能否可能出现在解的路径上,也没有考虑它是否有利于问题的求解以及所求的解是否为最优解。广度优先搜索、深度优先搜索和有界深度优先搜索都属于盲目搜索策略 1 、广度优先搜索 广度优先搜索又称为宽度优先搜索,是一种先生成的节点先扩展的简单策略。 其基本思想是:从初始节点 S0 ,开始逐层对节点进行扩展并考察它是否为目标节点,在第 n 层节点还没有全部扩展并考察之前,不对第 n+1 层节点进行扩展。 2 、深度优先搜索 深度优先搜索总是先扩展后生成的节点。基本思想是:从初始节点 S0 开始,在其子节点中选择一个最新生成的节点进行考察,如果该子节点不是目标节点且可以扩展,则扩展该子节点,然后再在此子节点的子节点中选择一个最新生成的节点进行考察,依此向下搜索,当到达某个子节点,此子节点既不是目标节点又不能继续扩展时,才选择其兄弟节点进行考察。 二、 实验目的 学习使用盲目搜索策略中的广度优先或者深度优先策略解决三阶 梵塔 问题或八数码问题。 三、 实验内容 使用广度优先或者深度优先策略解决三阶 梵塔问题或八数码问题,要求: ( 1 )设定初始与终止状态,确定搜索策略。 ( 2 ) Output :输出每一步搜索过程,如果无解则给出提示。 四、 实验提交 提交文件以姓名命名,包括: ( 1 )提交 word 实验报告,包括实验题目与实验内容,实验输入与输出,执行过程等的截图。 ( 2 )提交源代码压缩文件。 注意提交组员姓名、学号。 实验题目二.docx