作者rifiz (萨哈拉雅)
看板Prob_Solve
标题[问题] 请问这类问题的解法
时间Mon Jan 12 00:09:10 2009
想请问前辈们这类问题的解法. 就是给你一堆图形可能是圆形,三角,四边形, 椭圆
跟多边形, 如何找出这一堆图形占最小面积的摆法?
此外, 若是有一些限制条件的话, 该如何以一套演算法下去作?
在网路上google了一下, 大部分是在VLSI的Layout相关领域的研究成果, 大部分是
用greedy, genetic, Anneal 或是 cost function的方式去找, 也就是说算是某种
程度的 "暴力法".........不知道有没有其他的做法呢???
在看这个问题我又想到, 像是俄罗斯方块的游戏, 是否已有程式可以自动玩这个游戏
似乎也可以用上面的做法来解决???
请各位前辈提供一下宝贵的意见~~~谢谢~~~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.169.99.53
※ rifiz:转录至看板 Programming 01/12 00:09
1F：推 yoco315:没有… 01/12 02:40
2F：推 seanwu:"图形占最小面积的摆法" <= 这是什麽意思，不是总面积吧? 01/12 08:02
3F：→ seanwu:那麽，你所谓"面积"的意思是...? 01/12 08:03
4F：推 ledia:凸包面积 ? 还是各形状的联集图形面积 ? 不过这些问题都太难 01/12 10:21
5F：→ ledia:只有 greedy 或是 annealing 之类的作法并不意外 01/12 10:21
6F：推 ykjiang:这类问题，只要量到一定规模，只能求个次佳解 01/12 13:07
7F：推 aknow:这可能比2d bin packing更难 01/18 05:46