你曾经有过一个商业需求,结果是一个NP完全问题吗?

正如其他人所说,背包(用于包装货物)和旅行推销员问题可能是最常见的“现实世界”NP完全问题。

我经常在工作中遇到无法证明是NP完全或不完整的问题,因为它们没有很好的定义。

任何一种需要在两个以上位置之间找到最佳旅行点的映射工具都可以在不做任何更改的情况下成为 NP-Complete problem

优化仓库拣波问题相当于 Travelling Salesman problem .

也就是说,您有n个订单等待拣货,您希望找到n个最佳订单,以最小化所行驶的距离和拣货员访问的不同拣货位置。

我最近遇到了这个问题。我们提出了一个近似值,它对一般情况很有效,但有时可能会提供次优结果。

此外,背包问题(这是NP硬)经常出现。这是一个试图优化事物的诱人陷阱。

值得注意的是,对于NP完全问题,例如模拟退火和压缩退火,有一些启发式近似技术可以获得“足够好”的答案。如果你能把你的NP完全问题归结为旅行商问题,你可以使用这些方法。(任何NP完全问题都可以简化为任何其他NP完全问题,但实际上,这样做有时会让人头疼。)

不管怎样,有模拟退火和压缩退火实现;其中之一就是 Djinni ,它是用C++编写的,有Python绑定。

当我还是大学生的时候,我同意为一个朋友的父亲写软件。它是为了调度资源。当时我没有意识到,但结果却是一个NP完全问题。

谢天谢地,仅仅找到一个解决方案是可以接受的-不需要找到最佳的解决方案。编写启发式方法——实际上是一组启发式方法——是在程序运行并试图解决问题时改变的,这很有趣。

我有一个解决方案是在一个夏天完成的,但随后每年都要开发新的版本。我出售它的大计划失败了。我是一个比市场营销更好的开发人员。

这很有趣,并且在早期就教会了我很多关于开发的真实世界的知识(最终用户、需求收集、测试等——很多你在本科生中没有学到的东西)。

为了解决你的问题-这是一个老师谁必须安排学生的特殊教学。他是一名言语治疗师和听力学家——但它可以应用于任何类似的领域。他有现有的教师、课堂和学生活动,需要在周围工作,并且每周必须与学生会面特定次数。这是背包问题或任何其他类似/等效的调度问题。

再次证明,仅仅得到一个解决方案是很好的-我们不需要最大化或最小化任何东西-我们只需要容纳所有的学生。

我只记得我无法解决我过去运行场景的测试用例——他在我们解决的这些年中提供的所有问题。

我一直无法推销它——主要是因为我不知道自己在做什么,也不知道如何联系我的市场/买家。

旅行推销员问题就是一个很好的例子。同样的物流问题也适用于航空公司、邮局和各种行业。

另一个例子是,拥有区域分销中心的公司,尤其是那些直接向客户提供服务的公司(如Netflix),需要担心NP家族的完整问题,即 facility location .

事实上,NP完全问题在现实世界中是相关的,这一观点可以通过这样一个事实来证明:它们的近似算法经常出现在运筹学期刊上。

几年前我在研究一个地图程序,就像本地的谷歌地图。我在地图上画了一些位置标记,但是很多标记都是在特定的位置聚集在一起的。我的老板说“让我来做,这样我就可以把标记拖走一点”(它会有一条线或语音气泡指针,从标记到实际位置)。

我认为让用户这样做是愚蠢的,特别是因为他会花5分钟使它完美,然后更改缩放级别,然后一切都会出错。

我决定尝试编写一个函数,以找到一种方法来布局标签,使每个标签到其位置的总屏幕距离最小化。我相信我当时确信这是NP完全的,但是点数可能很小,足以使它仍然可行,至少在许多情况下是这样。(我记得我们在课堂上花了太多时间在NP完整性证明上,而在其他解决方案上却不够:如果你的老板想做点什么,你不能只说“NP难,不会做”——你还得想出 某物 )

然后谷歌地图出现了,只是把所有的标签都贴在了一起,这很糟糕(我每天都诅咒它),但我不能与他们的其他功能竞争,所以我放弃了。: