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