blocks|key|446864|text|正如其他人所说，背包(用于包装货物)和旅行推销员问题可能是最常见的“现实世界”NP完全问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|446865|我倾向于在工作中遇到不能被证明是NP完全或不完整的问题，因为它们没有很好的定义。|446866|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

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.

blocks|key|446737|text|任何一种需要在两个以上位置之间找到最佳出行点的制图工具，无需任何更改即可成为NP-Complete+problem|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|446738|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Traveling_salesman_problem^0|12|J|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

Any kind of mapping tool where you need to find optimal traveling points between more than two locations can without any changes become a <a href="http://en.wikipedia.org/wiki/Traveling_salesman_problem" rel="nofollow noreferrer">NP-Complete problem</a>

blocks|key|3666552|text|从仓库中优化拾波的问题等同于Travelling+Salesman+problem问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3666553|也就是说，您有N个订单等待挑库，并且您希望找到n个最佳订单，以最小化挑库者访问的距离和不同的挑库位置。|3666554|我最近遇到了这个问题。我们使用了一个近似值，这个近似值在一般情况下工作得很好，但有时可能会提供次优的结果。|3666555|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Traveling_salesman_problem^0|E|R|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]]]

The problem of optimizing wave picking from a warehouse is equivalent to the <a href="http://en.wikipedia.org/wiki/Traveling_salesman_problem" rel="nofollow noreferrer">Travelling Salesman problem</a>. 

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.

blocks|key|3666591|text|此外，背包问题(+NP-hard)也经常出现。这是一个试图优化事物的诱人陷阱。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3666592|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Also, the knapsack problem (which is NP-hard) shows up fairly frequently. It's a seductive trap for attempting to optimize things.

blocks|key|1084936|text|当我还是一名大学一年级学生的时候，我同意为一个朋友的父亲写软件。它是用于调度资源的。我当时没有意识到这一点，但事实证明这是一个NP完全的问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1084937|谢天谢地，找到一个解决方案是可以接受的--不需要找到最优的解决方案。编写启发式规则很有趣--实际上是一组启发式规则--可以在程序运行并试图解决问题时进行更改。|1084938|我在一个夏天就完成了一个解决方案，但之后每年都会推出新的版本。我想把它卖掉的宏伟计划落空了。我是一个比营销人员更好的开发人员。|1084939|它很有趣，并且在早期教会了我很多关于开发的真实世界-(最终用户，需求收集，测试，等等-很多你在本科生学不到的东西)|1084940|回答你的问题--这是为一位必须安排学生接受特殊指导的老师准备的。他是一位语言治疗师和听觉学家--但它也可以应用于任何类似的领域。他有现有的教师、课堂和学生活动要处理，每周必须与学生会面一些特定的次数。它是背包问题或任何数量的其他类似/等价的调度问题。|1084941|再一次，事实证明，仅仅是得到一个解决方案就可以了-我们不需要最大化或最小化任何东西-我们只需要容纳所有的学生。|1084942|我只能回忆起不能解决我用来运行场景的测试用例-他在我们解决的这些年里提供的所有问题。|1084943|我从来没有能够销售它-主要是因为我不知道我在做什么，我不确定如何接触到我的市场/买家。|1084944|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|V|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|W|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|X|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|Y|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|Q|$]]

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.

blocks|key|446949|text|值得注意的是，有一些启发式近似技术可以为NP-complete问题获得“足够好”的答案，例如模拟退火和压缩退火。如果您可以将NP完全问题简化为旅行商问题，则可以使用这些方法。(任何NP-complete问题都可以归结为任何其他NP-complete问题，但实际这样做有时会让人头疼。)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|446950|无论如何，有模拟退火和压缩退火实现；其中之一是Djinni，它是用C%2B%2B编写的，具有Python绑定。|offset|length|446951|entityMap|0|LINK|mutability|MUTABLE|url|http://scarydevilmonastery.com/trac/Djinni/wiki^0|0|N|6|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

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 <a href="http://scarydevilmonastery.com/trac/Djinni/wiki" rel="nofollow noreferrer">Djinni</a>, which is written in C++ and has Python bindings.

blocks|key|446707|text|旅行商问题就是一个很好的例子。同样的后勤问题也适用于航空公司、邮局和各行各业。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|446708|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

The travelling salesman problem is a perfect example. The same kind of logistical problems apply to airlines, post offices, and all kinds of industries.

blocks|key|3666773|text|另一个例子是，拥有地区性配送中心的公司，特别是那些直接向客户送货的公司(例如Netflix)，需要担心称为facility+location的NP完全问题家族。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3666774|事实上，NP-完全问题在现实世界中是相关的，这一观点被运筹学期刊上频繁出现的近似算法所证明。|3666775|entityMap|0|LINK|mutability|MUTABLE|url|http://people.brunel.ac.uk/~mastjjb/jeb/or/facloc.html^0|1H|H|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

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 <a href="http://people.brunel.ac.uk/~mastjjb/jeb/or/facloc.html" rel="nofollow noreferrer">facility location</a>.

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.

blocks|key|4512298|text|几年前，我正在开发一个地图程序，就像一个原生的谷歌地图。我在地图上放置了一些位置标记，但许多标记紧密地聚集在某些位置。我的老板说：“让我来做，这样我就可以把标记拖远一点”(它会有一条线或语音气泡指针之类的东西从标记到实际位置)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4512299|我认为让用户这样做是愚蠢的，特别是因为他会花5分钟来完善它，然后改变缩放级别，然后一切都会出错。|4512300|我决定尝试编写一个函数来找到一种布局标签的方法，使得从每个标签到其位置的总屏幕距离最小化。我相信我当时说服自己这是NP完全的，但点的数量可能足够少，至少在许多情况下，它仍然是可行的。(我记得我们在课堂上花了太多时间在NP完备性证明上，而在替代解决方案上花费的时间太少:如果你的老板想要完成某件事，你不能只说"NP+hard，still‘t+do“--你仍然必须想出一些东西。)|4512301|然后谷歌地图出现了，只是把所有的标签都拼凑在一起，这太糟糕了(我每天都在咒骂它)，但我无法与他们的其他功能竞争，所以我放弃了。:-(|4512302|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

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. :-(

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?

Have you ever had a business requirement that turned out to be an NP-Complete problem?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

在我看来，NP完备性似乎只是一种理论上的东西，而不是你在正常工作环境中会遇到的东西。所以我很好奇是否有人在他们的工作中遇到过问题，最终证明是NP-完全的，并且需要改变设计来适应它？

问您是否曾经遇到过业务需求最终成为NP-Complete问题的情况？
EN

回答 9

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问您是否曾经遇到过业务需求最终成为NP-Complete问题的情况？EN

回答 9

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问您是否曾经遇到过业务需求最终成为NP-Complete问题的情况？
EN