问题标签 [np]

我对搜索算法和回溯编程很感兴趣。目前，我已经实现了算法 X（请参阅我的另一篇文章：确定无冲突集？）来解决精确覆盖问题。这很好用，但我现在有兴趣使用更基本的回溯变体来解决这个问题。我只是无法弄清楚如何做到这一点。问题描述和之前一样：

假设您有一堆集合，而每个集合都有几个子集。

Set1 = {（香蕉、菠萝、橙子）、（苹果、羽衣甘蓝、黄瓜）、（洋葱、大蒜）}

Set2 = {（香蕉、黄瓜、大蒜）、（鳄梨、番茄）}

...

SetN = { ... }

现在的目标是从每个集合中选择一个子集，而每个子集必须与任何其他选定的子集无冲突（一个元素不包含在任何其他选定的子集中）。

例如，我编写了两个 Java 类。集合由单个字符标识，元素是纯数字。

我具体有两个问题：

• 如何以可以使用启发式的方式迭代所有集/子集（选择具有最少元素、最小成本的子集......）
• 如何维护选定的集合+子集及其包含的元素。

我能找到的所有其他示例都是数独或 n-Queens，并且都使用固定的 for 循环。除此之外，我正在考虑一种相当通用的方法，其中可以使用函数“isPossiblePartialSolution”来检查所选路径/集是否可能与先前选择的子集/元素冲突。

下面是两个 Java 类：

和

我在理解使用 NP 问题的减少时遇到了一些困难，希望得到澄清。考虑以下问题：

我知道关于这个主题还有其他主题，但我仍然不确定我是否理解如何进行这样的减少。

据我了解，这就是您处理此类问题的方式。

1. 假设给定的问题可以在多项式时间内解决。
2. 使用给定的问题来解决我们知道在多项式时间内是 NP-Hard 的问题
3. 这就产生了矛盾，所以假设一定是不正确的
4. 因此，给定的问题一定不能在多项式时间内解决

那么，对于这样的问题，这是一个合适的方法吗？

1. 如果我们选择 k 作为图中哈密顿循环的长度（假设有一个），这意味着这个问题可以用来在图中找到哈密顿循环。
2. 因为我们只能在 NP 时间内找到哈密顿循环，所以这个问题也必须只能在 NP 时间内解决。

所以一个问题如下：给你一个图，它是一棵树和你可以使用的边数。从 v1 开始，您选择超出您已经访问过的任何顶点的边。

一个例子：

在此示例中，最佳方法是：

起初我虽然找到从 A 开始的长度为 k 的最大路径是一个问题，这将是微不足道的，但关键是你总是可以选择不同的方式，所以这种方法不起作用。

到目前为止我的想法：

1. 在 k 处砍树，并暴力破解所有可能。

2. 计算所有边到边的成本。成本将包括我们试图去的边缘之前的所有边缘的总和除以为了到达该边缘而需要添加的边缘数量。从那里为所有边选择最大值，更新成本，然后再做一次，直到达到 k。

第二种方法看起来不错，但它让我想起了背包问题。

所以我的问题是：有没有更好的方法呢？这个问题是NP吗？

编辑：修剪答案的反例：

我在这个数组中有一系列六位数字：

如何从六位数字中的每一个中获取时间？例如：

我希望利用时间进行计算。

我知道他们的完全对应物意味着 NP - 完全是 NP 问题中最难的，而 co-NP-complete 意味着在 co-NP 问题中最难的，但两者之间有什么区别？我的教科书说“是与否是颠倒的”，这并没有给我留下太多线索。

和这个问题有点相关。

NP 复杂性类的基于验证者的定义说：

NP是确定性图灵机验证器在多项式时间内接受的语言类别。

P中的所有问题都被认为在NP中。作为解释，通常有以下说法：

给定P中问题的证书，我们可以忽略证书并在多项式时间内解决问题。

验证者需要使用证书并证明问题可以在多项式时间内得到验证。为什么每个人都在说忽略证书并解决问题？解决问题是否等同于提供证书？

我有一个问题......什么是非确定性程序？我有这个练习

为以下语言提供一个非确定性过程： L = {: G=(V,E) 有一个独立集 I st |I| >= k 和顶点 V\I 形成一个哈密顿循环}

谢谢！

在一个完整的n分无向图中，每个分集有n个顶点。我的问题是在图中找到一个最小权重n -clique。我想知道这个问题是否可以在多n时间内解决。

条款的更多细节：

Complete k-partite graph：当且仅当它们属于不同的部分集时，顶点相邻的图（维基百科）。图中有 k 个子集。在我的问题中，k = n。

Clique：图 G 中的一个 clique 是 G 的一个完全子图；也就是说，它是顶点的子集 S，使得 S 中的每两个顶点都由 G 中的一条边连接（维基百科）。

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

请注意，所需 clique 的大小是n，它是完整 n 部图中的最大 clique 大小，并且总是可以实现的。

我已经搜索了几个小时，似乎没有研究解决确切的问题。有什么建议么？

几周前，我遇到了一个问题，我几乎可以分解为旅行商问题的变体。曲折是：

有多个推销员。城市列表在动态增加（如实时输入）每个城市仅在有限的时间内完全盈利，如在一定时间后城市将返回较少的奖励并且有一个总体时间限制

显然，这个问题是NP。我想知道是否有任何好的 TSP 近似值可以被修改以适应这个问题？

在 MathExchange 中交叉发布以引起更多响应。

==================================================== ===============================

当我意识到之前有人问过这个问题时，我正在 StackOverflow 中写我最初的问题。

原来我有所谓的子集和问题，所以我去了维基百科并找到了这部分。

但是我在理解维基百科中编写的伪代码时遇到了问题。

例如，我认为目标是找到可以匹配 S 的最接近的一组数字。

但这里 S 是一个列表。这个元素为 0 的 S 列表是什么？

到底是 if y + cs/N < z ≤ s什么？我什至如何用代码写出来？

我希望有人能帮我把它翻译成 php 代码。

至少我对此比较熟悉。它不必是完整的翻译。

只要答案让我足够理解这个近似算法，让我自己用 php 代码编写它，就可以了。