织梦CMS - 轻松建站从此开始!

亚洲城

当前位置: 首页 > 影视综艺 >

什么是P问题、NP问题和NPC问题

时间:2018-08-08 09:53来源:亚洲城 作者:王建国 点击:
原文中有几处不是很理解,望赐教。 1. “现在某人拿到了一个求最短路径的问题,问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图,但怎么也算不出来,于

原文中有几处不是很理解,望赐教。
1. “现在某人拿到了一个求最短路径的问题,问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图,但怎么也算不出来,于是来问我:你看怎么选条路走得最少?我说,我RP很好,肯定能随便给你指条很短的路出来。”。那如果这个问题本身就没有小于100的路线,自然也就选不出来,那样岂不就不是NP问题了?
2.“但我要把问题换成这样:试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了,因为除非你试过所有的路,否则你不敢断定它“没有Hamilton回路”。”在这个问题中,我也可以假设我的RP非常好,一下子找到了一条Hamilton回路并验证了它,那这样问题岂不迎刃而解了?因为“图中存在一条Hamilton回路”。

2013年2月26日 14:40 /

(责任编辑:admin)
织梦二维码生成器
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
用户名: 验证码:点击我更换图片
栏目列表
推荐内容