D
DarwinZhang
Unregistered / Unconfirmed
GUEST, unregistred user!
算法是程序的灵魂,那么算法的基本概况如何呢?我尝试作一个简单的介绍:
1947年,G.B.Dantzig提出求解现行规划的单纯形方法以来,线性规划理论上趋于成熟,
虽然Dantzig的算法平均时间是非常优异的,为O(n*log(2,n) ),但它实际上是一个指数
算法,这由Klee和Minty在1972年指出,在1979年L.G.Khachina提出椭球算法
证明线性规划是P问题.
P问题就是所谓存在多项式算法的问题.
而NP问题是存在多项式可验证的但没有多项式求解算法的问题.
当然,这只是一个简略的规定,严格的规定要从图林机着手.
NP-难(NPC)问题则是1972年S.A.Cook提出的,他证明一切NP问题都可以
使用SAT问题的解决算法在多项式时间内解出.
假如一个问题A可以使用多项式的时间算法调用问题B得到解决,
那么认为A不会比B难.这是因为,假如B有多项式算法,
那么A一定有多项式算法,而A有多项式算法,那么B却不一定有多项式算法.
在NPC族问题中只要有任何一个被证明有多项式时间算法,
那么所有的NP问题就是P问题.经过几十年的探索,数学家们没有对NPC问题
获得任何进展.人们目前倾向与认为 NPC<>P.
Karp证明了: 3SAT,3DM(三维匹配问题),划分问题,顶点覆盖问题,哈密顿圈问题,
团问题,TSP(旅行商问题)都是NP-C(NP完全或NP难)的.
这一研究有什么意义呢?这实际上是目前算法的理论问题基石.
在本版的大量未解决的问题,大部分是NP-C的.
当我们遇到一个实际问题的时候,首先应该想一下,这个问题是不是NPC的,如果是,
那么就应该放弃求最优解的期望,而应该使用其它的一些办法.比如平均概率为
多项式的算法(比如:http://www.delphibbs.com/delphibbs/dispq.asp?lid=1588082 ),
求次优解的办法(比如:http://www.delphibbs.com/delphibbs/dispq.asp?lid=1886759 ).
如何判断一个问题是否是NPC的呢?首先我们需要试探求解最优解.
如果试探不出来P算法,那么就应该怀疑是否可以将这个问题归为NPC的.目前已知的
NPC问题有上千个.当年R.M.Karp在1972年就证明了21个NPC问题.初学者应该至少
知道几个基本的NPC问题,才可能学会将问题归到NPC的办法.
下面是几个很基本的NPC问题:
1. SAT问题:
给定布尔变量x1,x2,x3,......xn的一个布尔表达式c1*c2*c3*.....*cm,其中ci是
x1,x2,x3,......xn构成的句子,问此表达式可以取到真值吗?
SAT问题是数理逻辑的中心问题之一,这可以从计算机运行的方式看出来.
2. 3SAT问题:
给定布尔变量x1,x2,x3,......xn的一个布尔表达式c1*c2*c3*.....*cm,其中ci是
x1,x2,x3...xn中的三项构成的句子,问此表达式可以取到真值吗?
比如: (x1+!X2+x3).(x2+x3+!x4).(x4+!x1+x5)
3. 三维匹配问题:
给定X,Y,Z三个不相交的集合,他们的元素个数都是q, M是X,Y,Z的一个组合(匹配),
是否存在一个匹配Mi使M的元素个也为q?
比如:实际问题中,记单身男人集合为X,单身女人集合为Y,住房集合为Z,有些男人和女人
可以结合,有些不可以,有些人只愿意住某些房间,问可否组成一个匹配,使所有的人都
可以组成家庭不重婚且都有房屋?
4. 划分问题:
给定一个正整数集合 A={a1,a2,a3,....an},问是否存在一个A的子集A',使 A'中所有元素的和为
A中所有元素的和的一半?
5.顶点覆盖问题:
给定一个图集G=(V,E)和一个正整数K<=|V|,问G中是否含有不超过K个顶点的覆盖?
(覆盖表示它至少包含G中任何一条边的顶点之一)
6.哈密顿圈问题:
给定一个图G=(V,E),问是否存在哈密顿圈?
哈密顿圈是从某点出发,经过所有顶点一次而回到出发顶点的闭回路.
知道了上面6个问题是NPC问题,那么下面举几个例子来看看实际中
碰到一个问题时,是如何证明它是NPC的:
旅行商问题:有n个城市 a1,a2,a3...an,城市ai到aj的运费为cij,注意cij和cji可能不等,
有商人从城市a1出发去推销商品,城市只去且只去一次,问如何安排行程
才能够使运输费用最少?
很显然,取cij=cji=1,那么这个问题就转化成哈密顿圈问题.
如果运输费用为n就是存在哈密顿圈否则不存在哈密顿圈.
因此在多项式时间内旅行商问题可以转化成哈密顿圈问题,因此不比哈密顿圈问题容易,
所以旅行商问题是NPC的.
0-1线性规划问题:
首先介绍线性规划问题:对于变量x1,x2,x3,......xn,
有若干约束条件 f1(xi)<0, f2(xi)<0,....fm(xi)<0,
求min g(xi) .
如果线性规划中,xi只能取0,或1那么就转化成0,1线性规划问题
很容易看出,令A=a1+a2+a3......+an, a*x1+a*x2+a*x3+....+a*xn>=A/2,
求min(a*x1+a*x2+a*x3+....+a*xn),如果
结果为A/2,就知道划分问题的回答是肯定的,如果大于A/2答案为否.
因此0-1线性规划问题不比划分问题容易,所以0-1线性规划问题是NPC的.
但是线性规划问题是P问题,所以只要加上一个约束,P问题可能就变成NPC的了.
因此我们在实际中一定要小心.
希望能对各位有所帮助,
如有谬误还请指正!
by DarwinZhang 2004.1.16
1947年,G.B.Dantzig提出求解现行规划的单纯形方法以来,线性规划理论上趋于成熟,
虽然Dantzig的算法平均时间是非常优异的,为O(n*log(2,n) ),但它实际上是一个指数
算法,这由Klee和Minty在1972年指出,在1979年L.G.Khachina提出椭球算法
证明线性规划是P问题.
P问题就是所谓存在多项式算法的问题.
而NP问题是存在多项式可验证的但没有多项式求解算法的问题.
当然,这只是一个简略的规定,严格的规定要从图林机着手.
NP-难(NPC)问题则是1972年S.A.Cook提出的,他证明一切NP问题都可以
使用SAT问题的解决算法在多项式时间内解出.
假如一个问题A可以使用多项式的时间算法调用问题B得到解决,
那么认为A不会比B难.这是因为,假如B有多项式算法,
那么A一定有多项式算法,而A有多项式算法,那么B却不一定有多项式算法.
在NPC族问题中只要有任何一个被证明有多项式时间算法,
那么所有的NP问题就是P问题.经过几十年的探索,数学家们没有对NPC问题
获得任何进展.人们目前倾向与认为 NPC<>P.
Karp证明了: 3SAT,3DM(三维匹配问题),划分问题,顶点覆盖问题,哈密顿圈问题,
团问题,TSP(旅行商问题)都是NP-C(NP完全或NP难)的.
这一研究有什么意义呢?这实际上是目前算法的理论问题基石.
在本版的大量未解决的问题,大部分是NP-C的.
当我们遇到一个实际问题的时候,首先应该想一下,这个问题是不是NPC的,如果是,
那么就应该放弃求最优解的期望,而应该使用其它的一些办法.比如平均概率为
多项式的算法(比如:http://www.delphibbs.com/delphibbs/dispq.asp?lid=1588082 ),
求次优解的办法(比如:http://www.delphibbs.com/delphibbs/dispq.asp?lid=1886759 ).
如何判断一个问题是否是NPC的呢?首先我们需要试探求解最优解.
如果试探不出来P算法,那么就应该怀疑是否可以将这个问题归为NPC的.目前已知的
NPC问题有上千个.当年R.M.Karp在1972年就证明了21个NPC问题.初学者应该至少
知道几个基本的NPC问题,才可能学会将问题归到NPC的办法.
下面是几个很基本的NPC问题:
1. SAT问题:
给定布尔变量x1,x2,x3,......xn的一个布尔表达式c1*c2*c3*.....*cm,其中ci是
x1,x2,x3,......xn构成的句子,问此表达式可以取到真值吗?
SAT问题是数理逻辑的中心问题之一,这可以从计算机运行的方式看出来.
2. 3SAT问题:
给定布尔变量x1,x2,x3,......xn的一个布尔表达式c1*c2*c3*.....*cm,其中ci是
x1,x2,x3...xn中的三项构成的句子,问此表达式可以取到真值吗?
比如: (x1+!X2+x3).(x2+x3+!x4).(x4+!x1+x5)
3. 三维匹配问题:
给定X,Y,Z三个不相交的集合,他们的元素个数都是q, M是X,Y,Z的一个组合(匹配),
是否存在一个匹配Mi使M的元素个也为q?
比如:实际问题中,记单身男人集合为X,单身女人集合为Y,住房集合为Z,有些男人和女人
可以结合,有些不可以,有些人只愿意住某些房间,问可否组成一个匹配,使所有的人都
可以组成家庭不重婚且都有房屋?
4. 划分问题:
给定一个正整数集合 A={a1,a2,a3,....an},问是否存在一个A的子集A',使 A'中所有元素的和为
A中所有元素的和的一半?
5.顶点覆盖问题:
给定一个图集G=(V,E)和一个正整数K<=|V|,问G中是否含有不超过K个顶点的覆盖?
(覆盖表示它至少包含G中任何一条边的顶点之一)
6.哈密顿圈问题:
给定一个图G=(V,E),问是否存在哈密顿圈?
哈密顿圈是从某点出发,经过所有顶点一次而回到出发顶点的闭回路.
知道了上面6个问题是NPC问题,那么下面举几个例子来看看实际中
碰到一个问题时,是如何证明它是NPC的:
旅行商问题:有n个城市 a1,a2,a3...an,城市ai到aj的运费为cij,注意cij和cji可能不等,
有商人从城市a1出发去推销商品,城市只去且只去一次,问如何安排行程
才能够使运输费用最少?
很显然,取cij=cji=1,那么这个问题就转化成哈密顿圈问题.
如果运输费用为n就是存在哈密顿圈否则不存在哈密顿圈.
因此在多项式时间内旅行商问题可以转化成哈密顿圈问题,因此不比哈密顿圈问题容易,
所以旅行商问题是NPC的.
0-1线性规划问题:
首先介绍线性规划问题:对于变量x1,x2,x3,......xn,
有若干约束条件 f1(xi)<0, f2(xi)<0,....fm(xi)<0,
求min g(xi) .
如果线性规划中,xi只能取0,或1那么就转化成0,1线性规划问题
很容易看出,令A=a1+a2+a3......+an, a*x1+a*x2+a*x3+....+a*xn>=A/2,
求min(a*x1+a*x2+a*x3+....+a*xn),如果
结果为A/2,就知道划分问题的回答是肯定的,如果大于A/2答案为否.
因此0-1线性规划问题不比划分问题容易,所以0-1线性规划问题是NPC的.
但是线性规划问题是P问题,所以只要加上一个约束,P问题可能就变成NPC的了.
因此我们在实际中一定要小心.
希望能对各位有所帮助,
如有谬误还请指正!
by DarwinZhang 2004.1.16
]
]