您是否曾经遇到过一个被证明是 NP 完全问题的业务需求？
在我看来，NP 完备性就像是那些主要只是理论上的东西之一，而不是你在正常工作环境中遇到的真正东西。
所以我很好奇是否有人在工作中遇到过 NP 完全问题，并且需要更改设计以适应它？
NP-completeness seems to me like one of those things that's mostly just theoretical and not really something you'd run into in a normal work environment.
So I'm kind of curious if anyone's ever run into a problem at their job that turned out to be NP-complete, and that the design needed to be changed to accommodate for it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
正如其他人所说，背包（用于包装货物）和旅行推销员问题可能是最常见的“现实世界”NP 完全问题。
我在工作中往往会遇到无法证明是 NP 完全或不完全的问题，因为它们没有得到很好的定义。
As the others have stated, the knapsack (for packing cargo) and traveling salesmen problem are probably the most common "real world" NP-complete problems.
I tend to run into problems at work that can't be proven to be NP complete or incomplete because they're not very well defined.
任何类型的地图工具，您需要在两个以上位置之间找到最佳旅行点，无需任何更改即可成为 NP完全问题
Any kind of mapping tool where you need to find optimal traveling points between more than two locations can without any changes become a NP-Complete problem
优化仓库分批拣货的问题相当于旅行推销员问题。
也就是说，您有 N 个订单等待拣选，并且您希望找到 n 个最佳订单，以最小化拣选员行驶的距离和访问的不同拣选位置。
我最近遇到了这个问题。 我们进行了投注并使用了一种近似值，该近似值对于一般情况来说效果很好，但有时可能会提供次优结果。
The problem of optimizing wave picking from a warehouse is equivalent to the Travelling Salesman problem.
That is, you have N-orders waiting to be picked, and you want to find the n best orders to minimize distance travelled and different pick locations visited by a picker.
I recently came across this problem. We punted and used an approximation that will work well for the average case, but may sometimes provide sub-optimal results.
此外，背包问题（NP 难问题）也经常出现。 这是一个试图优化事物的诱人陷阱。
Also, the knapsack problem (which is NP-hard) shows up fairly frequently. It's a seductive trap for attempting to optimize things.
值得注意的是，有一些启发式近似技术可以为 NP 完全问题获得“足够好”的答案，例如模拟退火和压缩退火。 如果您可以将 NP 完全问题简化为旅行商问题，则可以使用这些方法。 （任何 NP 完全问题都可以简化为任何其他 NP 完全问题，但实际上这样做有时会很痛苦。）
无论如何，有模拟退火和压缩退火的实现； 其中之一是 Djinni，它是用 C++ 编写的并具有 Python 绑定。
It's worth noting that there are heuristic approximation techniques for obtaining "good enough" answers for NP-complete problems, such as simulated annealing and compressed annealing. If you can reduce your NP-complete problem to the Traveling Salesman problem, you can use these approaches. (Any NP-complete problem can be reduced to any other NP-complete problem, but actually doing that is sometimes a pain in the ass.)
Anyway, there are simulated-annealing and compressed-annealing implementations out there; one such is Djinni, which is written in C++ and has Python bindings.
当我还是一名大学一年级学生时，我同意为朋友的父亲编写软件。 是为了调度资源。 当时没意识到，结果发现这是一个NP完全问题。
值得庆幸的是，只要找到一个解决方案就可以接受——不需要找到最佳解决方案。 编写启发式方法（实际上是一组启发式方法）很有趣，可以在程序运行并尝试解决问题时进行更改。
我在夏天完成了一个解决方案，但随后每年都在开发新版本。 我出售它的宏伟计划落空了。 我是一个比营销人员更好的开发人员。
并且很早就教会了我很多关于开发的真实世界的知识 - （最终用户、需求收集、测试等 - 很多你在本科 CS 中无法学到的东西）
这很有趣， 问题 - 这是针对一位必须安排学生接受特殊指导的老师的。 他是一名言语治疗师和听力学家 - 但它可以应用于任何类似的领域。 他有现有的教师、课堂和学生活动需要解决，并且每周必须与学生会面一定次数。 这是背包问题或许多其他类似/等效的调度问题。
事实证明，只要找到一个解决方案就可以了——我们不必最大化或最小化任何东西——我们只需要适应所有的学生。
我只记得无法解决我用来运行场景的测试用例 - 多年来他提供的所有问题我们都解决了。
我从来没能推销它——主要是因为我不知道自己在做什么，也不知道如何接触我的市场/买家。
I agreed to write software for a friend's father when I was a first-year college student. It was for scheduling resources. I didn't realize it at the time, but it turned out to be an NP complete problem.
Thankfully just finding a solution was acceptable - didn't need to find the optimal solution. It was fun writing heuristics - actually a set of them - that could be changed while the program was running and trying to solve the problem.
I had a solution done in a summer, but then worked on new versions each successive year. My big plans to sell it fell flat. I was a better developer than marketer.
It was a lot of fun and taught me early on a lot about the real-world of development - (end users, requirements gathering, testing, etc - a lot of the things that you DON'T get in undergrad CS)
To address your question - it was for a teacher who had to schedule students for special instruction. He was a speech therapist and audiologist - but it could be applied to any similar field. He had existing teacher, classroom and student activities to work around and had to meet some specific number of times per week with students. It is the knapsack problem or any number of other similar/equivalent scheduling problems.
Again, it turned out that just getting a solution was fine - we didn't have to maximize or minimize anything - we just had to accommodate all the students.
I can only recall not being able to solve test cases that I used to run scenarios - all the problems he provided over the years we solved.
I was never able to market it - mostly because I had no idea what I was doing and I was not sure how to reach my market/buyers.
旅行商问题就是一个很好的例子。 同样的物流问题也适用于航空公司、邮局和各行各业。
The travelling salesman problem is a perfect example. The same kind of logistical problems apply to airlines, post offices, and all kinds of industries.
另一个例子是，拥有区域配送中心的公司，尤其是那些直接向客户配送的公司（例如 Netflix），需要担心一系列 NP 完全问题，称为 设施位置。
事实上，NP 完全问题与现实世界相关的想法已经被运筹学期刊中频繁出现的近似算法所证明。
Another example is that companies with regional distribution centers, especially those that deliver directly to the customer (e.g. Netflix), need to worry about the family of NP-Complete problems known as facility location.
In fact, the idea that NP-Complete problems are relevant in the real world is evidenced by the fact that approximation algorithms for them so frequently show up in journals of operational research.
几年前我正在开发一个地图程序，就像原生的谷歌地图一样。 我在地图上放置了一些位置标记，但很多标记都紧密地聚集在某些位置。 我的老板说“让我来实现，这样我就可以将标记拖开一点”（并且它会有一条线或语音气泡指针之类的东西从标记到实际位置）。
我认为让用户这样做是愚蠢的，特别是因为他花了 5 分钟使其完美，然后更改缩放级别，然后一切都会出错。
我决定尝试编写一个函数来找到一种布局标签的方法，以使每个标签到其位置的总屏幕距离最小化。 我相信我当时说服了自己，这是 NP 完全的，但点数可能足够小，至少在许多情况下仍然可行。 （我记得我们在课堂上花了太多时间在 NP 完整性证明上，而在替代解决方案上花费了足够的时间：如果你的老板想要完成某件事，你不能只是说“NP 很难，不会做”——你仍然必须想出一些东西。）
然后谷歌地图出现了，只是将所有标签都放在一起，这完全很糟糕（我每天都咒骂它），但我不能与他们的其他功能竞争所以我放弃了。 :-(
I was working on a mapping program a few years back, like a native Google Maps. I put little markers on the map for locations, but a lot of markers were clustered closely at certain locations. My boss said "let me make it so I can just drag the markers away a little" (and it'd have a line or speech-bubble-pointer-thingy going from the marker to the actual location).
I thought it was silly to make the user do this, especially since he'd spend 5 minutes making it perfect, and then change the zoom level, and then everything would be wrong.
I decided to try writing a function to find a way to lay out labels such that the total screen distance from each label to its location was minimized. I believe I convinced myself at the time that this was NP-complete, but that the number of points might be small enough for it to still be feasible, at least in many cases. (I remember thinking we spent way too much time in class on NP-completeness proofs, and not enough on alternative solutions: if your boss wants something done, you can't just say "NP hard, won't do" -- you still have to come up with something.)
Then Google Maps came along and just splatted all the labels on top of each other, which totally sucks (and I curse it every day), but I can't compete with their other features so I gave up. :-(