文档介绍：NOIP、产生式系统、宽度优先搜索、深度优先搜索双向搜索可逆性、“汇合”的复杂度预处理数学分析、排序、合法状态产生剪枝可行性、最优性、有序性、对称性记忆化搜索启发索式搜目录显式图与隐式图图、产生式系统、宽度优先搜索、深度优先搜索双向搜索可逆性、“汇合”的复杂度预处理数学分析、排序、合法状态产生剪枝可行性、最优性、有序性、对称性记忆化搜索启发式搜索顶点表示问题的一个状态边表示状态之间的转化规则隐式图和产生式系统只有初始状态和变化规则,在搜索的过程中产生出新状态。搜索就是按某次序遍历所有可能有“解”的顶点搜索算法-----显式图与隐式图举例1:人、狼、羊、草过河问题变化规则:状态表示:搜索算法-----显式图与隐式图羊和草不能单独在一边狼和羊不能单独在一边船最多2物,要人划?举例1:人、狼、羊、草过河问题状态表示:搜索算法-----显式图与隐式图两个集合,分别表示两岸情况4位的二进制数,0---左,1---右其它…举例1:人、狼、羊、草过河问题显式图:搜索算法-----显式图与隐式图0000111110011100001001100101001110101011111001001101000101111000举例2:N个数,排成一行,要求相邻两个数互质。变化规则:状态表示:搜索算法-----显式图与隐式图相邻两数互质?举例2:N个数,排成一行,要求相邻两个数素质。状态表示:隐式图:显式产生状态过程本身就是搜索了。只能利用规则产生系统在搜索中进入相邻“节点”---产生合法状态。搜索算法-----显式图与隐式图已经选中的数,排成一列其它…具体参见《NOIP基础数据结构》ppt相关页《NOIP图的基础算法》ppt相关页搜索算法-----BFS与DFS