问题标签 [np-complete]

这是来自的问题

ACM 国际大学生程序设计大赛亚洲区域赛，横滨，2006-11-05

从 x 开始并反复乘以x，我们可以计算出x^3130 次乘法：

编写一个程序，x^n 从x给定的正整数n和n<=200

对于 n = 31，最少 #operations 是 6
对于 n = 50，最少 #operations 是 7

欢迎任何想法。

几天前，我正在研究区间图来解决已知的资源分配问题，因为我们知道有一种贪心方法可以在多项式时间内解决这个问题（色数），并为我们提供区间图中每个顶点的颜色（在一般图中找到色数的问题是 NP-Complete（Karp 的 3-satisfiability reduction））。

我想知道：如果有一个图不是区间图，而是因为它有一个且只有一个长度 > 3 的无弦循环（有一条边，当你删除它时，图变成了区间图），它是否会导致在这种图 NP-Complete 上找到色数的问题？

给定一个集合 A = {a ₁ ,a ₂ ,...,a _n }

给定名为 B ₁ ,B ₂ , ..., B _m的 A 子集。如果一个名为 H 的 A 子集与所有给定的 B 有交集，我们称 H 为“覆盖子集”。对于给定的 A 和 B，是否有任何大小为 K（H 的基数为 K）的“覆盖子集”？证明这个问题是NP完全的。

我们应该将一些已知问题简化为“覆盖子集”问题。

我看过一个关于顶点覆盖问题（VC，已知 Np 完全问题）的 2 近似算法的问题，但我不知道答案。问题如下：使用“生成树”找到顶点覆盖问题的 2 近似算法。好吧，已经为 VC 提出了许多贪婪的方法，但是使用“生成树”的特殊算法具有挑战性。任何想法？

我知道在 NP-HARD 中存在以下问题：给定一个简单的图 G=(V,E)，V 中有两个顶点 v，v'，一个整数 B，以及一个非负长度函数 len：E-> Z+ ，是否有一条从 v 到 v' 长度小于 B的简单路径？

我的问题是：在与以前相同的条件下，如果我们有兴趣在 G 中找到从顶点 v 到 v' 的最长但不一定简单的路径，那么问题仍然存在于 NP-HARD 中吗？

注意：我试图减少汉密尔顿路径，但我仍然无法证明 NP 是否存在问题，可简化为我提到的这个问题。我也查过Garey & Johnson，但我什么也没找到。

我想要一点提示来证明这个问题是否是 NP-HARD。提前致谢！

我假设我们有 2 个标记图 G 和 T 并且算法确定 G 是否是 T 的子图以及主图 T 中的相应顶点和子图 G 应该具有相同的标签

这是问题所在。我想知道是否有一个清晰有效的证据：

顶点覆盖：输入无向 G，整数 k > 0。是否存在覆盖所有边的顶点 S，|S|<=k 的子集？

支配集：输入无向G，整数k > 0。是否存在支配所有顶点的顶点子集S，|S|<= k？

一个顶点覆盖它的入射边并支配它的邻居和它自己。

假设VC是NPC，证明DS是NPC。

我正在尝试解决哈密顿路径问题的略微修改版本。它的修改在于将起点和终点提供给我们，而不是确定解决方案是否存在，我们想要找到解决方案的数量（可能是 0）。

该图以二维数组的形式提供给我们，节点是数组的元素。此外，我们只能水平或垂直移动，不能沿对角线移动。不用说，我们不能从一个城市去两个城市，因为要这样做，我们需要访问一个城市两次。

我写了一个蛮力解决方案，在每个节点上尝试所有 4 个（边缘节点为 3 个或 2 个）可能的移动，然后计算解决方案的数量（当它达到目标并且也看到所有其他节点时），但是它在中等大小的输入（比如 7x7 数组）上运行了荒谬的时间。

我也想过使用双向搜索，因为我们知道目标，但这并没有真正帮助，因为我们不仅希望边缘相遇，我们还希望确保所有节点都已被访问。此外，当两个边缘之间的所有节点都用尽时，它们可能会以无法连接的方式结束。

我觉得有一些我不知道的东西让我只有一个蛮力解决方案。我知道问题本身是 NP 完全的，但我想知道是否对蛮力有任何改进。有人可以提出其他建议吗？

- 编辑 -

我提到使用双向搜索并没有真正的帮助，我想澄清我为什么这么认为。考虑一个 2x3 图形，左上角和右下角节点分别是起点和目标。让双向搜索的边缘从起点向右移动，从目标向左移动。在 2 次移动之后，所有节点都会被访问，但无法加入边缘，因为我们只能从一个节点向一个方向前进。但是，正如大卫在下面的回答中指出的那样，可以通过一些修改使算法工作。

这是我的问题：P2P 网络中有 n 个对等点，它们请求相同的数据块；并且有一些限制。1.对等点有自己的上传带宽，平均带宽就是数据块的大小。2. 对等体对这个数据块有不同的期限。如果一个节点在截止日期前没有获得整个区块，它必须搜索服务器帮助。3. 只有拥有整个数据块的对等方才能传输数据（部分或全部）。

目标是最小化服务器的总上传量，我无法弄清楚它是否具有最佳算法或者它是一个 NP 问题。截止时间优先或最大带宽优先可能无法处理某些情况是不是有一些类似这样的NP问题？这就像一个图流问题或一个指令调度，但我发现这很难，因为我必须同时处理截止日期和供应商总带宽的增长。我希望我能得到一些关于解决方案的方向或资源:) 谢谢。

我对寻找图的最小带宽的 NP 完全“最小带宽”问题很感兴趣。对于那些不熟悉的人，这里有一个关于它的链接......

http://en.wikipedia.org/wiki/Graph_bandwidth

我已经实现了 Cuthill-McKee 算法，这非常成功地为我提供了带宽减少的顶点的排列；但是，我正在寻找最小带宽，而不仅仅是接近的减少带宽。如果你们中的任何人有这个问题的经验，哪些算法提供的解决方案是最小的，而不仅仅是减少的？我不需要任何算法的实际实现，我只想要关于研究哪些算法可以产生实际最小带宽的建议。