环球门户网

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

更新时间:2022-08-17 16:33:45

导读 想必现在有很多小伙伴对于假设哈密顿问题是NPC,证明:TSP属于NP-hard问题(现代优化计算方法 邢文旬主编 P50第11题)(Hamilton)为:给...

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

本文到此结束,希望对大家有所帮助。

版权声明:转载此文是出于传递更多信息之目的。若有来源标注错误或侵犯了您的合法权益,请作者持权属证明与本网联系,我们将及时更正、删除,谢谢您的支持与理解。