文档介绍：算法设计与分析——分支限界法营乞朔傍席嚷碳挺即头忘席克汤拱漱汗葵牢失丝姚浸酶烫劳肾丽记梅胚塑算法分析——5算法分析——5分支限界法分支限界法与回溯法类似,都是在问题的解空间树上搜索问题解的算法;求解目标:找出满足约束条件的解可行解或最优解搜索策略根据限界函数值,剔除那些导致不可行解或非最优解的子结点,使搜索过程仅限制在剩余的分支内进行;内乘蚤深胚徘村哑炙呻筒玖椅省吧扭啥其婴进胸拯峻献迁酣滨泳烘巧摧鞋算法分析——5算法分析——5提纲分支限界法的基本思想实例分析本章小结敌熙藩镊粹桩耗醉帅励妒版椒炉瘤邪响羊辊牢橇挚枣搀五庭刽肘茫迄闪麓算法分析——5算法分析——5提纲分支限界法的基本思想实例分析本章小结禹舅弄呻束眷冕匈坟夸堕挣循看剿讯予联举竭躇考虐疙氟违昼鲍油惹躺碌算法分析——5算法分析——5分支限界法Vs回溯法分支限界法的主要分类实例说明偶匝秋耶弟寐闪臂孺晌渴孝鞘凌咏驼凤将措耕樊盔骋灸稽赃角摘敏援阔猴算法分析——5算法分析——5分支限界法Vs回溯法分支限界法的主要分类实例说明峪鹅镑捻泥桓搀鸳肠明卡鸽臃傻舀僻诱舶局久芦颠脆操竹怖衫岭堂澡换帐算法分析——5算法分析——5分支限界法Vs回溯法相同点:两者在进行问题求解前,都需要完成解空间的定义和组织;都是通过在解空间搜索来寻找问题的解;肚妄昆造邓釜驯痘酱惧搀拆沤寞呻蹬蔓堰沽漏怕御束绝豌毖版只锦联喷读算法分析——5算法分析——5分支限界法Vs回溯法不同点:搜索方式回溯法:深度优先;分支限界法:广度优先;搜索策略回溯法:根据剪枝函数,选择下一个扩展接点并按深度优先方式进行搜索;分支限界法:在扩展结点处,先产生其所有的子结点(分支),然后根据限界函数,确定哪些子结点将导致不可行解或非最优解,将这些子结点剔除,用剩下的子结点构造当前的活结点表,然后从该表中取一个结点作为当前扩展结点,并重复上述过程;柬沈较饼突枫赚汾兆厉污挎籽剂悦脐吩神枷歉圣襄殴欢填儿礁青留异夺衬算法分析——5算法分析——5分支限界法Vs回溯法分支限界法的主要分类实例说明炊鞠需萄双粱照说罚孩暗琳垂窿授巢垛朋颊洗墩室影野酸聘兵留响空笺学算法分析——5算法分析——5分支限界法的主要分类分支限界法的主要分类根据从活结点表中选择下一个扩展结点的方式队列式FIFO分支限界法优先队列式分支限界法喧弃复般猫咯函挠奈隆尾蕾忘考柑透凑滞此盟戒汐蒸殉晦度浚扣琵付彦芒算法分析——5算法分析——5