发布网友 发布时间:2024-07-03 15:51
共2个回答
热心网友 时间:2024-08-09 06:23
很有意思的题目,证明步骤如下:
博物馆观光计划问题属于NP问题(Clearly it is)
将现有某NPC问题归约到MPDP
证明归约可在多项式时间完成
这种npc证明题目有时候不一定非得从固定的某个现有npc问题来归约,当然如果选的合适,证明起来比较顺畅。但殊途同归,有时候一个问题可以从多个 npc问题归约。
热心网友 时间:2024-08-09 06:26
有点麻烦吧