工作总结与计划西安交通大学计算机教学试验中心

1、HPM&S活动活动14 Tourist Town 高效能建模与仿真研究小组2011年10本PPT的材料改编自Really Hard Problems-IntractabilityHPM&S 主要内容主要内容l旅行城镇问题描述l一般解决方案l计算思维及问题扩展l计算机求解复杂性及研究进展l结论l对问题的进一步思考l参考文献HPM&S1. 1. 旅游城镇问题描述旅游城镇问题描述l问题右图是旅游城市的地图。冰激凌销售车停在街道的拐角处出售冰激凌给游客。 我们想放置一些销售车，使得每个人可以至多走一个街道的距离，通过走到街道的终端来到达一个销售点。

2、 l目标问题是需要多少个销售车，以及这些销售车应该放在哪些十字路口？HPM&S2. 2. 一般解决方案一般解决方案l尝试法随机的放置一个空心筹码在一个交叉路口，代表冰激凌销售车，然后放置实心筹码在附近的交叉路口，这样游客就能买到冰激凌不断的重复上述过程就能找到一种配置方案l分解组合法把旅游城镇图拆分成若干个小地图，分解的原则是保证每个小地图只需要一个冰激凌销售车，同时将小地图用连线拼在一起构成旅游城镇图不断的重复上述过程就能找到一种配置方案l问题安置油箱、井、救火中心等等HPM&S3. 3. 计算思维及问题扩展计算思维及问题扩展l“穷举”算法思路考虑所有的放置冰激凌销售车的可能

3、情况，然后检验哪种是最好的过程。 1.如果有1个冰激凌车，在26个交叉路口放置一个冰激凌销售车有26种放置方法，然后验证，将有26种可能性要验证。 2.如果有2个冰激凌车，先放置第一辆，然后在剩余的25个地方放置第二辆，将有26*25种可能性要验证。 3.同理，如果有三辆，将有26*25*24种可能性要验证。 4.同理，如果有优点：问题规模不是很大时，很快的找出配置方案缺点：花费大量的时间,效率低 HPM&S3. 3. 计算思维及问题扩展计算思维及问题扩展l“穷举”算法伪代码 Exhaustion()/状态A(a1,a2,a26)代表每个交叉路口是否放置冰激凌/销售车，如果为1代表放置

4、，如果为0代表没有放置 for A(a1,a2,a26) from 00000 to 111.111 If 状态A(a1,a2,a26) 满足检验条件then 输出问题的解； HPM&S3. 3. 计算思维及问题扩展计算思维及问题扩展l“穷举”算法算法应用 一名货运司机要把货物从甲地运往加乙地，从甲地到乙地公路从横交错，那么如何选择行走路线，才能最快将货物运到目的地呢？一名销售员要到若干个城市去洽谈业务，已知任两个城市之间的距离，请为其设计一个旅行线路，使得他从某一城市出发恰好经过每个城市一次，最后回到出发城市。要求所走的路线最短。给定图G=（V，E），找顶点数最少的V的子集C， 使得

