首页 > 代码库 > 分支限界发

分支限界发

  1. 名词解释?

    扩展结点:一个正在生成孩子的结点成为扩展结点。

    活结点:一个自身已生成但其孩子还没有全部生成的的结点称为活结点。

    死结点:一个所有孩子已经生成的结点称为死结点。

  2. 宽度优先搜索思想?

    先访问顶点v,并将其标记为已访问过;然后从v出发,依次访问v的邻接点(孩子节点)w1,w2,w3..wt,如果wi(i=1,2...t)未访问过,则标记wi为已访问过,并将其插入到队列中;然后在依次从从队列中取出w1,w2,...wt访问它们的邻接点。依次类推,直到图中所有和源点v有路径相同的顶点均已访问过为止;若此时图G中任然存在未被访问过的顶点,则另选一个尚未访问过的顶点作为新的源点。重复上述过程,直到图中所有顶点均已访问过为止。

  3. 分支限界法的思想?

    分支限界法首先将根结点加入活结点表(用于存放活结点的数据结构),接着从活结点表中取出根节点,使其称为当前扩展结点,一次性生成其所有孩子结点,判断孩子结点是舍弃还是保留,舍弃那些导致不可行解或者导致非最优解的孩子结点,其余的被保留在活结点表中。再从活结点表中取出一个活结点作为当前扩展结点,重复上述过程,一直持续到找到所需的解或活结点表为空时为止。活结点表的实现通常有2种方法:一是先进先出队列;二是优先级队列

  4. 分支限界发的一般解题步骤为:

    (1)定义问题的解空间

    (2)确定问题的解空间组织结构(数或图)

    (3)搜索解空间,搜索前要定义判断标准(约束函数或限界函数),如果选用优先队列分支限界法,则必须确定优先级。

本文出自 “简答生活” 博客,转载请与作者联系!

分支限界发