算法设计与分析W12-近似算法

VIP免费
2025-01-13 0 0 2.69MB 159 页 5.9玖币
侵权投诉
近似算法
Approximation Algorithms
近似算法的设计方法
u
贪心算法
ü
旅行商问题
ü
背包问题
ü
最小顶点覆盖问题
u
局部搜索
( local search)
u
线性规划
u
随机算法
u
动态规划
u… …
91
最大背包问题
（
Maximum Knapsack
）
背包问题
ü
输入：
n
个物品的集合
U={u1, u2, ..., un}
，其中物品
ui
的重量记为
w(ui)
，价值记为
v(ui)
，
i =1, 2,..., n
；
一个承重为
W
的背包，
ü
输出：价值最高的物品子集
!:"U
，且能全部放入
背包中，即
max{#;∈=#$ % &!:"!'#;∈=#( % )*}
92
背包问题的近似算法
——
贪心算法
u
贪心策略
ü
把物品按照重量
wi
进行降序排序
ü
把物品按照价值
vi
进行降序排序
ü
把物品按照价值重量比
vi /wi
进行降序排序
93
背包问题的近似算法
——
贪心算法
u
算法
KnapsackGreedy
输入：
n
个物品
ui,
重量
w(ui),
价值
v(ui), i=1,2,..., n
，
承重
W
输出：最大价值物品子集
U '
，满足总重量
≤ W
1.
对给定的物品计算价值重量比
vi /wi, i=1,2,..., n
2.
把物品按价值重量比的降序排列，形成有序列表
3.
重复以下步骤，直至有序列表中不留下物品
4.
当前物品能够放入背包，则加入
U′
；
5.
否则，考虑下一物品；
5.
输出
U′
94
例：
背包的承重量
W
等于
10
。
物品 重量 价值
1 3 12
2 4 40
3 5 25
4 7 42
价值重量比
4
10
5
6
95
例：
背包的承重量
W
等于
10
。
算法选择物品顺序为：
物品
2
物品
4
（超过承重）
物品
3
物品
1
（超过承重）
物品 重量 价值
1 3 12
2 4 40
3 5 25
4 7 42
价值重量比
4
10
5
6
96
×
×
得，
Uʹ={
物品
2
，物品
3}
。
价值和为
65
总重量为
9<10
近似性能比？
例
:
算法输出为
{
物品
1}
，总价值为
2
最优解为
{
物品
2}
，总价值为
W
解的精度为
W/2
，没有上界
算法的性能比为
∞
物品 重量 价值
1 1 2
2W W
价值重量比
2
1
是否具有常数性
能比算法？
背包的承重量
W>2
97
增强贪心算法
（
Enhanced greedy algorithm
）
物品 重量 价值
1 1 2
2W W
价值重量比
2
198
算法
KnapsackGreedy-Enhanced
输入：
n
个物品
ui,
重量
w(ui),
价值
v(ui), i =1,2,..., n
，承重
量
W
输出：最大价值物品子集，满足总重量
≤ W
1. U′ = KnapsackGreedy(U, w, v, W)
2.
令
umax
是能放入箱子的物品中具有最大价值的物品
3.
输出
U′
与
umax
中价值最大者
max{v(U′), v(umax)}
背包的承重量
W>2
算法输出｛物品
2
｝
定理
5
：对于背包问题，增强贪心算法是一个
2-
近似算法。
假设最优解为
s*
，则一定有
m*(x)<Vj + vj
。
（考虑分数背包问题，此时
Vj+vj
一
定大于分数背包问
题的最优值，而分数背包问题最优值一定大于或等于
0-1
背包问题的最优值。）
99
证明：
给定背包问题的实例
x
，记
按价值重量比降序排列后物体序列为
u1,…,un,
对应的价值序列为
: v1,…,vn,
重量序列为
w1,…,wn
。
假设
uj
是第一个不能放入箱子中的物品，此时箱子中物
品为
u1,…, uj-1,
未放入箱子中的物品为
uj ,…, un
。
则箱子中物品的总价值为
+,>-#9-.
>$. $9,
总重为
*>-#9-.
>$. (9)*.
摘要：

近似算法ApproximationAlgorithms近似算法的设计方法u贪心算法ü旅行商问题ü背包问题ü最小顶点覆盖问题u局部搜索(localsearch)u线性规划u随机算法u动态规划u……91最大背包问题（MaximumKnapsack）背包问题ü输入：n个物品的集合U={u1,u2,...,un}，其中物品ui的重量记为w(ui)，价值记为v(ui)，i=1,2,...,n；一个承重为W的背包，ü输出：价值最高的物品子集=:⊆U，且能全部放入背包中，即max{∑;∈=#>?|=:⊆=,∑;∈=#A?≤B}92背包问题的近似算法——贪心算法u贪心策略ü把物品按照重量wi进行降序排序ü把物...

展开>> 收起<<
算法设计与分析W12-近似算法.pdf

共159页,预览32页

还剩页未读， 继续阅读

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

相关推荐

更多
立即下载
分类：计算机 价格：5.9玖币 属性：159 页 大小：2.69MB 格式：PDF 时间：2025-01-13

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

高考理综 人际关系 配电装置 动力学连接体 力的合成 全宋诗作者索引 公务员考试
/ 159
评分 收藏
分享
立即下载 VIP免费下载
客服
关注