我想嵌入 3 个 NP-Complete 问题(其中 2 个已知是 NP-Complete,其中 1 个是我自己的想法)。我看到了“这个问题”,并在理论上重新解释了嵌入问题:
- 服务员就是小偷。
- 桌子是商店。
- 食物是具有不同重量的有价值的物品。
- 小偷在抢劫之前知道所有物品的价格和重量。
- 他的目标是最有效的抢劫(使用的背包的最大容量,获得最有价值的物品)抢劫(至少获得 1 件物品)所有商店(完成抢劫之旅的最短路径,也访问每个商店 1 次)。
这部分是嵌入 2 个 NP-Complete 问题。
我的想法是,更多的物品意味着更多的袋子重量。更大的袋子重量会成倍地减慢小偷的速度。所以小偷的另一个目标应该是尽快完成抢劫。
此时,我不确定我的想法是否真的是 NP-Complete。也许,“重力”不仅仅是一个 NP 完全问题。但也许是在旅行推销员和背包问题的背景下。
所以我的问题是:
小偷NP的减速也完全吗?
是否有可能将这三个嵌入式问题简化为一个简单的 NP 完全问题?