【现代优化计算方法】...hard问题(现代优化计算方法邢文旬主编P50第11题)...
答案:2 悬赏:40 手机版
解决时间 2021-02-22 04:00
- 提问者网友：末路
- 2021-02-21 03:12
【现代优化计算方法】...hard问题(现代优化计算方法邢文旬主编P50第11题)...
最佳答案
- 五星知识达人网友：有你哪都是故乡
- 2021-02-21 04:00
【答案】 首先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问题
再利用无向图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问题
全部回答
- 1楼网友：由着我着迷
- 2021-02-21 04:11
感谢回答，我学习了
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