※ 引述《march20 ()》之銘言： : 先來大膽假設一件事: : 在所有最佳解中, 至少有一個是符合這個 pattern : ┌───┬───┐ : │ │ │ : │ A │ B │ : │ │ │ : ├───┴───┤ : │ │ : │ C │ : │ │ : └───────┘ : 其中 A 為正方型, B 和 C 為矩型 (可能為正方型, 也可能為長或寬為 0 的退化矩型) 以 7*7 來說，最佳解是 ┌──┬─┬─┐ │3 │2 │2 │ │ ├┬┼─┤ ├──┴┼┤2 │ │4 ├┴─┤ │ │3 │ │ │ │ └───┴──┘ order=9，沒有更好的解了 @"@ 所以不是所有的 optimal solution 都具有上面的形式.. 不過我從這篇 paper 看到一種形式 Tiling a rectangle with the fewest squares http://arxiv.org/pdf/math.CO/9411215 a ┌──┐ │ b│ c │ └───┐ │ │ │ │d │ │ │ │ └──────┘ 也許可以嘗試以 dynamic programming 建立 (a,b,c,d) 的表格來求解.. 不過這個也一樣要證明每個這種形式的最佳解，都必須含有這種形式的子集 我從這個網頁 http://www.stetson.edu/%7Eefriedma/mathmagic/1298.html 上面看到的最佳解 目前看到的都符合這個規則 (修一下文: 剛剛再去看了一下,發現反例了XD) 至於證明的話 在上面那篇 paper 第六節有提到 根據 abcd 的大小，可以分成六種類型 我粗看了一下，他應該是沒有證明 只是提出這種分解的 bound 所以我也不知道這是不是對的..... (是錯的 囧) -- To iterate is human, to recurse is divine. 遞迴只應天上有, 凡人該當用迴圈. 　 L. Peter Deutsch --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.31.171.248 ※ 編輯: yoco315 來自: 61.31.171.248 (11/16 05:01)