算法设计与分析W7-分支定界

VIP免费

2025-01-13 0 0 1.37MB 120 页 5.9玖币

侵权投诉

Last Section

可基于动态规划思想求解的

问题与算法

•计算有向图的传递闭包

Warshall 算法：

rij(k)置为1意味着存在一条从第i个顶点到第j个顶点的路径

，路径中每一个中间顶点的编号都不大于k

rij(k)=rij(k-1)or rik(k-1) and rkj(k-1)

•最优二叉查找树：

C[i,j]是在这棵树中成功查找的最小的平均查找次数

考虑从键ai,…,aj(sorted)中选择一个根ak的所有可能的方法





  j

is s

jki pjkCkiCjiC ]},1[]1,[{min],[

机器负荷分配问题

例2 机器负荷分配问题

设机器在高负荷下生产的产量函数为S1=8u1,

年折损率为a=0.7;

在低负荷下生产的产量函数为S2=5u2,年折

损率为b=0.9。

开始生产时完好机器的数量x1=1000台。按

题意要安排好五年的生产计划，使产品的

总产量最高。

回溯

•回溯法的主要思想

–有组织的穷尽搜索

•3 着色问题

•8皇后问题

•哈密尔顿回路

•一般回溯算法

分支定界

•主要的分支定界法相关概念:

Feasible （solution）, Infeasible （solution）,

Partial Solution, Optimal Solution, Branch, Bound

(tight), Traverse, Backtracking, Prune, DFS, BFS,

Frontier Search, Initial solution, Relax

•一般着色问题

•分支定界法解整数规划问题

•背包问题

Upper Bound and Lower Bound

Upper bound

Lower bound

Objective function value Inc

Dec

Existing solution

Minimization

Lower bound for pruning

Optimal Solution

Upper Bound and Lower Bound

Upper bound

Lower bound

Objective function value Inc

Dec

Existing solution

Maximization

Upper bound for pruning

c d

2 3

TSP

c d

2 3

TSP _ 搜索树？

The search tree - I

Stage 3

Stage 2

Stage 1

Vertex 3

Vertex 2

Vertex 1

Stage 1

Stage 2

Stage 3

Stage m

Ver 4

Ver 5

Ver 6

Ver 7

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

LastSection可基于动态规划思想求解的问题与算法•计算有向图的传递闭包Warshall算法：rij(k)置为1意味着存在一条从第i个顶点到第j个顶点的路径，路径中每一个中间顶点的编号都不大于krij(k)=rij(k-1)orrik(k-1)andrkj(k-1)•最优二叉查找树：C[i,j]是在这棵树中成功查找的最小的平均查找次数考虑从键ai,…,aj(sorted)中选择一个根ak的所有可能的方法jissjkipjkCkiCjiC]},1[]1,[{min],[机器负荷分配问题例2机器负荷分配问题设机器在高负荷下生产的产量函数为S1=8u1,年折损率为a=0.7;...

展开>> 收起<<

算法设计与分析W7-分支定界.pdf

共120页,预览24页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析W7-分支定界

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: