作者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
推 yoco315:沒有… 01/12 02:40
推 seanwu:"圖形佔最小面積的擺法" <= 這是什麼意思，不是總面積吧? 01/12 08:02
→ seanwu:那麼，你所謂"面積"的意思是...? 01/12 08:03
推 ledia:凸包面積 ? 還是各形狀的聯集圖形面積 ? 不過這些問題都太難 01/12 10:21
→ ledia:只有 greedy 或是 annealing 之類的作法並不意外 01/12 10:21
推 ykjiang:這類問題，只要量到一定規模，只能求個次佳解 01/12 13:07
推 aknow:這可能比2d bin packing更難 01/18 05:46