[问题] 一个 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