※ 引述《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)