文档介绍：广度优先搜索算法(Breadth-First-Search)使用计算机求解的问题中,有许多问题是无法用数学公式进行计算推导采用模拟方法来找出答案的。这样的问题往往需要我们根据问题所给定的一些条件,在问题的所有可能解中用某种方式找出问题的解来,这就是所谓的搜索法或搜索技术。通常用搜索技术解决的问题可以分成两类:一类问题是给定初始结点,要求找出符合约束条件的目标结点;另一类问题是给出初始结点和目标结点,找出一条从初始结点到达目标结点的路径。这里来讨论一下广度优先搜索法。广度优先搜索算法一般来说,可以采用搜索算法解决的这类问题的特点是:,状态是问题可能出现的每一种情况。全体状态所构成的状态空间是有限的,问题规模较小。,可以从一个状态按照问题给定的条件,转变为另外的一个或几个状态。,并且有明确的一个或多个目标状态。:根据给定的初始状态找出目标状态,或根据给定的初始状态和结束状态,找出一条从初始状态到结束状态的路径。采用广度优先搜索算法解答问题时,需要构造一个表明状态特征和不同状态之间关系的数据结构,这种数据结构称为结点。根据问题所给定的条件,从一个结点出发,可以生成一个或多个新的结点,这个过程通常称为扩展。结点之间的关系一般可以表示成一棵树,它被称为解答树。搜索算法的搜索过程实际上就是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。广度优先搜索算法中,解答树上结点的扩展是沿结点深度的“断层”进行,也就是说,结点的扩展是按它们接近起始结点的程度依次进行的。首先生成第一层结点,同时检查目标结点是否在所生成的结点中,如果不在,则将所有的第一层结点逐一扩展,得到第二层结点,并检查第二层结点是否包含目标结点,...对长度为n+1的任一结点进行扩展之前,必须先考虑长度为n的结点的每种可能的状态。因此,对于同一层结点来说,求解问题的价值是相同的,我们可以按任意顺序来扩展它们。这里采用的原则是先生成的结点先扩展。广度优先搜索算法中,为了便于进行搜索,要设置一个表存储所有的结点,为了满足先生成的结点先扩展的原则,存储结点的表一般设计成队列的数据结构。搜索过程中不断地从队列头取出结点进行扩展。对生成的新结点,要检查它是否已在队列中存在,还要检查它是否目标结点。如果新结点是目标结点,则搜索成功,程序结束;若新结点不是目标结点,并且未曾在队列中出现过,则将它加入到队列尾,否则将它丢弃,再从队列头取出结点进行扩展......。最终可能产生两种结果:找到目标结点,或扩展完所有结点而没有找到目标结点。如果目标结点存在于解答树的有限层上,广度优先搜索算法一定能保证找到一条通向它的最佳路径,因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径,则要保存每个结点的来源,也就是它是从哪一个节点扩展来的。对于不同的问题,用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否目标结点和是否重复结点的判断等方面则有所不同,对具体的问题需要进行具体分析。                  '定义一个结点数据类型        ....           '根据具体问题确定所需的数据类型        EndTypeDimState()AsTNode    '定义TNode类型的数组,作为存储结点的队列PrivateSubBFS()                    'BFS算法主程序  DimTempAsTNode                'TNode型临时结点  DimHeadAsInteger,TailAsInteger'队列头指针和尾指针  ReDimState(0)  InputData                 '从文件中读入数据进行初始化  Head=0  Tail=0                  '队列头指针和尾指针都指向队列头  Do  While  Head<=Tail                '队列非空时循环      '根据具体问题确定一个结点怎样扩展  Temp=State(0)                       '取队列头的结点  If  ExtendThen       '如果该结点可以扩展则产生一个新结点  If  NotRepeatThen          '如果新结点未曾在队列中出现过    Tail=Tail+1                  '将新结点加入队列尾    ReDimPreserveState(Tail)    State(Tail)=Temp    State(Tai