问题标签 [np-hard]

我的问题

是否有一种有效的算法可以在完整的k分图中找到最大权重（或最小权重）k-团（根据维基百科，当且仅当它们属于不同的分集时，顶点相邻的图）？

有关条款的更多详细信息

Max-weight Clique：图中的每条边都有一个权重。团的权重是团中所有边的权重之和。目标是找到一个权重最大的集团。

请注意，clique 的大小是 k，它是完整 k-partite 图中可能的最大 clique 大小。

我试过的

我在一个项目中遇到了这个问题。由于我不是 CS 人员，因此我不确定复杂性等。

我搜索了几篇相关论文，但没有一篇涉及相同的问题。我还编写了一个贪心算法+模拟退火来处理它（结果似乎不好）。我也尝试过动态编程之类的东西（但它似乎效率不高）。所以我想知道是否可以有效地计算出精确的最优值。提前致谢。

编辑由于我的输入可能非常大（例如，每个团中的顶点数是 2^k），我希望找到一个非常快速的算法（例如 k 的多项式）来计算出最佳结果。如果不可能，我们可以证明复杂性的一些下限吗？

我有一个带有和等式约束的 0/1 最小化背包问题。然而，更有趣的是，我的权重可以取 0:15 之间的值。我的问题是，我真的可以在多项式时间内解决这个问题吗？如果可以，如何解决？

顺便说一句，我有 n=100 个项目，所有项目的权重 (w_i) 都可以在 0 到 15 之间。此外，当权重在给定范围内发生变化时，我的值 (v_i) 会随着每个项目的变化而变化。我的平等值也是212。

我正式提出了一个问题并完成了这个 ILP：

我试图减少到多个背包问题以证明它是 NP 难的，但由于约束 (4) 我被卡住了。有人可以给我一些建议吗？谢谢

我正在学习复杂性课程。需要清除 NP_Hard 问题。

谢谢，哈伦德拉

假设我们想从$A$ 走到$B$，但是它们之间有几条河流。为了从$A$ 走到$B$，我们需要为每条河流建造一座桥。

我们有几种类型的木板。不同类型的木板成本和长度不同，但相同类型的木板成本和长度相同。我们可以用木板搭桥。但是，可用木板的数量是有限的。我们的目标是为每条河流建造一座桥梁，同时最大限度地降低木板的总成本。

为了更好地描述问题，我们画了一个图来描述我们的问题。

有 3 条河流需要的桥梁长度分别为 $d_1$、$d_2$ 和 $d_3$。

我们有 4 美元的木板。令 $l_i$ 和 $c_i$ 表示第 $i$ 种木板的长度和成本。令$\delta_i$ 表示第$i$ 种木板的可用数量。令 $n_{ij}$ 表示用于建造桥梁 $j$ 的木板数量。

那么问题可以表述如下：

最小化 $\sum_{j=1}^3 \sum_{i=1}^4 n_{ij}c_i$

英石

$\sum_{i=1}^4 n_{ij}l_i \geq d_j$

$\sum_{j=1}^3 n_{ij} \leq \delta_i$

$n_{ij}\geq 0$ & $n_{ij} \in Z$

我认为这个问题应该是 NP-Hard，因为它是一个整数规划问题。这是真的？有谁知道如何解决这个问题？即使是不是最优的解决方案。

折叠背包问题是普通背包问题的推广，其中背包容量是包含物品数量的非增函数。

有没有人知道关于背包容量根据您选择的项目（即，域是项目的权力集）而不是项目数量而变化的变体的任何信息（名称、文献、算法......）？

根据wiki，它将需要（N-1）！计算 N 个城市的旅行。我找到了一种更好的方法，但我无法通过数学计算我改进了多少。我可以告诉你，在我的家用电脑上，我能够在不到 1 小时的时间内解决 20 个城市的地图。20！= 2.43290200e+18。这是我所做的：

当使用 brout 算法搜索 N 个城市的路线（让它们命名：City(1)、City(2)、City(3)...City(N)）时，您将首先执行此测试：City( 1), City(2), City(3), City(4)... City(N) 一段时间后，这个：City(1), City(3), City(2), City(4 )... 城市 (N)。我声称第二次计算是不必要的。如果我只计算一次 City(4) ... City(N) 的最短路线，我可以将其用于第二次计算并确定哪条路线更好。

使用这个技巧，我可以通过以下方式减少我为 K 城市所做的计算次数： (N - k) 这是我可以选择的第一个城市的选项数量，乘以 (N - K - 1) ！这是我必须选择其余城市的选项数量，减去第一次，我需要执行完整计算。所以它将是（N - K）！。您需要对从 k = 3 到 k = N - 2 的所有 K 求和。

这是我所到之处，（不远）......我希望你能帮我计算一下。

编辑：发现了对该算法的改进。欢迎你来看看。

这个问题是对我的老问题的改进。现在我想向您展示Java 代码示例，并更详细地解释我的算法。

我认为我找到了一个多项式算法来获得旅行商问题的精确解决方案。我的实现是从 5 个步骤构建的：

• 1) 快速设置
• 2)寻找解决方案
• 3)停止条件 1
• 4) 停止条件 2
• 5) 停止条件 3

我想从第 2 步和第 3 步开始，如果我没有弄错，我会告诉你剩下的。

所以我现在要向你展示的，不是多项式算法，而是对Held–Karp 算法的改进，可以在 O(n^2 2^n) 时间内解决问题

