0

現在、正方形と、次のサイズの一連の長方形があります: (225,300)、(225,450)、(450,225)、(300,225)

この正方形内のブロックのすべての可能な組み合わせを重なり合うことなく決定し、常にボックス全体を埋め、各ブロックが無限にあると仮定するアルゴリズムを設計する必要があります。現在、これを効率的に処理するアルゴリズムはありますか?

4

2 に答える 2

3

文献では、効率的=多項式.

正方形を完全に埋めることができることを知っていても、指数関数的な数があるため、可能なすべての方法を見つけることは指数関数的であることに注意してください。

6K * 6K ボードをご覧ください。それを埋める1つの方法は、すべてサイズ6 * 6のK ^ 2サブスクエアに縮小することです。これらのそれぞれについて、(6,3)または(3,6)を使用して作成できます-結果として、2^(K^2)可能な方法で埋めることができます広場。（そして、それを行うためのすべての可能な方法をまだカバーしていません）.

したがって、ALL ソリューションの生成は、多項式 (=効率的) に行うことはできません。
バックトラッキング/徹底的な検索ソリューションを使用して、可能なすべてのプレースメネットをチェックして、目的の結果を取得します。

元の回答は、特定の問題のいくつかの問題を無視し、より一般的なバリエーションに直面しています(与えられたボードは正方形ではなく長方形であり、タイルは固定サイズではありません):

ただし、正方形の長方形1を完全に塗りつぶす方法があるかどうかを判断する問題はNP-Hardです。そのプライベート ケース (「ボード」とサイズ nxm の 1 つの可能な長方形が与えられた場合) は、このスレッドで説明されています。は NP 困難であることが証明されているため、この問題の既知の多項式解はありません。

可能性のあるタイリングがあるかどうかを判断することは NP 困難であるため、それらすべて (またはそれらの 1 つでも) を見つけることは、多項式的にも行うことができません ( P=NPを除きますが、ほとんどの場合、可能性は低いと考えられます)。

(1) 元の回答では正方形と書いていますが、長方形を想定しています。正方形の場合、単一の答えを見つける方が簡単な場合があり、還元は成り立ちません。

于 2012-12-25T13:18:28.553 に答える
1

正方形を塗りつぶすのに4種類の長方形だけを使用すれば、この問題を解決できます。

入力： N
出力：寸法Nの正方形を長方形（3,4）、（3,6）、（6,3）、および（4,3）で埋めることができるかどうかを判断します。

答えは、次の場合にのみ当てはまります。

  1. Nは正の整数です
  2. N mod 6 == 0

以下は私の説明です。

  1. 整数を加算した分数を取得できなかったため、Nは整数である必要があります。
  2. N mod 6 == 1の場合、この正方形の面積mod 6==
    1。Nmod6== 2の場合、この正方形の面積mod 6==
    4。Nmod6== 3の場合、この正方形の面積mod6== 3.
    N mod 6 == 4の場合、この正方形の面積
    mod6==4。Nmod6== 5の場合、この正方形の面積mod 6==1。
    与えられた各長方形の面積は6の倍数であるため、これらの正方形をこれらの長方形で埋めることは不可能です。
  3. N mod 6 == 0の場合、この正方形を（3,6）または（6,3）で埋めることができます。
于 2012-12-25T15:58:43.340 に答える