问题标签 [np-hard]

我有一个大约 1000 种不同资产的列表，我想按我正在制作的游戏的价值对它们进行排名。

玩家有机会选择两个资产篮子之一。例如，他们可能会被问到他们更喜欢 A +​​ B 还是 C。

从大量的篮子偏好列表中，我希望按感知价值对资产进行排名。

这是一些示例输入，相应地玩家说：

即他们宁愿有一个A而不是一个B。他们宁愿有2个A而不是一个B和一个C。等等。

从这个输入中，我认为最有可能的价值排名是：

我应该使用哪种算法来解决这个问题？

有时偏好列表会相互矛盾（一些玩家认为 A > B，其他玩家可能会说 B > A）。如果我有一个单独的玩家技能水平衡量标准，我如何利用它来获得更准确的排名？

我还需要能够处理篮子之间的关系中存在“孤岛”的情况。例如：

即你不能说如果 A <> C。

在我看来，这似乎是一个类似于各种打包算法的优化问题。这个排名问题是 NP 难的吗？

我正在研究一个 NP-hard 问题算法（如手卖家问题），但我找不到合适的算法。如果有人可以帮助我，我将不胜感激。我们有一个(x,y)矩阵，块中有一个机器人，(n,m)矩阵块中有一些垃圾。

我们希望机器人去每个有垃圾的街区，在穿过所有垃圾后，它会回到它的第一个街区。相关问题中有两个条件：

1. 机器人只能水平和垂直移动。
2. 输出是一个整数，它是它经过的路径的长度。此路径必须具有最小长度。

例如，输入是：

垃圾的位置：

输出是：

我得到了某张桌子

专卖店

产品

它们的价格如下所示

假设用户想尽可能便宜地购买 2 家商店的所有东西，是否只有有效的算法呢？

这是旅行购买者问题吗？

经常看到Tabu Search用于解决旅行购买者/旅行推销员，我想研究一下但总是无法弄清楚进展和停止条件，谁能解释一下如何实现?

我目前正在做一项任务，我坚持使用这种方法。

我有一个填字游戏问题，它由一个空网格组成（没有像传统填字游戏那样的实心正方形），宽度和高度在 4 到 400（含）之间变化。

规则：

1. 单词是输入的一部分——包含 10 到 1000 个（含）长度不等的英语单词的列表。
2. 水平词只能与垂直词相交。
3. 垂直词只能与水平词相交。
4. 一个词只能与其他 1 或 2 个词相交。
5. 每封信值一分。
6. 单词周围必须有 1 个网格空间间隙，除非它是相交单词的一部分。

例子：

目标：
在 5 分钟的时间内获得最高分。

到目前为止：
经过一些研究，我知道这是一个 NP-Hard 问题。因此，无法计算出最优解，因为无法检查每个组合。

最简单的解决方案似乎是根据长度对单词进行排序并插入得分最高的单词以获得最高分数（贪婪算法）。

我还被告知一个递归树，其节点由替代的等分词插入组成，背包算法适用于这个问题（不确定实现会是什么样子）。

问题：

1. 是什么让我可以在 5 分钟的时间跨度内检查最大组合数，并根据最大可能的单词列表和网格大小进行缩放？
2. 插入单词时可以应用哪些启发式方法？

顺便说一句，这里的目标是在 5 分钟内获得最佳解决方案。澄清一个有效单词的每个字母得 1 分，因此一个 5 个字母的单词得 5 分。

在此先感谢我整天都在阅读很多关于填字游戏研究论文的数学符号，这似乎让我绕了一圈。

PS：输出不包含任何其他集合的子集。1)If X = {1, 2, 3}是解决方案之一，X {1} {2} {3} {1, 2} {1, 3} {2, 3}则省略 的所有子集。

我知道有一些算法可以解决它。但我想知道是否有多项式算法。如果存在，它是如何工作的？如果不是，如何证明它是一个 NP-hard 问题。

谢谢！

在最终幻想 XIII-3 游戏中，玩家会遇到几个谜题。引入的第一个谜题称为Tile Trial，它向玩家展示了一个瓷砖网格，其中一些上面有水晶。目标是取回所有水晶并到达出口，同时踩到每个瓷砖不超过一次。

http://arxiv.org/pdf/1203.1633v1.pdf的作者表示，这个问题是 NP-Hard，因为可以将特定情况简化为哈密顿循环。我发现这是一个幼稚的假设，因为他开发了一个特定的谜题，虽然符合游戏规则，但恰好涉及哈密顿循环。

看一般情况：我们可以将拼图的每个图块建模为图中的一个顶点。如果两个瓦片相邻，则一个顶点与另一个顶点有一条边。问题在于找到从起始图块到结束图块的路径，同时遍历所有具有晶体的顶点并且不多次访问任何顶点。

我相信这可以简化为 TSP（旅行商问题），我们只需要访问一部分城市。假设有n个城市的常规 TSP 问题。但是，在这个特定问题中，我们不必访问所有n个城市，只需访问其中的一个特定子集m，其中m<=n。不需要访问n中而不是m中的城市，但如果路径m1->m2大于m1->n1->m2则它们可能需要访问。

然而，这个“更简单”的 TSP 问题仍然是 NP-hard 吗？任何人都知道可以用作减少的更好的NP-hard问题吗？

给定n组整数，如何最大化非重叠集的数量？

例如，让给定的sets是，

那么答案将是4，

{1,2,3}并且{1,4,5}不能由不重叠的集合组成，因为 1 在两个集合中都很常见。这是一个NP听说的问题吗？如果有针对该问题的有效解决方案，我将期待一些细节。

[NB]输入集的数量最多为1000 个，每个集最多包含1000 个整数。

假设宇宙是U，子族是S={s11,s12,...s1a,s21,...,s2b,...,sn1,...snz}，每个元素都是U的子集. 现在我想选择 S 中最小数量的元素来覆盖整个宇宙，但请注意，如果选择 s11，则不会考虑 {s12,...s1a}，这与 {s11, 中的所有元素相同， s12,...s1a,s21,...,s2b,...,sn1,...snz}。我知道这完全是一个集合覆盖问题，但我现在不确定我的约束是否满足。是否还是套套问题？谢谢您的帮助。

我正在研究算法，我遇到了这个练习：

“证明没有程序/算法可以确定程序 P 是否在给定的输入 x 上使用未初始化的变量。”

这是我想出的证据：

让我们假设有一个算法 Det 来确定程序 P 是否在给定输入 x 上使用未初始化的变量。

让程序成为

P(x) 如果 Det(P,x) 为真，则不执行任何其他操作变量 i 打印 i

在这里，我们看到了一个矛盾。如果 Det(P,x) 为假，那么我们使用了未初始化的变量。我们没有在其他地方使用未初始化的变量，所以只要它返回 true，它就是错误的。

我不确定我的想法是否正确。