NP完全问题或NP困难问题

Question

有没有人在工作中经常解决NP完全问题或NP难题(通过启发式，或追求次优解或其他什么)的现实生活中的例子？我知道它们发生在调度、规划、VLSI设计等方面，但我想了解现在雇用程序员或工程师的主要行业经常这样做。如果要开发专门知识或库，例如组合优化，人们可以在哪里使用它作为编程工作的一部分？

有私人账户吗？

Answer 1

我能想到的一些事情(其中大部分我或多或少都参与过)：

• 语言和编译器的开发环境。例如:这种语法是否会产生一种模糊的语言？(这个问题实际上是无法判定的！)
• 数据恢复。重新组装部分丢失的数据包或恢复分段文件。(阶乘复杂性)
• 软件安全。通过一段软件对所有可能的执行路径进行评估，以确定某些观察到的行为是否可以归因于此。(停止问题？)
• 物流。优化基于数据包的传输的使用，它们的大小和它们必须去的地方。(至少指数)

有很多标准的例子，例如找到最短路径、护士调度等等，但是如果您对组合优化感兴趣，您就会了解这些:)

Answer 2

用时间约束模拟退火法解决了触摸屏制造中的旅行销售员类问题。每毫秒我们可以从激光刻蚀每个面板的周期时间缩短，这将增加机器的吞吐量、利用率和盈利能力，所以我投入了大量的精力来减少刻划路径之间的死时间(非划线路径)(这显然无法被优化)。

我使用了一种有时间限制的算法来绕过问题的NP硬度，因为我们无法承担优化计算可能比最优路径节省的时间更长的风险。当机器将面板从加载位置移动到激光头位于最近角落的位置时，我有时间进行一些模拟。该算法几乎从未在移动后的几百毫秒内完成，但几乎总是返回比我们以前一直使用的任何简单、非自适应模型(例如螺旋形或蛇形路径)更好的划线路径。

Answer 3

我正在研究生物信息学中的多个局部DNA序列比对问题。这其中的要点是，如果很多基因序列具有一些共同的特性(在芯片芯片实验中有相似的表达谱或相同的转录因子结合)，那么你可能已经找到了它们共同特性的原因。再说一遍，我对这个问题的统计方面更感兴趣。尽管这是NP难的，但在实践中使用启发式并不会造成什么损失。这个问题的有趣部分，IMHO，是一个信噪比问题。