江苏省常州市第一中学林厚从。
一、概述。搜索是程序设计中的一项重要技术。许多编程问题不能用公式推导、数学计算或者模拟等方法来寻找答案，这样的问题往往有一个庞大的问题状态空间，并且给出了一些约束条件，要求寻找“解空间”中的一个或多个解。
对于这样的问题，我们需要在“状态空间树”中摸索，以某种方式或顺序来试探不同的“状态结点”，使得尽可能快的寻找到“目标结点”，或者是从“初始结点”到“目标结点”的一个路径。这也正好利用了计算机运算速度快的优点。
1、状态和状态空间。
状态一般是指客观现场信息的描述，通常用t表示，而用t0表示初始状态、tn表示目标状态。状态空间是指所有合理状态的集合，可以表示成∑=。
例1、分油问题。
问题描述]有3个油瓶，容量分别为10斤、7斤、3斤。开始时，10斤的瓶子中装满了油，其余为空，现在通过在这3个瓶子中倒来倒去，将10斤油分成2个5斤的。请编程输出一种倒油的方案。
概念解释]用一个三元组t（x10,x7,x3）来表示一种状态，其中x10，x7，x3分别表示10斤瓶、7斤瓶、3斤瓶中的油量。
初始状态：t0=（10，0，0）
目标状态：tn=（5，5，0）
约束条件：x10+x7+x3=10, 0≤x10≤10，0≤x7≤7，0≤x3≤3
状态空间：所有满足上述约束条件的状态，如t（3,7,0），t（4,4,2）
状态总数：35种。
2、产生式系统。
产生式系统由一个综合数据库、一组产生式规则和一个控制系统三个基本要素组成。其中，综合数据库是产生式系统所用的主要数据结构（常见的如：集合、数组、树、队列等）。
它主要用来表示问题的状态（初始状态、目标状态、中间状态）及状态之间的关系，它不是固定不变的，在求解过程中，它的内容会越来越多，关系也会越来越复杂。
产生式规则是对数据库进行操作的一系列规则。规则的一般形式就是：if 条件 then 操作。它实现了状态之间的转移和关联，一般也称为状态变化规则。
控制策略规定了操作的顺序，即在什么条件下用什么规则进行操作，什么条件下停止运行，它规定了问题求解的搜索策略和路线。控制策略一般分为不可撤回方式和可撤回方式（试探法、回溯法）两类。
对于分油问题，有6种倒油的可能性（6条产生式规则），分别如下：
①10斤的瓶子往7斤的瓶子里倒：条件是x10>0 and x7<7
操作是x10:=x10+x7-7;x7:=7;x3不变。
10斤的瓶子往3斤的瓶子里倒：条件是x10>0 and x3<3
操作是x10:=x10+x3-3;x3:=3;x7不变。
7斤的瓶子往3斤的瓶子里倒：略。
7斤的瓶子往10斤的瓶子里倒：略。
3斤的瓶子往7斤的瓶子里倒：略。
3斤的瓶子往10斤的瓶子里倒：略。
3、搜索中的一些问题。
搜索的问题一般有两种情况：一种是给出初始结点，要求寻找到符合约束条件的目标结点；另一种是给出初始结点和目标结点，要求找到从初始结点到目标结点的一条路径。对于解的要求也不尽相同，有的问题要求出问题的最优解，有的则要求出较优解，而有的问题要找出问题的全部解。
搜索问题中的数据结构一般要求表达要合理，要有助于计算机的处理；信息要完整，要能反应出状态的本质和状态之间的关系；还要节省存储空间，尽可能地提高搜索的速度。比如分油问题本来用一个三元组（x10,x7,x3）即可，但是为了输出方便，我们增加一个d,用来表示该结点的父结点（由谁扩展来的），即变成一个四元组（x10,x7,x3,d）。另外还用到队列来实现控制策略，当然，不能忘记状态变化过程中的重复性检查，因为大多数情况下，出现重复状态是毫无意义的，会造成死循环和空间的浪费。
二、广度优先搜索算法。
广度优先搜索是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一扩展，得到第二层结点，并逐一检查第二层结点是否包含目标结点。若没有，再用产生式规则扩展第二层结点……，如此依次扩展，检查下去，直至发现目标结点为止。
如果扩展完所有结点，都没有发现目标结点，则问题无解。
在搜索的过程中，广度优先搜索对于结点是沿着深度的断层扩展的。如果要扩展第n+1层结点，必须先全部扩展完第n层结点。对于同一层结点来说，他们对于问题的解的价值是相同的。
所以，这种搜索方法一定能保证找到最短的解序列。也就是说，第一个找到的目标结点，一定是应用产生式规则最少的。因此，广度优先搜索算法比较适合求最少步骤或者最短解序列的题目。
在具体求解过程中，广度优先一般用到“队列”这种重要的数据结构。
例2、奇怪的电梯。
问题描述]有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1≤i≤n)上有一个数字ki(0≤ki≤n)。电梯只有四个按钮：
开，关，上，下。上下的层数等于当前楼层上的那个数字ki。当然，如果不能满足要求，相应的按钮就会失灵。
例如代表了ki(k1=3,k2=3,……从1楼开始。在1楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从a楼到b楼至少要按几次按钮呢？
输入格式]输入文件共有二行，第一行为三个用空格隔开的正整数，表示n,a,b(1≤n≤200, 1≤a,b≤n)，第二行为n个用空格隔开的正整数，表示ki。
输出格式]输出文件仅一行，即最少按键次数，若无法到达，则输出-1。输入样例]
输出样例]
问题分析]因为要求的是“最少按几次按扭”，所以是很明显的广度优先搜索。每次从当前结点最多只可以扩展两个结点。
参考程序]program lift;
var n,a,b,i,x:longint;
r,r1:set of 1..200;
k,s:array[1..200]of longint;
beginreadln(n,a,b);
for i:=1 to n do read(k[i]);
for i:=1 to n do s[i]:=maxlongint;
s[a]:=0; r:=[a]; x:=1;
while (s[b]=maxlongint)and(x<>0) do
beginx:=0;r1:=[
for i:=1 to n do
if i in r then
beginif (i+k[i]<=n)and(s[i]+1begin
x:=x+1;
s[i+k[i]]:s[i]+1;
r1:=r1+[i+k[i]]
end;if (i-k[i]>=0)and(s[i]+1begin
x:=x+1;
s[i-k[i]]:s[i]+1;
r1:=r1+[i-k[i]]
end;end;
r:=r1
end;if s[b]<>maxlongint then writeln(s[b]) else writeln(-1);
end.例3、图的广（宽）度优先搜索。
问题描述]读入一个用邻接矩阵存储的无向图，输出它的广度优先遍历序列。
输入样例]
输出样例]
参考程序]program bfs;
var i,j,n,front,rear,x:integer;
g:array[1..20,1..20] of integer;
q,flag:array[0..20] of integer;
beginreadln(n);
for i:=1 to n do
beginfor j:=1 to n do read(g[i,j]);
readln;
end;for i:=1 to n do flag[i]:=0;
flag[1]:=1;q[1]:=1;
front:=1;rear:=1;
while front<=rear do
beginx:=q[front];
front:=front+1;
for i:=1 to n do
if (flag[i]=0) and (g[x,i]=1) then
begin rear:=rear+1;q[rear]:=i;flag[i]:=1;end;
end;for i:=1 to n-1 do write(q[i],‘
writeln(q[n]);
end.例4、分油问题。
参考程序]
program oil;
var i,j,x,y,z,y10,y7,y3,front,rear:integer;
q:array[1..100,1..4] of integer;
out:array[1..100,1..3] of integer;
算法初步作业
1.下面对算法描述正确的一项是 a 算法只能用自然语言来描述 b 算法只能用图形方式来表示。c 同一问题可以有不同的算法 d 同一问题的算法不同，结果必然不同。2.对赋值语句的描述正确的是 可以给变量提供初值 将表达式的值赋给变量。可以给一个变量重复赋值 不能给同一变量重复赋值。a b c d 3....
算法初步小结
课题 算法初步小结 说课稿 占书文 湖北省云梦县梦泽高中 一。说教材分析。1.地位和作用。算法初步 是人教a版高中新课标教材必修3第一章的内容，是一项新增内容，也是广大数学教师教学中普遍感到比较困难的一章。算法是数学及其应用的重要组成部分，是计算科学的重要基础。随着现代信息技术的飞速发展，算法在科学...
算法初步总结
课题 必修三第一章算法初步。课时 课时班级姓名 学习目标 知识与技能 1 通过对具体问题的分析，体会算法的思想，了解算法的含义。2.理解程序框图的三种基本逻辑结构 顺序结构 条件结构 循环结构。3.理解并掌握几种基本的算法语句 输入语句 输出语句 赋值语句 条件语句 循环语句。过程与方法 进一步体会...