1

次の問題に適したアルゴリズムを知っているかどうか疑問に思っていました。

一辺の長さが 1 の 11 個の正方形が与えられています。それらは他の正方形と重なることはありません。これらの 11 個の正方形を含むことができる小さな正方形はどれくらいですか?

さて、これは未解決ですhttps://math.stackexchange.com/questions/8698/eleven-unit-squares-inside-a-larger-square。しかし、コンピュータによってどの程度の結果が得られるでしょうか?

4

1 に答える 1

1

最もよく知られている最適解は、1979 年にウォルター・トランプによって発見されました。

この問題はパッキング問題であり、より具体的には、正方形の問題における正方形のパッキングです。

アルゴリズム的に解決策を見つけたい場合は、2次元パッキング ヒューリスティックまたは進化的アルゴリズムなどのメタヒューリスティックに基づく近似方法を使用する必要があります。組み合わせ最適化の各問題とアルゴリズムに関する文献は多数あります。それ自体が研究かもしれません。

簡単なグーグル検索の後、いくつかのリンクの下で開始します。

于 2013-03-28T14:25:50.250 に答える