Data Structures and Algorithms
13 Hard or Intractable Problems
If a problem has an O(nk) time algorithm (where k is a constant), then we
class it as having polynomial time complexity and as being efficiently
solvable.
If there is no known polynomial time algorithm, then the problem is classed
as intractable.
The dividing line is not always obvious. Consider two apparently similar
problems:
Euler's problem asks whether there is a
(often characterized as the path through a graph which
Bridges of K�nigsberg - a traverses each edge only
popular 18th C puzzle) once.
Hamilton's problem asks whether there is a
path through a graph which
visits each vertex exactly
once.
Euler's problem
The 18th century German city of K�nigsberg was situated on the
river Pregel. Within a park built on the banks of the river, there
[Image]were two islands joined by seven bridges.
The puzzle asks whether it is possible to take a tour through the
park, crossing each bridge only once.
An exhaustive search requires starting at every possible point and
traversing all the possible paths from that point - an O(n!) problem.
However Euler showed that an Eulerian path existed iff
* it is possible to go from any vertex to any other by following the
edges (the graph must be connected) and
* every vertex must have an even number of edges connected to it, with at
most two exceptions (which constitute the starting and ending points).
It is easy to see that these are necessary conditions: to complete the tour,
one needs to enter and leave every point except the start and end points.
The proof that these are sufficient conditions may be found in the
literature . Thus we now have a O(n) problem to determine whether a path
exists.
Transform the map into a
graph in which We can now easily see that the Bridges of
the nodes represent the "dry K�nigsberg does not have a solution.
land" points
and the arcs represent the A quick inspection shows that it does have a
bridges. Hamiltonian path.
[Image]
However there is no known efficient algorithm for determining
whether a Hamiltonian path exists.
But if a path was found, then it can be verified to be a solution in
polynomial time: we simply verify that each edge in the path is actually an
edge (O(e) if the edges are stored in an adjacency matrix) and that each
vertex is visited only once (O(n2) in the worst case).
Classes P and NP
What does NP mean?
At each step in the algorithm, you guess
which possibility to try next. This is the
non-deterministic part: it doesn't matter
Euler's problem lies in the which possibility you try next. There is no
class P: problems solvable in information used from previous attempts
Polynomial time. Hamilton's (other than not trying something that you've
problem is believed to lie in already tried) to determine which
class NP (Non-deterministic alternative should be tried next. However,
Polynomial). having made a guess, you can determine in
polynomial time whether it is a solution or
Note that I wrote "believed" not.
in the previous sentence.
No-one has succeeded in Since nothing from previous trials helps you
proving that efficient (ie to determine which alternative should be
polynomial time) algorithms tried next, you are forced to investigate
don't exist yet! all possibilities to find a solution. So the
only systematic thing you can do is use some
strategy for systematically working through
all possibilities, eg setting out all
permutations of the cities for the
travelling salesman's tour.
Many other problems lie in class NP. Some examples follow.
Composite Numbers
Determining whether a number can be written as the product of two other
numbers is the composite numbers problem. If a solution is found, it is
simple to verify it, but no efficient method of finding the solution exists.
Assignment
Assignment of compatible room-mates: assume we have a number of students to
be assigned to rooms in a college. They can be represented as the vertices
on a graph with edges linking compatible pairs. If we have two per room, a
class P algorithm exists, but if three are to be fitted in a room, we have a
class NP problem.
Boolean satisfiability
Given an arbitrary boolean expression in n variables:
a1 op a2 op ... op an
where op are boolean operators, and, or, ..
Can we find an assignment of (true,false) to the ai so that the expression
is true? This problem is equivalent to the circuit-satisfiability problem
which asks can we find a set of inputs which will produce a true at the
output of a circuit composed of arbitrary logic gates.
A solution can only be found by trying all 2n possible assignments.
Map colouring
The three-colour map colouring problem asks if we can colour a map
so that no adjoining countries have the same colour. Once a
solution has been guessed, then it is readily proved.
[This problem is easily answered if there are only 2 colours - [Image]
there must be no point at which an odd number of countries meet -
or 4 colours - there is a proof that 4 colours suffice for any
map.]
This problem has a graph equivalent: each vertex represents a country and an
edge is drawn between two vertices if they share a common border.
Its solution has a more general application. If we are scheduling work in a
factory: each vertex can represent a task to be performed - they are linked
by an edge if they share a common resource, eg require a particular machine.
A colouring of the vertices with 3 colours then provides a 3-shift schedule
for the factory.
Many problems are reducible to others: map colouring can be reduced to graph
colouring. A solution to a graph colouring problem is effectively a solution
to the equivalent map colouring or scheduling problem. The map or
graph-colouring problem may be reduced to the boolean satisfiability
problem. To give an informal description of this process, assume the three
colours are red, blue and green. Denote the partial solution, "A is red" by
ar so that we have a set of boolean variables:
ar A is red
ab A is blue
ag A is green
br B is red
bb B is blue
bg B is green
cr C is red
... ...
Now a solution to the problem may be found by finding values for ar, ab, etc
which make the expression true:
((ar and not ab and not ag) and ( (bb and (cb and (dg ....
Thus solving the map colouring problem is equivalent to finding an
assignment to the variables which results in a true value for the expression
- the boolean satisfiability problem.
There is a special class of problems in NP: the NP-complete problems. All
the problems in NP are efficiently reducible to them. By efficiently, we
mean in polynomial time, so the term polynomially reducible provides a more
precise definition.
In 1971, Cook was able to prove that the boolean satisfiability problem was
NP-complete. Proofs now exist showing that many problems in NP are
efficiently reducible to the satisfiability problem. Thus we have a large
class of problems which will are all related to each other: finding an
没有合适的资源?快使用搜索试试~ 我知道了~
算法源代码
共692个文件
class:263个
java:252个
gif:84个
需积分: 0 8 下载量 187 浏览量
2008-02-29
13:30:46
上传
评论
收藏 1.01MB RAR 举报
温馨提示
各种算法的C语言的代码实现
资源详情
资源评论
资源推荐
收起资源包目录
算法源代码 (692个子文件)
1 2B
2 2B
Edge.backup 9KB
Arrow.backup 7KB
Node.backup 4KB
TextFrame.bk 3KB
graph.circle 183B
graph.circle 183B
OptMatMult.class 15KB
BinTree.class 14KB
BinTree.class 13KB
RBTree.class 12KB
Heap.class 12KB
Heap.class 12KB
DrawingPanel.class 11KB
DrawingPanel.class 11KB
AlgThread.class 9KB
AlgAnimFrame.class 9KB
AlgAnimFrame.class 9KB
DrawingPanel.class 9KB
AlgAnimFrame.class 9KB
AlgAnimFrame.class 9KB
AlgAnimFrame.class 9KB
AlgAnimFrame.class 9KB
AlgAnimFrame.class 9KB
AlgAnimFrame.class 9KB
AlgAnimFrame.class 9KB
AlgThread.class 9KB
DrawingPanel.class 7KB
DrawingPanel.class 7KB
DrawingPanel.class 7KB
DrawingPanel.class 7KB
DrawingPanel.class 7KB
IntMatrix.class 7KB
OBSearch.class 7KB
DrawingPanel.class 7KB
DrawingPanel.class 7KB
DrawingPanel.class 6KB
OBSearch.class 6KB
Edge.class 6KB
Edge.class 6KB
IntMatrix.class 6KB
OBSAnim.class 6KB
AlgThread.class 6KB
Edge.class 6KB
AlgThread.class 6KB
AlgThread.class 6KB
OBSAnim.class 5KB
IntMatrix.class 5KB
IntMatrix.class 5KB
IntMatrix.class 5KB
AlgThread.class 5KB
DrawingPanel.class 5KB
GraphDij.class 5KB
TableCanvas.class 5KB
TableCanvas.class 5KB
TableCanvas.class 5KB
TableCanvas.class 5KB
AlgThread.class 5KB
TextPanel.class 5KB
AlgAnimFrame.class 5KB
AlgAnimFrame.class 5KB
AlgAnimFrame.class 5KB
Histogram.class 5KB
Histogram.class 5KB
Histogram.class 5KB
AlgAnimFrame.class 5KB
AlgAnimFrame.class 5KB
StickPanel.class 5KB
AlgAnimFrame.class 5KB
TextPanel.class 5KB
TextPanel.class 5KB
TextPanel.class 5KB
TextPanel.class 5KB
TextPanel.class 5KB
TextPanel.class 5KB
TextPanel.class 5KB
TextPanel.class 5KB
Histogram.class 5KB
TextFrame.class 5KB
GraphPanel.class 5KB
TextFrame.class 4KB
TextFrame.class 4KB
TextFrame.class 4KB
TextFrame.class 4KB
TextPanel.class 4KB
Graph.class 4KB
TextFrame.class 4KB
AlgAnimFrame.class 4KB
ControlPanel.class 4KB
Graph.class 4KB
TextFrame.class 4KB
AlgAnimFrame.class 4KB
Node.class 4KB
AlgThread.class 4KB
AlgThread.class 4KB
ControlPanel.class 4KB
Arrow.class 4KB
Node.class 4KB
Node.class 4KB
共 692 条
- 1
- 2
- 3
- 4
- 5
- 6
- 7
stxkwynfv
- 粉丝: 5
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0