广度和深度优先搜索

《广度和深度优先搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、◆2深度优先搜索和广度优先搜索——产生式系统深度优先搜索和广度优先搜索一、产生式系统首先通过一个具体事例说明什么是产生式系统。[例题4-1八数码难题]在3X3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是：找到一种移动方法，实现从初始布局到目标布局的转变。例如输入：（代表从前一布局到后一布局）283164705123804765[分析]状态表示：用二维数组来表示布局。(si,sj)表示第i行、第j列上放的棋子数字。空格用0表示。产生规则：

2、原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察，也可看做空格向四周移动。这样处理更便于编程。如果空格位置在(si,sj)，则有四条规则：(1)空格向上移动:Ifsi-1>=1thench(si,sj):=ch(si-1,sj);ch(si-1,sj):=0(2)空格向下移动:Ifsi+1<=3thench(si,sj):=ch(si+1,sj);ch(si+1,sj):=0(3)空格向左移动:Ifsj-1>=1thench(si,sj):=ch(si,sj-1);ch(si,sj-1):=0(4)

3、空格向右移动:Ifsj+1<=3thench(si,sj):=ch(si,sj+1);ch(si,sj+1):=0搜索策略：(1)把初始状态作为当前状态；(2)从当前状态出发，运用四条移动规则，产生新的状态；(3)判断新的状态是否达到目的状态，如果是，转(5)；(4)把新的状态记录下来，取出下一个中间状态作为当前状态，返回(2)；(5)输出从初始状态到目标状态的路径，结束。这个例子就是产生式系统。产生式系统的组成：产生式系统是由三个基本要素组成的：一个综合数据库（GOLBLEDATABASE），一组产生式规则（

4、Setofrules），和一个控制系统（ControlSystem）。1、综合数据库:它是产生式系统所有的主要数据结构。它主要表示问题的状态，即初始状态，目标状态，和中间状态等，以及状态之间的关系。它不是固定不变的，在求解过程中，它的内容将越来越多，状态之间的关系也越来越复杂。经常用来表示数据库的数据结构有串，集合，数组，树，表，记录，队列等。[例题4-1八数码难题]使用数组这种数据结构表示状态，若压缩数据存储，把二维数组压缩为串，则数据库采用的数据结构就是串。2、产生式规则：是对数据库进行操作的一系列规则。规

5、则的一般形式是：if条件then操作即满足应用的先决条件后，就对数据库实行后面的操作。3、控制策略：它规定了操作的顺序既在什么条件下用什么规则进行操作，什么条件下停止操作，即它规定了问题的搜索策略和路线。一般的，控制策略分为两大类：3.1不可撤回方式(IRREVOCABLE)3.2试探法(TENTATIVE)：3.2.1回溯法(BACKTRACKING)3.2.2图搜索法(GRAPH-SEARCH)4、搜索策略：搜索策略有两种基本方式：一种是不考虑给定问题的特有性质，按事先规定好的顺序依次运用规则，这是一种盲目

6、搜索的方法，或称为无信息引导的搜索。另一种是考虑问题的特有性质，优先选用较合适的数据和规则，这称为启发式搜索，或有信息引导的搜索。目前，从这两种基本方式出发，已创造出多种具体的搜索方法。归纳起来有以下几种：◆2深度优先搜索和广度优先搜索——产生式系统(一)求任一路径的搜索策略：回朔法(Backtracking)、爬山法(Hillclimbing)、深度优先搜索法(Depth-first)、广度优先搜索法(Breadth-first)、限定范围搜索法(Beamsearch)、最优策略(Bestfirst)(二)求

7、最优路径的搜索策略：大英博物馆法(BritishMuseum)、分支定界法(BranchandBound)、动态规划法(DynamicProgramming)、最佳图搜索法(A*)(三)与或图搜索法：一般与或图搜索法(AO*)、极大极小法(Minimax)、a-b剪枝法(Alpha-betaPruning)、启发式剪枝法(HeuristicPurning)产生式系统的应用[例题4—2]有N枚硬币(N为偶数)正面朝上排成一排，每次将N—1枚硬币翻过来放在原位置上，不断地重复上述过程，直到最后全部硬币翻成反面朝上为

8、止。编程让计算机把翻币的最简过程及翻币次数打印出来(用x代表正面，O代表反面)。[分析]状态表示：显然可以用一个数组a描述当前的状态，当元素a[i]=“*”时，第i枚硬币朝上，a[i]=“o”时，第i枚硬币朝下。移动规则：根据题意每次翻动N—1枚硬币，相当于固定一枚硬币，把其他各枚硬币翻个。所以每次有n种操作方案：固定第i{i∈1．．n}枚硬币，使其他硬币翻面。搜索策略：把初始状态(即