假设哈密顿问题是NPC,证明:TSP(旅行商问题)属于NP-hard问题(现代优化计算方法 邢文旬主编 P50第11题)哈密顿问题(Hamilton)为:给定一个无向图G=(N,E),其中N={1,2,…,n}为所有的节点组成的

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/25 01:21:19
假设哈密顿问题是NPC,证明:TSP(旅行商问题)属于NP-hard问题(现代优化计算方法邢文旬主编P50第11题)哈密顿问题(Hamilton)为:给定一个无向图G=(N,E),其中N={1,2,…

假设哈密顿问题是NPC,证明:TSP(旅行商问题)属于NP-hard问题(现代优化计算方法 邢文旬主编 P50第11题)哈密顿问题(Hamilton)为:给定一个无向图G=(N,E),其中N={1,2,…,n}为所有的节点组成的
假设哈密顿问题是NPC,证明:TSP(旅行商问题)属于NP-hard问题(现代优化计算方法 邢文旬主编 P50第11题)
哈密顿问题(Hamilton)为:给定一个无向图G=(N,E),其中N={1,2,…,n}为所有的节点组成的集合,E={(i,j)|i,j∈N}为边集合,是否存在一个闭圈通过所有结点正好一次?

假设哈密顿问题是NPC,证明:TSP(旅行商问题)属于NP-hard问题(现代优化计算方法 邢文旬主编 P50第11题)哈密顿问题(Hamilton)为:给定一个无向图G=(N,E),其中N={1,2,…,n}为所有的节点组成的
首先HC是一个npc问题且是一个搜索问题,假设使用贪心策略的算法A(·)可解HC得到一条哈密顿回路.
再利用无向图G构造tsp的图G',图G中存在的边权值设为1,图G中不存在的边权值设为X(X>1的整数).
这样得到的一个TSP问题可使用算法A(·)来解.
图灵规约条件:(1)问题1,问题2都是搜索问题;
(2)求解问题1的算法A(·)可求解问题2;
(3)算法A(问题1)时间复杂度是多项式时间,则算法A(问题2)也是多项式时间;
所以HC可以图灵规约到这样一个TSP问题实例.
又因为HC是NPC类问题,可以图灵规约到TSP,所以TSP是NP-hard问题