腾讯java 面试题
3星 · 超过75%的资源 需积分: 13 73 浏览量
2013-04-18
10:41:15
上传
评论 2
收藏 639KB PDF 举报 
1
Chapter 10
Extending the Limits
of Tractability
Slides by Kevin Wayne.
Copyright @ 2005 Pearson-Addison Wesley.
All rights reserved.
2
Coping With NP-Completeness
Q. Suppose I need to solve an NP-complete problem. What should I do?
A. Theory says you're unlikely to find poly-time algorithm.
Must sacrifice one of three desired features.
Solve problem to optimality.
Solve problem in polynomial time.
Solve arbitrary instances of the problem.
This lecture. Solve some special cases of NP-complete problems that
arise in practice.
10.1 Finding Small Vertex Covers
4
Vertex Cover
VERTEX COVER: Given a graph G = (V, E) and an integer k, is there a
subset of vertices S ⊆ V such that |S| ≤ k, and for each edge (u, v)
either u ∈ S, or v ∈ S, or both.
3
6
10
7
1
5
8
2
4 9
k = 4
S = { 3, 6, 7, 10 }
资源评论
zmjzmj01232013-07-18不好，无用- vitrys2013-10-16楼主 你这个 不是啊 你应该删掉 不要给人误导啊
shiyan192013-07-23一点用都没有，去腾讯面试了，完全不同，风马牛不相及
条款大爷2013-04-23上传出错了吧，呵呵，不是面试题。
