PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者 (卡卡獸)時間9年前 (2015/02/01 15:16), 編輯推噓3(3推 0噓 10→)
留言13則, 3人參與, 最新討論串1/1
標題有點難想，見諒。 假定有一個地圖，座標可用一個格子表示，長相如下 　ＡＢＣＤＥＦＧＨＩ １□□□□■■■■□ ２□□□■■□□■□ ３□□■■■■□■■ ４□■■□□■□■■ ５□□□□□■□□■ ６□□□■■■■■■ 紅色點 flood fill 的起始點， 白色點是 flood fill 之結果。 現我想多加一個動作，想用 " 較少 的矩形"， 去包覆這個結果，但苦無較有效率的算法可執行。 我可不需 最少 的矩形 ( 因應 空間/時間 考量問題)， 但目前連 "暴力法" 的想法真的都卡卡的， 不知目前是否已有有效算法可解決？ 給個 KEYWORD 也行，謝謝各位。 -- 就算把新鮮的肝拿回去，還是一樣寫碼到禿頭，加班到天亮， 永遠當老闆的傀儡 你是不是想這麼做？ 是的話你就拿回去~ 拿啊！！ 九世宅男 : 下輩子不要再讓我幹工程師了 ~ < Kuso 星爺語錄 > -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.74.8 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1422775009.A.60F.html
→
02/02 09:32, , 1F
要求覆蓋不可重疊，用數個矩形覆蓋所有白色區域？
02/02 09:32, 1F
→
02/02 09:33, , 2F
感覺壓縮算法，如果求最少可以用 DLX 精準覆蓋問題
02/02 09:33, 2F
→
02/02 09:35, , 3F
單純找較少，用貪心法，每次找未覆蓋的左上角，往右下
02/02 09:35, 3F
→
02/02 09:35, , 4F
盡可能覆蓋最多個數的矩形，直到所有點都被覆蓋。
02/02 09:35, 4F
→
02/02 15:09, , 5F
抱歉，沒說清楚，圈出來的每個矩形彼此間可重疊，先感謝
02/02 15:09, 5F
→
02/02 15:09, , 6F
您提供的想法，我會先research
02/02 15:09, 6F
推
02/03 00:55, , 7F
矩形可以重疊 那可以覆蓋非白色區域嗎？
02/03 00:55, 7F
→
02/03 00:57, , 8F
@FRAXIS, 非白色區域(上圖完全沒上色的) 不能被覆蓋。
02/03 00:57, 8F
推
02/03 04:27, , 9F
那就先找出所有可以使用的矩形
02/03 04:27, 9F
→
02/03 04:28, , 10F
每回合挑一個矩形 使得可以多覆蓋的範圍越多越好
02/03 04:28, 10F
推
02/03 04:34, , 11F
感覺上像是 set cover 的問題
02/03 04:34, 11F
→
02/05 02:31, , 12F
最後還是用貪心法先爆出來了，幾個例子效率有點差，謝謝
02/05 02:31, 12F
→
02/05 02:31, , 13F
各位。
02/05 02:31, 13F
‣ 更多 EdisonX 的文章
文章代碼(AID): #1KpTBXOF (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 EdisonX 的文章
文章代碼(AID): #1KpTBXOF (Prob_Solve)