假设我们想用 brout 算法解决 6 个城市的路线。有（6-1）！= 120 个选项，我们需要全部测试并返回建立的最短路径。所以它看起来像这样（城市名称是：A、B、C、D、E、F）：

• 选项 1：A -> B -> C -> D -> E -> F -> A
• 选项 2：A -> B -> C -> D -> F -> E -> A
• 选项 3：A -> C -> B -> D -> E -> F -> A
• 选项 4：A -> C -> B -> D -> F -> E -> A
• .
• .
• 选项 120

现在我说在计算选项1和2之后，你可以跳过选项3和4。你是怎么做到的？很简单：在计算选项 1 时，您需要计算从 D 市开始，在 A 市结束，然后经过 E、F 城市的最短路线，它实际上是在计算选项 1 和 2。我们要做的是构建一个包含 4 个城市的地图，我们在其中强制执行第一个和最后一个城市，在此示例中，在计算选项 1 时，您创建一个 D、E、F、A 的地图，其中包含最短路径的数据D 到 A 到 E、F。因此，现在当您开始计算选项 3 和 4 时，您可以在到达 D 市时停下来，因为您已经知道从 D 市开始、在 A 市结束并经过 E、F 市的最短路线。

这是我在算法中使用的原理。我运行了一个蛮力算法并映射了所有子结果，这些结果不是子路由，不要在那里混淆。它们只是为了找到最短路径而需要完成的计算的一部分。所以每次我意识到我在做同样的计算时，我都会使用地图中的解决方案。

这是我的算法在 19 个城市上运行的输出。这只是一个样本，但它的意义远不止于此。事实上，它代表了 19 个城市的所有结果。无论 19 个城市的输入是什么，算法总是会创建相同数量的地图，执行相同数量的操作，并且会在相同的时间内解决。

Source(19)是输入城市。我的电脑321550 mills计算了一下，（大约 5 分钟）。Created: 20801457表示创建的搜索实例的数量（我使用地图或创建地图的所有时间。您需要查看代码才能更好地理解这个数字）。Map(3)谈到已创建的 3 个城市的地图数量。创建了2448张3城地图，使用了34272次。

我的算法将在 N 个城市路线中生成具有 K 个城市大小的地图数量将是： 我可以选择地图的第一个城市的次数：N乘以我可以从剩余城市：（n-1）！/（（n - k - 1）！*（k-1）！）。来到n！/ ((n - k - 1)! * (k-1)!)。假设创建一个大小为 3 的地图是一个原子动作，那么我的算法效率将是所有这些地图的总和。

所以我的算法有下一个效率。

N * (N - 1) * (N - 2) / 2！+ N * (N - 1) * (N - 2) * (N - 3) / 3！+ N * (N - 1) * (N - 2) * (N - 3) (N -4) / 4！+ ... N！/（N - 1）！= N * (N - 1) * (N - 2) / 2！+ N * (N - 1) * (N - 2) * (N - 3) / 3！+ N * (N - 1) * (N - 2) * (N - 3) (N -4) / 4！+ ... N

那么这是一种怎样的效率呢？

它看起来像O(N^C*2^N) 的指数函数，其中 C 比 one 小一点。我通过求解效率算法找到了这一点，N 从 7 到 100，并将其与之前的结果（N = 9 和 N = 8 的结果，N = 24 和 N = 23 的结果）进行比较，我发现对于N的大数比较结果是2。然后我用传统的动态规划算法效率做了同样的事情。这是我得到的清单：

第 1 列是 N，第 2 列是我的算法效率比较，第 3 列是动态规划算法比较，第 4 列是我的算法效率乘以 N 比较。

看看第 3 列和第 4 列是如何几乎相同的。我就是这样找到它的。

请验证我的工作，看看代码，告诉我你是否同意我的观点。如果不是，请通过精确样本告诉我我的算法或数学在哪里不起作用。如果你同意我的观点，那么请帮助我更改 wiki 页面，证明我的这部分算法比 Held–Karp 算法更好。

你好，我正在处理以下问题。

给定一个大小为 M x N 且系数为正的矩阵。目标是选择 P 列，以使生成的 M x P 矩阵的每一行中所有元素的最大总和最小化。例如，如果 M = 3，N = 5，P = 2，矩阵由下式给出

a ₁₁ a ₁₂ a ₁₃ a ₁₄ a ₁₅
a ₂₁ a ₂₂ a ₂₃ a ₂₄ a ₂₅
a ₃₁ a ₃₂ a ₃₃ `a ₃₄ a ₃₅

最佳解决方案是选择“第 2 列和第 4 列，得到的矩阵由下式给出

_{12 14 22 24 32 34} _ _
_ _ _ _

并且值 max{a ₁₂ + a ₁₄ , a ₂₂ + a ₂₄ , a ₃₂ + a ₃₄ } 在 P 列的所有选择中最小。

由于有 (N over P) 解决方案，因此可以实现一种简单的指数算法来解决这个问题，但是有没有更快的多项式时间解决方案呢？

或者，如果没有，任何人都可以肯定地证明这是一个 NP-hard 问题吗？你知道任何类似的 NP-hard 问题可以简化为这个问题吗？

你们中的任何人都知道一种解决方案，即使是针对旅行推销员问题的平庸解决方案。我有 3 个人打算访问 31 个目的地……我不知道该怎么办？

谢谢大家 -

格言