算法设计与分析W6-回溯+分支定界

VIP免费

2025-01-13 3 0 780.93KB 64 页 5.9玖币

侵权投诉

Last Section

变治_改变表现

变换为同样实例的不同表现—改变表现

(Representation Change)

•2-3 树

•堆和堆排序

•霍纳法则

•二进制幂

变治

变换为另一个问题的实例，这种问题的算法是已知

的—问题化简(Problem reduction)。

•Lcm

•图中的路径数量

•函数极值

•综合除法

•凸包，解析几何

•线性规划

•简化为图

•MST vs. Element Uniqueness

动态规划

•最优化原理:

–无论过去的状态和决策如何，对前面的决策所形

成的状态而言，余下的诸决策必须构成最优策略

•构成动态规划模型的条件

–正确选择状态变量xk, 使它既能描述过程的状态，

又要满足无后效性(如果某段状态给定，则在这段

以后过程的发展不受前面各阶段状态的影响)

–确定决策变量uk及每段的允许决策集合

–写出状态转移方程

–列出指标函数Vk,n 关系，并要满足递推性

动态规划应用举例

•资源分配问题

•生产与存储问题

•复合系统工作可靠性问题

•排序问题

•设备更新问题

















nix

axxx

xgxgxg

......,2,10

......

)](......)()(max[

2211

)(),......,,(max 1

21 ii

nzpzzzP 













  

 

iiiiii zwzwczczR

1 1

0,,|

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

问题与算法

•计算二项式系数

•最长公共子序列

L[i,j] = 0 若i=0或j=0

=L[i-1, j-1] + 1 若i>0, j>0 和ai=bj

=max{ L[i,j-1], L[i-1, j]} 若i>0, j>0 和ai≠bj

•矩阵链相乘

),1()1,1(),( knCknCknC 

}],[]1,[{

min

],[ 1





jki rrrjkCkiC

jki

jiC

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

问题与算法

•所有点对的最短路径问题

–做n次迭代，使在第k次迭代后，Dk[i,j]含有从顶点i到顶点j

，

且不经过编号大于k的任何顶点的最短路径的长度。

dki,j=l[i,j]若k = 0

=min{dk-1i,j,dk-1i,k+ dk-1k,j}若1≤k≤n

•0/1 背包问题

–设V[i,j] 表示从前i项{u1，u2，…,ui}中取出来的装入体积为j

的背包的物品的最大价值

V[i,j] = 0 若i=0或j=0

=V[i-1,j]若j<si

=Max{V[i-1,j],V[i-1,j-si]+vi}若j≥si

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

问题与算法

•计算有向图的传递闭包

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和投入生产的机器数

量u1的关系为

s1=g(u1)

这时，机器的年折损率为a，即如果年初完好机器的数量为u，

到年终时完好的机器就为au, 0<a<1.

在低负荷下生产时，产品的年产量s2和投入生产的机器数量u2

的关系为

s2=h(u2)

相应的机器的年折损率为b, 0<b<1.

假定开始生产时完好的机器数量为x1。要求制定一个五年计划，

在每年开始时，决定如何重新分配完好的机器在两种不同

的负荷下生产的数量，使在五年内产品的总产量达到最高。

机器负荷分配问题

例2 机器负荷分配问题

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

年折损率为a=0.7;

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

损率为b=0.9。

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

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

总产量最高。

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

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

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

LastSection变治_改变表现变换为同样实例的不同表现—改变表现(RepresentationChange)•2-3树•堆和堆排序•霍纳法则•二进制幂变治变换为另一个问题的实例，这种问题的算法是已知的—问题化简(Problemreduction)。•Lcm•图中的路径数量•函数极值•综合除法•凸包，解析几何•线性规划•简化为图•MSTvs.ElementUniqueness动态规划•最优化原理:–无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略•构成动态规划模型的条件–正确选择状态变量xk,使它既能描述过程的状态，又要满足无后效性(如果某段状态给定，则...

展开>> 收起<<

算法设计与分析W6-回溯+分支定界.pdf

共64页,预览13页

还剩页未读，继续阅读

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

算法设计与分析W6-回溯+分支定界

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: