问题标签 [np-hard]

这是我想了很久的问题。作为老师和程序员的儿子，我很早就想到了……但我仍然没有找到解决方案。

所以这就是问题所在。需要使用一些约束条件为一所学校创建一个时间表。这些通常分为两类：

健全性检查

• 一个老师不能同时教两门课
• 学生不能同时上两节课
• 一些教师在一周内必须至少休息一天
• 一周中的所有日子都应包含在时间表中
• 对象 X 每周必须有确切的时间
• ...

优先

• 每位教师的日程安排应尽可能紧凑（即教师应连续工作一天中的所有时间，如果可能，不得停顿）
• 放假的老师应该能够表达对哪一天的偏好
• 从事兼职工作的教师应该能够表达偏好是在上学的开始还是结束时工作。
• ...

现在，在几年没有找到解决方案（同时学习一两件事......）之后，我意识到这闻起来像是一个 NP 难题。

它被证明是NP难的吗？

有没有人知道如何破解这个东西？

看着这个问题让我想到了这个问题，以及在这种情况下遗传算法是否可用。然而，在保持健全性检查规则的同时改变可能性是相当困难的。我也不清楚如何区分不兼容的要求。

一个小的附录，以更好地说明问题。这适用于意大利学校风格的教室，所有学生都在不同的班级（例如：第一年 A 部分）并且教师在班级之间移动。同一班级的所有学生都有相同的时间表，并且无法选择参加哪节课。

我在大学时在 NP Completeness 的背景下学习了 TSP。我从来没有真正遇到过适用于实际问题的情况。一些研究表明，它已被用来选择最便宜的移动钻头的路径，即在电路板上打孔。这几乎是我能找到的所有东西。

你在用吗？TSA 还有哪些其他实际应用？

给定一个项目数组，每个项目都有一个value和cost，确定以最小成本达到最小值所需的项目的最佳算法是什么？例如：

请注意，最后的总体价值：成本比是无关紧要的（A + A会给你最好的物有所值，但A + B + B它是一个更便宜的选择，它达到了最小值）。

对于一个拥有 1000 万玩家的在线扑克网站，描述合谋检测算法复杂性的最佳方式是什么？

假设（我认为这些假设没有太大区别，因此请随意忽略它们，但只是为了澄清）：

• 该网站拥有10,000,000个注册用户。
• 即这些玩家一共玩了50亿手牌。
• 您获得的唯一信息是该网站的“主手牌历史数据库”，其中包含所有玩家底牌和每手牌的下注动作。
• 换句话说，您可能不会走捷径，例如检查 IP 地址、寻找不寻常的抽水/盈利模式等等。
• 假设您有一个函数，当传递一组恰好 N（其中 N 在 2 到 10 之间）玩家时，如果该组中的所有玩家都串通在一起，则返回 TRUE。如果部分但不是所有玩家是共谋者，则该函数返回 FALSE。TRUE 的返回值是（例如）75% 的置信度。

Your job is to produce an exhaustive list of every player who's colluded, along with a complete list of the players he's colluded with. I have recently heard this problem described as NP-hard but is this accurate? Sometimes we call things "NP" or "NP-hard" that are merely "hard".

Thanks!

这是我似乎在使用会计系统时遇到的一个问题。

我有一组交易，但它们的总和不等于会计部门认为应该的金额。他们不是在质疑数学，只是在质疑交易：p

是否有一种算法可以帮助我确定不应该包含集合中的哪些交易以使总和与给定金额匹配。

编辑： 集合中的事务少于 100 个。有没有人有一个 C# 示例，因为在 XKCD 问题中解决 NP 完全问题没有一个？

伙计，我应该获得CS学位。

我有一个强连接的有向图（即，对于图 G 中的每对节点（i，j），都有一条从 i 到 j 和 j 到 i 的路径）。我希望从这个图中找到一个强连通图，使得所有边的总和最小。

换句话说，我需要以这样一种方式摆脱边缘，即在移除它们之后，图形仍将是强连接的，并且边缘总和的成本最低。

我认为这是一个NP难题。我正在为一小组数据（如 20 个节点）寻找最佳解决方案，而不是近似值。

编辑

更一般的描述：给定一个图 G(V,E) 找到一个图 G'(V,E') 使得如果在 G 中存在从 v1 到 v2 的路径，那么在 G 中也存在 v1 和 v2 之间的路径' 和 E 中每个 ei 的总和是最不可能的。所以它类似于找到一个最小等价图，只是在这里我们想要最小化边权重的总和而不是边的总和。

编辑：

到目前为止我的方法：我想过使用多次访问的 TSP 来解决它，但它是不正确的。我的目标是覆盖每个城市，但使用最低成本路径。所以，我猜这更像是封面设置问题，但我不确定。我需要使用总成本最低的路径覆盖每个城市，因此多次访问已经访问过的路径不会增加成本。

我需要编写一个程序（大学项目）来解决（大约）一个 NP 难题。它是线性排序问题的一种变体。一般来说，我将有非常大的输入（作为图表）并会尝试找到最佳解决方案（基于将“评价”每个解决方案的函数）

如果我用 C 风格的代码（一个 main 和函数）编写这个或构建一个 Solver 类，创建一个实例并从 main 调用一个“运行”方法（类似于 Java），会有什么不同吗？

此外，每次迭代都会进行大量浮点数学运算。

谢谢！

NP、NP-Complete和NP-Hard之间有什么区别？

我知道网上有很多资源。我想阅读您的解释，原因是它们可能与外面的不同，或者有些我不知道。

我面临一个 3 维装箱问题，目前正在对哪些算法/启发式目前产生最佳结果进行一些初步研究。由于问题是 NP 难题，我不希望在每种情况下都能找到最佳解决方案，但我想知道：

1）什么是最好的精确求解器？分支和绑定？我可以期望通过合理的计算资源解决哪些问题实例大小？
2）什么是最好的启发式求解器？
3) 有哪些现成的解决方案可以进行一些实验？

抱歉，问题标题不是很清楚，这是一个具有挑战性的问题，无需提供更具体的示例。考虑以下场景：

我有一些朋友的生日即将到来（d1..dn），我设法想出了一些我想以成本购买他们的礼物（c1..cn）。不幸的是，我每天只能存下固定数量的钱（m）来购买这些礼物。我想问的问题是：

什么是每件礼物的理想储蓄分配（mi，其中 mi 从 1..n == m 的总和）以最小化我朋友的生日和我存够钱的日期之间的总偏差购买该礼物。

我正在寻找的不是这个问题的解决方案，就是我可以用来确定性地回答这个问题的已解决问题的映射。感谢您的思考，如果我能提供任何额外的说明，请告诉我！