3

n個の個別のラベルを持つグリッドを作成しようとしています.n個のラベルのいずれかで各セルにラベルが付けられ、すべてのラベルがグリッド内のどこかに（エッジごとに）他のすべてのラベルに隣接するようになります（場所は気にしません）。ラベルは何度でも自由に表示できますが、グリッドはできるだけ小さくしたいと考えています。例として、1 から 5 までの 5 つのラベルのグリッドを次に示します。

3 2 4
5 1 3
2 4 5

これを手動で生成することは、少数のラベルではそれほど悪くはありませんが、多数のラベルに対して妥当なサイズのグリッドを生成するのは非常に難しいようです。力ずくの捜索。これは以前に調査されたにちがいないと思いますが、私が見つけた最も近いものは De Bruijn tori であり、私が探しているものとはまったく異なります。どんな助けでも大歓迎です。

編集：次の改善された説明についてBenawiiに感謝します：

「整数 n が与えられた場合、x≠y および x,y ∈ {1,...,n} であるすべてのペア (x,y) に対して、値が行列内に隣接するセルのペアが存在する、可能な限り最小の行列を生成します。 x と y です。」

4

1 に答える 1

0

単純な貪欲なアルゴリズムを試すことができます。

少なくとも質問が厳密に定義されていないため、厳密な数学的証明を提供できるとは思いませんが、アルゴリズムは非常に直感的です。

まず、1...K 個の番号 (K 個のラベル) がある場合、完全にカバーするには、少なくとも K*(K-1)/2 個の隣接セル (接続) が必要です。サイズ NxM の行列は、(N-1)*M+(M-1)*N=2*N*M-(N+M) 接続を生成します。

「最小マトリックス」の下で何を理解しているかについて言及していないので、面積を意味していると仮定しましょう。その場合、特定の領域に対して正方行列がより多くの接続を生成することは明らかです。これは、他の 4 つのセルに隣接する「内部」セルが多いためです。たとえば、エリア 16 の場合、マトリックス 4x4 は 2x8 よりも優れています。「より良い」は直感的です。より多くのつながりがあり、目標に到達する可能性が高くなります。ターゲットの正方行列を使用して、必要に応じて拡張します。上記の式は 2*N*(N-1) になります。

次に、次の貪欲なアルゴリズムを試すことができます。

  1. 入力番号 K について、2*N*(N-1)>K*(K-1)/2 となるような N を見つけます。簡単な学校の方程式.
  2. 隣接行列 M を保持し、すべての i に対して M[i][i]=1 を設定し、残りのペアに対して 0 を設定します。
  3. サイズ NxN の結果の行列 R を初期化し、「空の値」マーカー (たとえば -1) で埋めます。

  4. 左上隅から開始し、右下に繰り返します。

    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
                R[i][j];
  5. そのようなR[i][j]（現在は-1）ごとに、「最適な」値を見つけます。繰り返しますが、「最適」は直感的な定義です。ここでは、新しい未使用の接続に寄与する値を理解しています。そのため、すでに満たされたセルの隣接番号のセットを作成します-S、そのサイズは最大で 2 (上と左の隣接) です。次に、S の両方の数値 x に対して M[x][k]=0 となる最初の k を見つけます。そのような数値がない場合は、少なくとも 1 つの新しい接続を試してください。1 つでも数値がない場合は、両方の隣接が完全にカバーされているため、いくつかの数値を入力します。ここで明らかになった - おそらく「最悪の状況」にあるもの - そのような x Sum(M[x][i]) は最小です。また、いずれにせよ複数の選択肢がある場合は、「最悪の状況」にあるものを選択する必要があります。
  6. R[i][j] の値を設定したら、新しい接続を S - M[R[i][j]][x] = M[x][R[i] の番号 x でマークすることを忘れないでください。 [j]] = 1。
  7. 行列がいっぱいで、M にマークされていない接続がまだある場合は、別の行を行列に追加して続行します。すべての接続が最後まで見つかった場合は、余分な行を削除します。

このアルゴリズムをチェックして、何が起こるかを確認できます。ステップ 5 は、特に同じ状況でどれを選択するかを推測するための場所です (複数の数字が同じように「最悪の状況」になる可能性があります)。

例：

K=6 の場合、15 個の接続が必要です。

N=4、4x4 正方行列が必要です。理論上、4x3 マトリックスには 17 個の接続があるため、収まる可能性がありますが、4x4 を試してみます。

上記のアルゴリズムの出力は次のとおりです。

1234
5615
2413
36**

4x3でできるかどうかはわかりませんが、そうかもしれません... :)

于 2013-08-21T00:29:23.987 に答える