Bin Packing 问题

in Blog Posts, Computer Vision (机器视觉), Solution, 文章

Bin Packing 问题

Bin Packing 问题

实际项目中同事提出来需要解决这么一个子问题:我们有一堆大小不同的小图,希望可以把它们拼接起来成为几张大小相同的大图,尽量保持大图的数量越少越好。

这个问题挺有趣的,当时直觉上判断这个是NP的,应该是很难快速地得到最优解的。同时也觉得这个问题抽象出来之后应该是有被仔细研究过的。周末有点时间RE-Search了一下,果然这是一个很经典的问题,叫Bin Packing,也确实是NP的。

准确的说,Bin Packing是开头那个问题的一维版本,开头的问题是2D Bin Packing的一个特殊情况。继续走到更高维度去,比如3D的Bin Packing就很接近于集装箱装货的场景了,这个问题的名字可能也就是这么来的。

Bin Packing 在 wiki 上有很详细的介绍: 给定N个数值,分成K份,每个分区的和不大于B,K最小的解就是最优解。这个问题也分为两个版本: 在线(online) 的版本,和离线(offline)的版本。在线的版本是特殊情况,也就是数值是逐个给出的,每次拿到一个新的数值之后,需要决定把它放到哪个Bin里面,或者是新开一个Bin。常用的好实现的算法都是近似解,有很多人做了数学上的证明说一个算法能保证得到的解的质量。对于离线版本,基本上就是从大到小排序之后跑一个在线版本的算法,就可以提升解的质量。

挺有趣的是,这个问题还是在被研究。特别是在对应的exact algorithm这块。wiki上提到的最新的版本,居然是2013年发在IJCAI上的文章。粗看了一下,是从Branch-and-cut这套方法做的,没有找到开源的实现,估计得是比较好的solver才有的了。

到这为止还只是讨论的一维的Bin Packing。实际2D的情形更加复杂,但是也更加实用。找到了一篇2010年的Survey对这个问题做了很好的一个总结。对于这个问题被研究的程度,文章的标题说明了一切: A Thousand Ways to Pack the Bin – A Practical Approach to Two-Dimensional Rectangle Bin Packing。Github有对应的代码实现: https://github.com/juj/RectangleBinPack

再次感觉到很多时候,实践中遇到的问题,合适地抽象出来之后,很有可能只是某个很经典问题的特例。新的问题并不多。

Write a Comment

Comment