请教 如何证明np问题问题为NP

下载作业帮安装包
扫二维码下载作业帮
1.75亿学生的选择
已知TSP是NP难的 证明WTSP是NP难的 是一道数模题 这个要怎么证明?TSP是旅行商问题 WTSP流浪旅行商问题
dsXP56PS20
由哈密顿路构造,设原来求哈密顿路的图1中每条边权值都为1,总边数为n,由于求哈密顿路的图1不是完全图,故新增加权值为n的边使之变为完全图2,假若WTSP会解,我们用WTSP的算法在图2中找出WTSP的路径.若总权值n,则此路径必包含原图1中新增加的权值为n的边,原图中无哈密顿路.由此推出,若WTSP会解,那么我们可以在多项式时间内转化为哈密顿路,而已知哈密顿路是NP难的,所以WTSP是NP难的.
为您推荐:
其他类似问题
我也想问、、、
扫描下载二维码君,已阅读到文档的结尾了呢~~
扫扫二维码,随身浏览文档
手机或平板扫扫即可继续访问
NP完全问题证明1
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由:
将文档分享至:
分享完整地址
文档地址:
粘贴到BBS或博客
flash地址:
支持嵌入FLASH地址的网站使用
html代码:
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布,请您等待!
3秒自动关闭窗口小木虫 --- 500万硕博科研人员喜爱的学术科研平台
&&查看话题
如何证明一个问题是NP完全问题
如何证明一个问题是NP完全问题?
研究生必备与500万研究生在线互动!
扫描下载送金币
浏览器进程
打开微信扫一扫
随时随地聊科研

我要回帖

更多关于 np完全性证明 的文章

 

随机推荐