HPMS4.计算机求解复杂性及研究进展-西安交通大学计算机教学.ppt

* * * * HPMS HPMS 活动14 Tourist Town  ——支配集 西安交通大学 高效能建模与仿真研究小组 2011年10 本PPT的材料改编自csunplugged.org项目 Really Hard Problems-Intractability 主要内容 旅行城镇问题描述 一般解决方案 计算思维及问题扩展 计算机求解复杂性及研究进展 结论 对问题的进一步思考 参考文献 1. 旅游城镇问题描述 问题 右图是旅游城市的地图。冰激凌销 售车停在街道的拐角处出售冰激 凌给游客。 我们想放置一些销售 车，使得每个人可以至多走一个街 道的距离，通过走到街道的终端来 到达一个销售点。 目标 问题是需要多少个销售车，以及这 些销售车应该放在哪些十字路口？ 2. 一般解决方案 尝试法 随机的放置一个空心筹码在一个交叉路口，代表 冰激凌销售车，然后放置实心筹码在附近的交叉 路口，这样游客就能买到冰激凌 不断的重复上述过程就能找到一种配置方案 分解组合法 把旅游城镇图拆分成若干个小地图，分解的原则 是保证每个小地图只需要一个冰激凌销售车，同 时将小地图用连线拼在一起构成旅游城镇图 不断的重复上述过程就能找到一种配置方案 问题 安置油箱、井、救火中心等等 构造过程 3. 计算思维及问题扩展 “穷举”算法 思路 考虑所有的放置冰激凌销售车的可能情况，然后检验哪种是最好的过程。 1.如果有1个冰激凌车，在26个交叉路口放置一个冰激凌销售车有26种放置方法，然后验证，将有26种可能性要验证。 2.如果有2个冰激凌车，先放置第一辆，然后在剩余的25个地方放置第二辆，将有26*25种可能性要验证。 3.同理，如果有三辆，将有26*25*24种可能性要验证。 4.同理，如果有…… 优点：问题规模不是很大时，很快的找出配置方案 缺点：花费大量的时间,效率低 3. 计算思维及问题扩展 “穷举”算法 伪代码 Exhaustion(){ //状态A(a1,a2,……a26)代表每个交叉路口是否放置冰激凌 //销售车，如果为1代表放置，如果为0代表没有放置 for A(a1,a2,……a26) from 00…000 to 111..111 { If 状态A(a1,a2,……a26) 满足检验条件then 输出问题的解； } } 3. 计算思维及问题扩展 “穷举”算法 算法应用 最短路问题 一名货运司机要把货物从甲地运往加乙地，从甲地到乙地公路从横交错，那么如何选择行走路线，才能最快将货物运到目的地呢？ 旅行商问题 一名销售员要到若干个城市去洽谈业务，已知任两个城市之间的距离，请为其设计一个旅行线路，使得他从某一城市出发恰好经过每个城市一次，最后回到出发城市。要求所走的路线最短。 顶点覆盖问题 给定图G=（V，E），找顶点数最少的V的子集C， 使得E中每条边的两端至少有一个属于与C。 3. 计算思维及问题扩展 “贪婪”算法 思路 考虑把第一辆销售车放在连接最多街道数目的交叉点处，第二辆放在下一个类似的交叉点处，如此类推。 缺点：不能保证得到最优解 优点：效率高 3. 计算思维及问题扩展 “贪婪”算法 伪代码 Greedy(C) //C是问题的输入集合即候选集合 { S={}; //初始解集合为空集 While(not solution(S)) //集合S没有构成问题的一个解 { X=select(C); //在候选集合中做贪心选择 If feasible(S,x) //判断集合S中加入x后的解是否可行 S=S+{x}; C=C-{x}; } Return S; } 3. 计算思维及问题扩展 “贪婪”算法 算法应用 人员分派问题 工作人员去做 n 件工作，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？ 旅行商问题 给定一个载重为M的背包，及N个重量为wi、价值为Pi的物体，1=i=n,要求把物体装满背包，且使得背包内的物体价值最大，这类问题称为背包问题。 公路连接问题 某地区有若干主要城市，现在要修建一些高速公路将它们连起来，使得从任一城市可经过高速公路直接或间接地到达另一城市。假定已经知道任两城市间修建成本，那么如何修建高速公路网，才能使得总的成本最小？ 4. 计算机求解复杂性及研究进展 计算机求解复杂性 复杂性问题 支配集问题是一个NP完全问题（non-eterministic poly