5、E中每条边的两端至少有一个属于与C。 HPM&S3. 3. 计算思维及问题扩展计算思维及问题扩展l“贪婪”算法思路考虑把第一辆销售车放在连接最多街道数目的交叉点处，第二辆放在下一个类似的交叉点处，如此类推。缺点：不能保证得到最优解优点：效率高 HPM&S3. 3. 计算思维及问题扩展计算思维及问题扩展l“贪婪”算法伪代码Greedy(C) /C是问题的输入集合即候选集合 S=; /初始解集合为空集While(not solution(S) /集合S没有构成问题的一个解 X=select(C); /在候选集合中做贪心选择If feasible(S,x) /判断集合S中加入x后的解

6、是否可行S=S+x;C=C-x;Return S;HPM&S3. 3. 计算思维及问题扩展计算思维及问题扩展l“贪婪”算法算法应用工作人员去做 n 件工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？给定一个载重为M的背包，及N个重量为wi、价值为Pi的物体，1=i=n,要求把物体装满背包，且使得背包内的物体价值最大，这类问题称为背包问题。某地区有若干主要城市，现在要修建一些高速公路将它们连起来，使得从任一城市可经过高速公路直接或间接地到达另一城市。假定已经知道任两城市间修建成本，那么如何修建高速公路网，才能使得总的成本最小？HPM&am

7、p;S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l计算机求解复杂性复杂性问题支配集问题是一个NP完全问题（non-eterministic polynomial-time complete）-多项式复杂程度的非确定性问题。这类问题出现在不同领域：布尔逻辑，图论，算术，网络设计，集合与划分，排序与调度，数学程序设计，代数与数论，自动机与语言理论，程序优化，生物学，化学，物理。HPM&S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l计算机求解复杂性多项式时间复杂度经典P问题，一般复杂度为O(nK)一个图中任意两点最短距离的 Dijkstra算法指派

8、问题（赋权匹配问题）Kuhn算法；排序、查找问题HPM&S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l计算机求解复杂性NP问题NP是一大类判定问题，其准确含义是可在一种假想的机器非确定型Turing机上在多项式时间内可求解的问题，或者说可由非确定型算法在多项式时间可解。NP完全问题（NPC）最难的NP问题（超级NP问题）所有NP问题都可规约为NP完全问题HPM&S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l计算机求解复杂性NP完全问题（NPC）如果解决了此类问题，则所有NP问题都可以被解决1972年 karp给出了标准化的验证方式，证

9、明21个NP完全问题是同复杂度，包括哈密顿回路问题，经销商问题NP-hard寻找国际象棋或围棋最佳走法 一些指数级问题HPM&S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l计算机求解复杂性可能的关系HPM&S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l研究进展1970年左右,Cook发现了一些组合优化问题可在多项式时间内相互转化,如果其中一个是P问题,那么其他问题也属于P问题,反之亦然. 目前已证明有几千个组合优化问题包含在其中。近年，任意大数质数判断问题被证明为一个多项式问题HP LAB的 Vinay Deolalikar 教授宣布

10、于公元2010年8月6日证明了P!=NP，在他的主页上，证明过程已经公布。HPM&S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l研究进展尽管目前没人能给出一个令人信服的证明，但人们普遍倾向于认为 P!=NP.主要原因 ?（1）基于NP-完全理论，人们发现大量的组合优化问题（几千个！）有着一样的难解性，一个可以多项式求解，则所有的问题可多项式求解。而没人能给出任一个NP-完全问题的多项式时间算法；（2）如果P=NP， 这个世界与我们所想象的大不一样！ 当然，P是否等于NP尚没有最后定论，需要解决它需要新的重大的突破。HPM&S4. 4. 计算机求解复杂性及研

11、究进展计算机求解复杂性及研究进展l研究进展近似算法如何求解NPC，NP-hard问题：对小规模问题，利用指数时间复杂性算法限制于一些特殊情况，求子问题的最优解。譬如对最大独立集问题， 如果限制考虑平面图（或二部图）的话,可以在多项式时间内求解利用启发式算法（heuristic），求问题的一个可行解。如贪婪算法，遗传算法、模拟退火、Local search、分支定界等等。(参考文献6)设计多项式时间近似算法（Approximation Algorithms）。（参考文献1，pp：633-652）HPM&S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l研究进展近似算法对

12、于NPC， NP-hard问题，启发式算法与近似算法（Approximation Algorithm）的主要区别在于： 前者无法在理论上给出所求的解与真正最优解的差距（即算法有多好，或多坏），一般仅通过数值模拟来判定算法好坏。后者强调对所给问题的任一实例，在多项式时间内求出一个可行解，该解所对应的目标函数值与最优值的偏差在理论上有充分的保证（需要给出理论上严格的证明）HPM&S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l研究进展启发式算法根据定理，图的每个极大独立集均为一个极小支配集，而根据定义，图的最小支配集也是极小支配集，故可以把图的极大独立集中基数最少的点集

13、近似作为图的最小支配集，而要找出极大独立集中基数最少的点集，可以按启发式规则实现。HPM&S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l研究进展启发式算法对于图G=，逆序启发式算法可描述为：步骤步骤1 1：将V中的顶点按顶点度数从大到小逆序排列成点集V，全部顶点设置为未标号；步骤步骤2 2：取中V第一个顶点，若该点已经标号，则在V删除该点，转至步骤3:否则，将该点标号为1，并将与之相关联且未标号的顶点标号为0，在V删除该点；步骤步骤3 3：若V为空，转至步骤4；否则，转至步骤2；步骤步骤4 4：取标号为1的顶点作为支配点，把这些点组成的点集为最小支配集。HPM&a

14、mp;S4. 4. 计算机求解复杂性及研究进展计算机求解复杂性及研究进展l研究进展启发式算法禁忌搜索(Tabu Search，TS)是另一个著名的启发式搜索算法，在搜索过程中可以接受劣解，使得Ts在搜索过程中能够跳出局部最优解，进而转向其他区域进行搜索，并通过藐视准则来赦免一些被禁忌的优良状态，从而高优化效率，获得更好的解或全局最优解的概率也大大增加。 HPM&S5. 5. 结论结论l主要结论存在一类不能用常规数学方法求解的问题计算机求解这类问题的局限性HPM&S6. 6. 对问题的进一步思考对问题的进一步思考l如果P=NP被证明正确或者错误，将对计算机研究应用领域带来什么样的

15、冲击？l启发式算法求解思路HPM&S7. 7. 参考文献参考文献lThomas H.Cormen Charles E.Leiserson著 潘金贵 顾铁成 李成法 叶懋 译，算法导论，机械工业出版，2006.l M.R. Garey, D.S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, San Francisco, W.H. Freedman and Co., 1979.lD. S. Hochbaum (eds) , Approximation Algorithms for NP-hard Problems, 世界图书出版社（影印），1995.l V. V. Vazirani，Approximation Algorithms, Springer, 2002.l谢政，李建平，网络算法与复杂性