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

活动14TouristTown 高效能建模与仿真研究小组2011年10 本PPT的材料改编自csunplugged org ReallyHardProblems 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代表没有放置forA a1 a2 a26 from00 000to111 111 If状态A a1 a2 a26 满足检验条件then输出问题的解 3 计算思维及问题扩展 穷举 算法算法应用最短路问题一名货运司机要把货物从甲地运往加乙地 从甲地到乙地公路从横交错 那么如何选择行走路线 才能最快将货物运到目的地呢 旅行商问题一名销售员要到若干个城市去洽谈业务 已知任两个城市之间的距离 请为其设计一个旅行线路 使得他从某一城市出发恰好经过每个城市一次 最后回到出发城市 要求所走的路线最短 顶点覆盖问题给定图G V E 找顶点数最少的V的子集C 使得E中每条边的两端至少有一个属于与C 3 计算思维及问题扩展 贪婪 算法思路考虑把第一辆销售车放在连接最多街道数目的交叉点处 第二辆放在下一个类似的交叉点处 如此类推 缺点 不能保证得到最优解优点 效率高 3 计算思维及问题扩展 贪婪 算法伪代码Greedy C C是问题的输入集合即候选集合 S 初始解集合为空集While notsolution S 集合S没有构成问题的一个解 X select C 在候选集合中做贪心选择Iffeasible S x 判断集合S中加入x后的解是否可行S S x C C x ReturnS 3 计算思维及问题扩展 贪婪 算法算法应用人员分派问题工作人员去做n件工作 每人适合做其中一件或几件 问能否每人都有一份适合的工作 如果不能 最多几人可以有适合的工作 旅行商问题给定一个载重为M的背包 及N个重量为wi 价值为Pi的物体 1 i n 要求把物体装满背包 且使得背包内的物体价值最大 这类问题称为背包问题 公路连接问题某地区有若干主要城市 现在要修建一些高速公路将它们连起来 使得从任一城市可经过高速公路直接或间接地到达另一城市 假定已经知道任两城市间修建成本 那么如何修建高速公路网 才能使得总的成本最小 4 计算机求解复杂性及研究进展 计算机求解复杂性复杂性问题支配集问题是一个NP完全问题 non eterministicpolynomial timecomplete 多项式复杂程度的非确定性问题 这类问题出现在不同领域 布尔逻辑 图论 算术 网络设计 集合与划分 排序与调度 数学程序设计 代数与数论 自动机与语言理论 程序优化 生物学 化学 物理 4 计算机求解复杂性及研究进展 计算机求解复杂性多项式时间复杂度经典P问题 一般复杂度为O nK 一个图中任意两点最短距离的Dijkstra算法指派问题 赋权匹配问题 Kuhn算法 排序 查找问题 4 计算机求解复杂性及研究进展 计算机求解复杂性NP问题NP是一大类判定问题 其准确含义是可在一种假想的机器 非确定型Turing机上在多项式时间内可求解的问题 或者说可由非确定型算法在多项式时间可解 NP完全问题 NPC 最难的NP问题 超级NP问题 所有NP问题都可规约为NP完全问题 4 计算机求解复杂性及研究进展 计算机求解复杂性NP完全问题 NPC 如果解决了此类问题 则所有NP问题都可以被解决1972年karp给出了标准化的验证方式 证明21个NP完全问题是同复杂度 包括哈密顿回路问题 经销商问题NP hard寻找国际象棋或围棋最佳走法一些指数级问题 4 计算机求解复杂性及研究进展 计算机求解复杂性可能的关系 4 计算机求解复杂性及研究进展 研究进展1970年左右 Cook发现了一些组合优化问题可在多项式时间内相互转化 如果其中一个是P问题 那么其他问题也属于P问题 反之亦然 目前已证明有几千个组合优化问题包含在其中 近年 任意大数质数判断问题被证明为一个多项式问题HPLAB的VinayDeolalikar教授宣布于公元2010年8月6日证明了P NP 在他的主页上 证明过程已经公布 4 计算机求解复杂性及研究进展 研究进展尽管目前没人能给出一个令人信服的证明 但人们普遍倾向于认为P NP 主要原因 1 基于NP 完全理论 人们发现大量的组合优化问题 几千个 有着一样的难解性 一个可以多项式求解 则所有的问题可多项式求解 而没人能给出任一个NP 完全问题的多项式时间算法 2 如果P NP 这个世界与我们所想象的大不一样 当然 P是否等于NP尚没有最后定论 需要解决它需要新的重大的突破 4 计算机求解复杂性及研究进展 研究进展近似算法如何求解NPC NP hard问题 对小规模问题 利用指数时间复杂性算法限制于一些特殊情况 求子问题的最优解 譬如对最大独立集问题 如果限制考虑平面图 或二部图 的话 可以在多项式时间内求解利用启发式算法 heuristic 求问题的一个可行解 如贪婪算法 遗传算法 模拟退火 Localsearch 分支定界等等 参考文献6 设计多项式时间近似算法 ApproximationAlgorithms 参考文献1 pp 633 652 4 计算机求解复杂性及研究进展 研究进展近似算法对于NPC NP hard问题 启发式算法与近似算法 ApproximationAlgorithm 的主要区别在于 前者无法在理论上给出所求的解与真正最优解的差距 即算法有多好 或多坏 一般仅通过数值模拟来判定算法好坏 后者强调对所给问题的任一实例 在多项式时间内求出一个可行解 该解所对应的目标函数值与最优值的偏差在理论上有充分的保证 需要给出理论上严格的证明 4 计算机求解复杂性及研究进展 研究进展启发式算法逆序启发式算法求解MDS根据定理 图的每个极大独立集均为一个极小支配集 而根据定义 图的最小支配集也是极小支配集 故可以把图的极大独立集中基数最少的点集近似作为图的最小支配集 而要找出极大独立集中基数最少的点集 可以按启发式规则实现 4 计算机求解复杂性及研究进展 研究进展启发式算法逆序启发式算法求解MDS对于图G 逆序启发式算法可描述为 步骤1 将V中的顶点按顶点度数从大到小逆序排列成点集V 全部顶点设置为未标号 步骤2 取中V 第一个顶点 若该点已经标号 则在V 删除该点 转至步骤3 否则 将该点标号为1 并将与之相关联且未标号的顶点标号为0 在V 删除该点 步骤3 若V 为空 转至步骤4 否则 转至步骤2 步骤4 取标号为1的顶点作为支配点 把这些点组成的点集为最小支配集 4 计算机求解复杂性及研究进展 研究进展启发式算法禁忌搜索禁忌搜索 TabuSearch TS 是另一个著名的启发式搜索算法 在搜索过程中可以接受劣解 使得Ts在搜索过程中能够跳出局部最优解 进而转向其他区域进行搜索 并通过藐视准则来赦免一些被禁忌的优良状态 从而高优化效率 获得更好的解或全局最优解的概率也大大增加 5 结论 主要结论存在一类不能用常规数学方法求解的问题计算机求解这类问题的局限性 6 对问题的进一步思考 如果P NP被证明正确或者错误 将对计算机研究应用领域带来什么样的冲击 启发式算法求解思路 7 参考文献 ThomasH CormenCharlesE Leiserson著潘金贵顾铁成李成法叶懋译 算法导论 机械工业出版 2006 M R Garey D S Johnson ComputersandIntractability AguidetothetheoryofNP completeness SanFrancisco W H FreedmanandCo 1979 D S Hochbaum eds ApproximationAlgorithmsforNP hardProblems 世界图书出版社 影印 1995 V V Vazirani ApproximationAlgorithms Springer 2002 谢政 李建平 网络算法与复杂