没有合适的资源?快使用搜索试试~ 我知道了~
IntractabilityIII.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 57 浏览量
2021-11-28
00:03:03
上传
评论
收藏 14.85MB PDF 举报
温馨提示
试读
68页
算法设计
资源推荐
资源详情
资源评论
Lecture slides by Kevin Wayne!
Copyright © 2005 Pearson-Addison Wesley!
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
Last updated on 5/5/18 5:15 AM
INTRACTABILITY III
‣
special cases: trees
‣
special cases: planarity
‣
approximation algorithms: vertex cover
‣
approximation algorithms: knapsack
‣
exponential algorithms: 3-SAT
‣
exponential algorithms: TSP
Coping with NP-completeness
Q. Suppose I need to solve an NP-hard problem. What should I do?
!
A. Sacrifice one of three desired features.
i. Solve arbitrary instances of the problem.
ii. Solve problem to optimality.
iii. Solve problem in polynomial time.
!
Coping strategies.
i. Design algorithms for special cases of the problem.
ii. Design approximation algorithms or heuristics.
iii. Design algorithms that may take exponential time.
2
using greedy,
dynamic programming,
divide-and-conquer, and
network flow algorithms!
INTRACTABILITY III
‣
special cases: trees
‣
special cases: planarity
‣
approximation algorithms: vertex cover
‣
approximation algorithms: knapsack
‣
exponential algorithms: 3-SAT
‣
exponential algorithms: TSP
SECTION 10.2
Independent set on trees
Independent set on trees. Given a tree, find a max-cardinality subset of
nodes such that no two are adjacent.
!
Fact. A tree has at least one node that is a leaf (degree = 1).
!
!
!
!
Key observation. If node v is a leaf, there exists!
a max-cardinality independent set containing v.
Pf. [exchange argument]
・
Consider a max-cardinality independent set S.
・
If v ∈ S, we’re done.
・
Otherwise, let (u, v) denote the lone edge incident to v.
-
if u ∉ S and v ∉ S, then S ∪ {
v
} is independent ⇒ S not maximum
-
if u ∈ S and v ∉ S, then S ∪ {
v
} − {
u
} is independent ▪
4
u
v
Independent set on trees: greedy algorithm
Theorem. The greedy algorithm finds a max-cardinality independent!
set in forests (and hence trees).
!
Pf. Correctness follows from the previous key observation. ▪
!
!
!
!
!
!
!
!
!
!
!
Remark. Can implement in O(n) time by maintaining nodes of degree 1.
5
INDEPENDENT-SET-IN-A-FOREST(F)
_____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
S ← ∅.
WHILE (F has at least 1 edge)
Let v be a leaf node and let (u, v) be the lone edge incident to v.
S ← S ∪ { v }.
F ← F – { u, v }.
RETURN S ∪ { nodes remaining in F }.
delete both u and v (including all incident edges)
剩余67页未读,继续阅读
资源评论
码上富贵
- 粉丝: 1w+
- 资源: 177
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功