怎么证明最短公共超序列有关问题是np hard
发布时间:2011-06-29 00:38:28 文章来源:www.iduyao.cn 采编人员:星星草
如何证明最短公共超序列问题是np hard?
最短公共超序列问题(Shortest common supersquence):给一些字符串 比如 abc ,bcd
,def
然后可以判断是否有长度为 x 的字符串是这些字符串的父串,换句话说是否有一个长
度为x 的字符串能包含着三个字符串,比如abcdef就能,如果x为6 我们就能找到长度
为6的字符串包含了abc, bcd, def
再给一个例子,如果有这些字符串 abc, bcd, efg, x还是为 6,是否有长度为6的字
符串能包含这3个字符串么?没有!最短的是abcdefg 也就是说这三个字符串的最短公
共超序列长度为7
我现在不需要求最短公共超序列,但是我想证明这个问题是NP hard的,我想用TSP旅行
商问题 或者汉密尔顿路的问题reduce到这个问题上来证明这个最短公共超序列也是
nphard的,因为如果我们能把任何一个nphard的问题reduce到最短公共超序列问题上来
,就能证明最短公共超序列问题也是nphard的了。换句话说,我不明白怎么能给一个旅
行商问题或者汉密尔顿路径的问题,根据这些问题建立出一个最短公共超序列问题,然
后如果最短公共超序列问题可以解决,TSP或者汉密尔顿路径问题就可以解决。
我想了很久也想不明白,没能把模型对上,有知道的么?非常感谢!
--
------解决方案--------------------
http://topic.csdn.net/u/20100427/12/01e86ec2-36bf-4948-8077-d3b55a111771.html
------解决方案--------------------
up!
友情提示:
信息收集于互联网,如果您发现错误或造成侵权,请及时通知本站更正或删除,具体联系方式见页面底部联系我们,谢谢。
其他相似内容:
-
身为程序员一定要学C吗?还是直接学其他语言就可以了?
本来有javascript基础.
但想学c++或者c#.不知道从何开始.
有一次在某网站看...
-
有用双屏幕开发的吗?
RT,本人新手,昨天公司发了个大屏幕的显示器,本来是笔记本,结果我双屏幕切换时把两个显卡驱动都禁用了,两个显示器...
-
急!Microsoft Visual Studio 2010图标显示问题!
一开始我是把VS的那个无穷大似的图标锁定在任务栏里的,后来解锁了,然后桌面上、开始...
-
AIX下如何得知一个文件是否被进程打开?
问题可以参考
http://topic.csdn.net/u/20110809/23/d4d8db23-07eb-4ac3-b212-c5a010820c...
-
推荐一款2000左右的智能机
RT~
------解决方案--------------------
merry christmas
------解决方案--------------------
小...
-
关于 % 的小问题,求解
有这样一句提示信息:
printf("n请输入一个型如2+3*(4+5)-3^2%4*6/2的表达式n");
但在运行后输出是:
请输入...
-
新手求助
大家好,鄙人刚来,菜鸟一个,想知道如何下载别人上传的资源,为什么没有下载链接,是需要一定的分数才能下载还是怎么回事?希望好...
-
CSDN有搜索自己发言或者某人发言的功能吗
请指教
------解决方案--------------------
没有。。。
------解决方案------------...
-
订到2张回成都的车票, 不容易啊, 散分
12点左右就每5分钟刷一次, 从13号到16号就一直只有无坐...
13:55 刷出3张硬卧, 大喜, 结...
-
计算机专业大四应该学点什么东西呢?
我现在的情况是已经保研,计算机专业专业硕士。现在大四上半学期快结束了,寒假和下学期除了毕业...