1、Artificial Intelligence Principles and Applications第 5 章 搜索求解策略教材：王万良 人工智能及其应用 （第 2版）高等教育出版社， 2008. 6第 5章 搜索求解策略o 5.1 搜索的概念o 5.2 状态空间的搜索策略o 5.3 盲目的图搜索策略o 5.4 启发式图搜索策略o 5.5 与 /或 图搜索策略2第 5章 搜索求解策略5.1 搜索的概念o 5.2 状态空间知识表示方法o 5.3 盲目的图搜索策略o 5.4 启发式图搜索策略o 5.5 与 /或 图搜索策略35.1 搜索的概念 o 问题求解：o 问题的表示。 o 选择一种相对合适
2、的求解方法。o 问题求解的基本方法： 搜索法 、归约法、归结法、推理法及产生式等。45.1 搜索的概念o 5.1.1 搜索的基本问题与主要过程o 5.1.2 搜索策略55.1.1 搜索的基本问题与主要过程 o 搜索中需要解决的基本问题 ：（ 1）是否一定能找到一个解。（ 2）是否终止运行或是否会陷入一个死循环。（ 3）找到的解是否是最佳解。（ 4）时间与空间复杂性如何。65.1.1 搜索的基本问题与主要过程o 搜索的主要过程 ：(1) 从初始或目的状态出发，并将它作为当前状态。(2) 扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针 。(3)
3、检查所生成的新状态是否满足结束状态，如果满足，则得到问题的一个解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第 (2)步再进行搜索。 75.1.2 搜索策略o 1. 搜索方向 ：(1) 数据驱动 ：从初始状态出发的正向搜索。 正向搜索 从问题给出的条件（一个用于状态转换的操作算子集合）出发。逆向搜索 ：先从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。(2) 目的驱动 ：从目的 状态出发的逆向搜索。85.1.2 搜索策略o 1. 搜索方向 ：(3) 双向搜索 双向搜索：从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止。95.1.2 搜索策略o 2. 盲目搜索与启发式搜索 :（ 1）盲目搜索 ：在不具有对特定问题的任何有关信息的条件下，按固定的步骤（依次或随机调用操作算子）进行的搜索。 （ 2）启发式搜索 ：考虑特定问题领域可应用的知识，动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束 状态。10
