[問題] 一個 block 找出最少可蓋覆方形個數

作者: EdisonX (卡卡獸)   2015-02-01 15:16:34
標題有點難想,見諒。
假定有一個地圖,座標可用一個格子表示,長相如下
 ABCDEFGHI
1□□□□■■■■□
2□□□■■□□■□
3□□■■■■□■■
4□■■□□■□■■
5□□□□□■□□■
6□□□■■■■■■
紅色點 flood fill 的起始點,
白色點是 flood fill 之結果。
現我想多加一個動作,想用 " 較少 的矩形",
去包覆這個結果,但苦無較有效率的算法可執行。
我可不需 最少 的矩形 ( 因應 空間/時間 考量問題),
但目前連 "暴力法" 的想法真的都卡卡的,
不知目前是否已有有效算法可解決?
給個 KEYWORD 也行,謝謝各位。
作者: Morris1028 (某 M)   2015-02-02 09:32:00
要求覆蓋不可重疊,用數個矩形覆蓋所有白色區域?感覺壓縮算法,如果求最少可以用 DLX 精準覆蓋問題單純找較少,用貪心法,每次找未覆蓋的左上角,往右下盡可能覆蓋最多個數的矩形,直到所有點都被覆蓋。
作者: EdisonX (卡卡獸)   2015-02-02 15:09:00
抱歉,沒說清楚,圈出來的每個矩形彼此間可重疊,先感謝您提供的想法,我會先research
作者: FRAXIS (喔喔)   2015-02-03 00:55:00
矩形可以重疊 那可以覆蓋非白色區域嗎?
作者: EdisonX (卡卡獸)   2015-02-03 00:57:00
@FRAXIS, 非白色區域(上圖完全沒上色的) 不能被覆蓋。
作者: FRAXIS (喔喔)   2015-02-03 04:27:00
那就先找出所有可以使用的矩形每回合挑一個矩形 使得可以多覆蓋的範圍越多越好感覺上像是 set cover 的問題
作者: EdisonX (卡卡獸)   2015-02-05 02:31:00
最後還是用貪心法先爆出來了,幾個例子效率有點差,謝謝各位。

Links booklink

Contact Us: admin [ a t ] ucptt.com