我有一个程序,将计算通过拟合矩形所采取的最小区域.
输入:不同高度和宽度的矩形.
输出:一个包含所有这些矩形的矩形.
规则:不能转动或滚动矩形,它们不能重叠.
我知道这是相关的,或者可能被定义为垃圾箱包装问题(NP-hard).然而,我找到的那些算法通常会对例如宽度设置限制.我没有这样的限制,唯一的目标是让得到的区域尽可能小.
关于什么算法适合获得合适解决方案的任何指针？
http://www-rcf.usc.edu/~skoenig/icaps/icaps04/icapspapers/ICAPS04KorfR.pdf
显然这个问题比起初看起来更难.这是一个有趣的算法,因为它首先猜测一个解决方案,然后改进它,所以如果你不想等待最佳解决方案,你可以运行它一定数量的迭代来获得一个近似的解决方案(更长的时间)你运行它,近似值越好).
| 归档时间： |
|
| 查看次数： |
1927 次 |
| 最近记录： |