从技术上讲，任何一个人，他做的任何一件事都不是必须的。他不必按照老师说的去做，不必按照长辈说的去做，他甚至不必遵守法律，所有的事情都会产生后果，他只需要想好是否愿意承担这些后果。这就是拉格朗日松弛算法背后的理念：采用那些看似不可能的方法，然后将其降级为高昂代价。一旦我们可以越界，哪怕只是一点点，甚至付出高昂的代价，那么原先无法处理的问题就会变得可以处理了。
假如在一场婚礼上有100个人，十张桌子，每张桌子可容纳十个人，这意味着座位安排的可能是一个超过100位数的数字，这个数字甚至远远超过了可观测的宇宙中原子的数量。如果加入一些合理的约束条件，比如相互认识的人坐在一起可以得一分，不认识的人坐在一起就不得分，夫妻坐在一起可以得十分。那么很明显，我们可以发现座位安排是存在一种最优解的，如果要穷举所有座位安排来获得这个最优解的话，那么这个问题的复杂度是不可接受的。
如果用拉格朗日松弛算法来思考上面那个问题的话，可能会放松对每桌最多十人的限制，这样可以让桌子上的人坐得满满的，但是会有空间上的弊端。如果这样的话，这个问题的复杂度就是可以接受的。最终的解决方法很可能不是最优解，但是一定距离最优解很接近。
这种近似的最优解，在很多现实场景中是有实际意义的。比如城市规划，比如疾病控制。生活中也没有什么问题，值得我们花无数的时间去追求一个完美的答案，这就是松弛得意义。
网友评论