东风雪铁龙2012年夏季营销终端执行手册PPT培训课件.ppt

第5章搜索求解策略
搜索的概念
状态空间的搜索策略
盲目的图搜索策略
启发式图搜索策略
与/或图搜索策略

例1 三数码问题(3 puzzle problem)。
1
2
3
3
1
2
初始棋局
目标棋局
第5章搜索求解策略
问题求解:
问题的表示。
选择一种相对合适的求解方法。
问题求解的基本方法:搜索法、归约法、归结法、推理法及产生式等。
状态空间表示法
搜索策略:
(1)盲目搜索:宽度优先搜索、深度优先搜索
(2)启发式搜索:A算法和A*搜索;
第5章搜索求解策略
搜索中需要解决的基本问题:
(1)是否一定能找到一个解。
(2)是否终止运行或是否会陷入一个死循环。
(3)找到的解是否是最佳解。
(4)时间与空间复杂性如何。
搜索的基本问题与主要过程
搜索的基本问题与主要过程
搜索的主要过程:
(1) 从初始或目的状态出发,并将它作为当前状态。
(2) 扫描操作算子集,将适用当前状态的一些操作算子作用于当前状态而得到新的状态,并建立指向其父结点的指针。
(3) 检查所生成的新状态是否满足结束状态,如果满足,则得到问题的一个解,并可沿着有关指针从结束状态反向到达开始状态,给出一解答路径;否则,将新状态作为当前状态,返回第(2)步再进行搜索。
搜索策略
1. 搜索方向:
(1) 数据驱动:从初始状态出发的正向搜索。
正向搜索——从问题给出的条件(一个用于状态转换的操作算子集合)出发。
逆向搜索:先从想达到的目的入手,看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。
(2) 目的驱动:从目的状态出发的逆向搜索。
搜索策略
(3) 双向搜索
双向搜索:从开始状态出发作正向搜索,同时又从目的状态出发作逆向搜索,直到两条路径在中间的某处汇合为止。
搜索策略
2. 盲目搜索与启发式搜索:
(1)盲目搜索:在不具有对特定问题的任何有关信息的条件下,按固定的步骤(依次或随机调用操作算子)进行的搜索。
(2)启发式搜索:考虑特定问题领域可应用的知识,动态地确定调用操作算子的步骤,优先选择较适合的操作算子,尽量减少不必要的搜索,以求尽快地到达结束状态。
搜索策略
:
求最佳解的搜索策略:
大英博物馆法(British museum);
宽度优先法(Breadth-first search);
分支界定法(Branch and Bound);
最佳图搜索法(A*);
动态规划法(Dynamic Programing);