唐山做网站公司汉狮价格,创意设计人才网,wordpress 分类文章数,wordpress 问答插件2LIFO和FIFO分枝-限界法 采用宽度优先策略#xff0c;在生成当前E-结点全部儿子之后再生成其它活结点的儿子#xff0c;且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。两种基本设计策略#xff1a; FIFO检索#xff1a;活结点表采用队列#x…LIFO和FIFO分枝-限界法 采用宽度优先策略在生成当前E-结点全部儿子之后再生成其它活结点的儿子且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。两种基本设计策略 FIFO检索活结点表采用队列LIFO检索活结点表采用栈。 如采用FIFO分支限界法检索4-皇后问题的状态空间树 LC-检索Least CostA*算法 LIFO和FIFO分枝-限界法存在的问题 对下一个E-结点的选择规则过于死板。对于有可能快速检索到一个答案结点的结点没有给出任何优先权如结点30。 解决做某种排序让可以导致答案结点的活结点排在前面 。 如何排序 寻找一种“有智力”的排序函数C(·)来选取下一个E 结点加快到达一答案结点的检索速度。 如何衡量结点的优先等级 对于任一结点用该结点导致答案结点的成本代价 来衡量该结点的优先级——成本越小越优先。 对任一结点X可以用两种标准来衡量结点的代价 1在生成一个答案结点之前子树 X 需要生成的结点数。 2在子树 X 中离 X 最近的那个答案结点到 X 的路径长度。 C(x) “有智力”的排序函数依据成本排序优先选择成本最小的活结点作为下一个E结点进行扩展。 C(·)又称为“结点成本函数” n 结点成本函数C(X)的取值 1如果X是答案结点则C(X)是由状态空间树的根结点到X 的成本(即所用的代价可以是级数、计算复杂度等)。 2) 如果X不是答案结点且子树X不包含任何答案结点则 C(X)∞ 3) 如果X不是答案结点但子树X包含答案结点则C(X)应等于子树X中具有最小成本的答案结点的成本。 计算结点X的代价通常要检索子树X才能确定因此 计算C(X)的工作量和复杂度与解原始问题是相同的。 n 计算结点成本的精确值是不现实的——相当于求解 原始问题。怎么办 n 结点成本的估计函数包括两部分h(X)和 是由X到达一个答案结点所需成本的估计函数。 性质单纯使用选择E结点会导致算法偏向纵深检查。 故引进h(X)改进成本估计函数h(x)根结点到结点X的成本——已发生成本。 f(·)是一个非降函数。 非零的f(·)可以减少算法作偏向于纵深检查的可能性 它强使算法优先检索更靠近答案结点但又离根更近的结点。 LC-检索选择值最小的活结点作为下一个E-结点的状态空间树检索方法。 特例 BFS 依据级数来生成结点 D-Search令f (h(X)) 0所以当Y是X的一个儿子时 总有 LC分支-限界检索带有限界函数的LC-检索 LEAST(E)在活结点表中找一个具有最小成本估计值的活结点从活结点表中删除这个结点并将此结点放在变量E中返回。 ADD(X)将新的活结点X加到活结点表中。 活结点表以优先队列存放
不同估算函数对于结果的影响 1、当估算的距离等于实际距离时一路下去肯定就是最优的解而且基本不用扩展其它的点。 2、如果估算距离小于实际距离时则到最后一定能找到一条最短路径但是有可能会经过很多无效的点。(过于乐观以h(X)为主) 3、如果估算距离大于实际距离时有可能就很快找到一条通往目的地的路径但是却不一定是最优的解。过于悲观以g(X)为主 成本函数在分支-限界算法中的应用 假定每个答案结点X有一个与其相联系的c(X)且找成本最小的答案结点。 1最小成本的下界为X的成本估计函数。当时 给出了由结点X求解的最小成本的下界作为启发性函数减 少选取E结点的盲目性。 2最小成本的上界 。最小成本的上界 定义U为最小成本解的成本上界则对具有的所有活结点可以被杀死从而可以进一步使算法加速减少求解的盲目性。 最小成本上界U的求取 1初始值利用启发性方法赋初值或置为∞ 2每找到一个新的答案结点后修正UU取当前最小成本值。 注只要U的初始值不小于最小成本答案结点的成本利用U就不会杀死可以到达最小成本答案结点的活结点。
利用分枝-限界算法求解最优化问题 可行解类似于n-元组的构造把可行解可能的构造过程用 “状态空间树”表示出来。 最优解把对最优解的检索表示成对状态空间树答案结点的 检索。 成本函数每个结点赋予一个成本函数c(X) 并使得代表最优解的答案结点的c(X)是所有结点成本的最小值 。
