在我看来，NP-completeness 似乎是那些大多只是理论上的东西，而不是你在正常工作环境中遇到的东西。
所以我有点好奇，是否有人在他们的工作中遇到了一个结果证明是 NP 完全的问题，并且需要更改设计以适应它？
Davy8
问问题
562 次
9 回答
7
正如其他人所说，背包（用于包装货物）和旅行商问题可能是最常见的“现实世界”NP-完全问题。
我倾向于在工作中遇到无法证明是 NP 完整或不完整的问题，因为它们的定义不是很好。
于 2009-03-10T01:34:19.710 回答
1
任何需要在两个以上位置之间找到最佳旅行点的映射工具都可以在不进行任何更改的情况下成为NP-Complete 问题
于 2009-03-10T00:48:35.593 回答
1
从仓库优化波次拣货的问题等价于旅行推销员问题。
也就是说，您有 N 个订单等待拣选，并且您希望找到 n 个最佳订单以最小化行进距离和拣货员访问的不同拣货位置。
我最近遇到了这个问题。我们下注并使用了一个近似值，该近似值适用于一般情况，但有时可能会提供次优结果。
于 2009-03-10T00:52:20.250 回答
1
此外，背包问题（NP-hard）相当频繁地出现。这是试图优化事物的诱人陷阱。
于 2009-03-10T01:30:00.703 回答
1
当我还是大学一年级的学生时，我同意为朋友的父亲编写软件。这是为了调度资源。我当时并没有意识到，但事实证明这是一个 NP 完全问题。
值得庆幸的是，只需找到一个解决方案是可以接受的——不需要找到最佳解决方案。编写启发式方法很有趣——实际上是一组启发式方法——可以在程序运行并尝试解决问题时进行更改。
我在夏天完成了一个解决方案，但随后每年都在开发新版本。我出售它的宏伟计划落空了。我是一个比营销人员更好的开发人员。
这很有趣，并且在早期教会了我很多关于现实世界的开发——（最终用户、需求收集、测试等——很多你在本科 CS 中得不到的东西）
为了解决您的问题 - 这是一位必须安排学生接受特殊指导的老师。他是一名言语治疗师和听力学家——但它可以应用于任何类似的领域。他有现有的教师、课堂和学生活动可以解决，并且每周必须与学生见面特定次数。这是背包问题或任何数量的其他类似/等效的调度问题。
再次证明，只要找到一个解决方案就可以了——我们不必最大化或最小化任何东西——我们只需要容纳所有的学生。
我只记得无法解决我用来运行场景的测试用例——他多年来提供的所有问题，我们都解决了。
我从来没有能够推销它——主要是因为我不知道我在做什么，我不知道如何接触我的市场/买家。
于 2009-08-05T18:24:51.253 回答
1
值得注意的是，有一些启发式逼近技术可以为 NP 完全问题获得“足够好”的答案，例如模拟退火和压缩退火。如果您可以将 NP 完全问题简化为 Traveling Salesman 问题，则可以使用这些方法。（任何 NP 完全问题都可以简化为任何其他 NP 完全问题，但实际上这样做有时会让人头疼。）
无论如何，那里有模拟退火和压缩退火实现。其中之一是Djinni，它是用 C++ 编写的并具有 Python 绑定。
于 2009-08-05T18:25:34.653 回答
0
旅行商问题就是一个很好的例子。同样的物流问题也适用于航空公司、邮局和各行各业。
于 2009-03-10T00:48:20.510 回答
0
另一个例子是，拥有区域配送中心的公司，尤其是那些直接向客户交付的公司（例如 Netflix），需要担心被称为设施位置的 NP-Complete 问题系列。
事实上，NP-Complete 问题与现实世界相关的想法得到了证明，即它们的近似算法如此频繁地出现在运筹学期刊中。
于 2009-08-05T18:26:49.253 回答
0
几年前我正在开发一个地图程序，比如原生的谷歌地图。我在地图上放置了一些位置标记，但是很多标记紧密地聚集在某些位置。我的老板说“让我来做，这样我就可以将标记拖开一点”（它会有一条线或语音气泡指针从标记到实际位置）。
我认为让用户这样做是愚蠢的，特别是因为他会花 5 分钟使它完美，然后更改缩放级别，然后一切都会出错。
我决定尝试编写一个函数来找到一种布置标签的方法，以使从每个标签到其位置的总屏幕距离最小化。我相信我当时说服自己这是 NP 完全的，但点的数量可能足够小，至少在许多情况下仍然可行。（我记得我们在课堂上花了太多时间在 NP 完备性证明上，而在替代解决方案上花的时间不够：如果你的老板想要完成某件事，你不能只说“NP 很难，不会做”——你还是得想办法。）
然后谷歌地图出现了，只是把所有的标签都放在了一起，这太糟糕了（我每天都在诅咒它），但我无法与他们的其他功能竞争，所以我放弃了。:-(
于 2009-08-05T18:40:56.557 回答