23

これは、私が解決しなければならないコンピューター ビジョンの問題のトーンダウン バージョンです。パラメーター n,q が与えられ、n 行 n 列のグリッドの要素に整数 0..(q-1) を割り当てる方法の数を数えなければならない場合を想定して、割り当てごとに以下がすべて真になるようにします。

  1. 2 つの隣接 (水平または垂直) が同じ値になることはありません。
  2. 位置 (i,j) の値は 0
  3. 位置 (k,l) の値は 0

(i,j,k,l) が指定されていないため、出力は (i,j,k,l) の有効な設定ごとに 1 つずつ、上記の評価の配列になります。

ブルート フォース アプローチを以下に示します。目標は、q<=100 および n<=18 で機能する効率的なアルゴリズムを取得することです。

def tuples(n,q):
  return [[a,]+b for a in range(q) for b in tuples(n-1,q)] if n>1 else [[a] for a in range(q)]

def isvalid(t,n):
  grid=[t[n*i:n*(i+1)] for i in range(n)];
  for r in range(n):
    for c in range(n):
      v=grid[r][c]
      left=grid[r][c-1] if c>0 else -1
      right=grid[r][c-1] if c<n-1 else -1
      top=grid[r-1][c] if r > 0 else -1
      bottom=grid[r+1][c] if r < n-1 else -1
      if v==left or v==right or v==top or v==bottom:
        return False
  return True

def count(n,q):
  result=[]
  for pos1 in range(n**2):
    for pos2 in range(n**2):
      total=0
      for t in tuples(n**2,q):
        if t[pos1]==0 and t[pos2]==0 and isvalid(t,n):
          total+=1

      result.append(total)

  return result

assert count(2,2)==[1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1]

更新 11/11 TopCoderフォーラムでもこれを尋ねましたが、彼らの解決策は私がこれまでに見た中で最も効率的なものです (著者の見積もりから、n=10、任意の q で約 3 時間)

4

6 に答える 6

3

これは単純すぎるように聞こえるかもしれませんが、うまくいきます。2 つだけが空になるまで、値をすべてのセルにランダムに分配します。すべての値の隣接性をテストします。分散が許容範囲内に収まるまで、成功したキャストとすべてのキャストの割合の平均を計算します。

リスクはゼロになり、リスクにさらされているのはわずかな実行時間だけです。

于 2010-11-10T21:53:57.607 に答える
2

これは答えではなく、コメントするには長すぎる議論への貢献です。

tl; 博士; Eric Lippert のアルゴリズムやブルート フォース アプローチなど、「可能性を計算し、それらをカウントする」ということになるアルゴリズムは、@Yaroslav のq <= 100andの目標には機能しませんn <= 18

n x 1まず、1 つの列について考えてみましょう。この 1 つの列の有効な番号付けはいくつ存在しますか? 最初のセルでは、q数値から選択できます。縦方向に繰り返すことはできないq - 1ため、2 番目のセルの数字を選択q - 1し、3 番目のセルの数字を選択することができます。q == 100とは、非常に大雑把な有効な色付けn == 18があることを意味します。q * (q - 1) ^ (n - 1) = 100 * 99 ^ 1710 ^ 36

次に、バッファー列 (マスタード列と呼びます) で区切られた任意の 2 つの有効な列 (パン列と呼びます) を考えます。次の場合に、マスタード列の有効な値のセットを見つける簡単なアルゴリズムを次に示しますq >= 4。マスタード列の一番上のセルから始めます。高々 2 つの一意の値を持つパン列の隣接セルについてのみ心配する必要があります。マスタード列の 3 番目の数字を選択します。からし柱の 2 番目のセルを考えてみましょう。前のマスタード セルと隣接する 2 つのパン セルを考慮し、合計で最大 3 つの一意の値を指定する必要があります。4 番目の値を選択します。マスタード欄に記入を続けます。

0 のハードコードされたセルを含む最大 2 つの列があります。したがって、マスタード列を使用して、少なくとも 6 つのパン列を作成し、それぞれが10 ^ 36少なくとも10 ^ 216有効な解の合計について約解を持ち、丸めのために大きさのオーダーを与えるか取ることができます。エラー。

ウィキペディアによると10 ^ 80、宇宙には原子に関するものがあります。

したがって、より賢くなります。

于 2010-11-10T19:21:39.730 に答える
1

更新 11/11 TopCoder フォーラムでもこれを尋ねましたが、彼らの解決策は私がこれまでに見た中で最も効率的なものです (著者の見積もりから、n=10、任意の q で約 41 時間)

私は著者です。41 時間ではなく、わずか 3 時間の並列化可能な CPU 時間です。対称性を数えました。n=10 の場合、(i,j) と (k,l) の実際に異なるペアは 675 しかありません。私のプログラムは、それぞれ約 16 秒必要です。

于 2010-11-12T08:58:01.853 に答える
0

DaveAaronSmithによるディスカッションへの貢献に基づいて貢献を構築しています。

ここでは、最後の2つの制約((i,j)および(k,l))については考慮しません。

1つの列(nx1)だけで、解決策はq * (q - 1) ^ (n - 1)です。


2番目の列の選択肢はいくつですか?(q-1)一番上のセル(1,2)の場合、q-1またはq-2(1,2)/(2,1)の色が同じかどうかにかかわらず、セル(2,2)の場合。

(3,2):q-1またはq-2ソリューションについても同じです。

可能性のある二分木があり、その木を合計する必要があることがわかります。左の子は常に「上と左で同じ色」であり、右の子は「異なる色」であると仮定しましょう。

ツリー上で、そのような構成を作成するための左側の列の可能性の数と、色付けする新しいセルの可能性の数を計算することにより、2つの列を色付けする可能性の数を数えます。

しかし、2番目の列の色付けの確率分布を考えてみましょう。プロセスを繰り返す場合は、2番目の列に均一な分布を持たせる必要があります。これは、最初の列が存在しなかったように、すべての色付けの中で最初の2つの列は1/q、2番目の列の一番上のセルの色が0であると言えます。

一様分布がなければ、それは不可能です。

問題:分布は一様ですか?

回答: 最初に2番目の列を作成し、次に最初の列を作成し、次に3番目の列を作成することで、同じ数のソリューションを取得できます。この場合、2番目の列の分布は均一であるため、最初の場合も同様です。

これで、同じ「ツリーのアイデア」を適用して、3番目の列の可能性の数を数えることができます。

私はそれを発展させて一般式を構築しようとします(ツリーのサイズは2 ^ nなので、明示的に調べたくありません)。

于 2010-11-10T22:00:47.113 に答える
0

他の回答者にも役立つ可能性のあるいくつかの観察:

  1. 値 1..q は交換可能です。これらは文字である可能性があり、結果は同じになります。
  2. 隣人が一致しないという制約は非常に緩いものであるため、ブルート フォース アプローチは過度にコストがかかります。1 つのセルを除くすべてのセルの値がわかっている場合でも、q>8 の場合、少なくとも q-8 の可能性があります。
  3. この出力はかなり長くなります - i、j、k、l のすべてのセットには 1 行が必要です。組み合わせの数は n 2 (n 2 -3) のようになります。これは、最初の規則に従う必要がない場合を除き、2 つの固定ゼロが互いに隣接する以外の場所にある可能性があるためです。n=100 および q=18 の場合、これは最大の困難なケースであり、これは ~ 100 4 = 1 億です。これが最小の複雑さであり、問​​題が現在述べられているため、避けられません。
  4. 単純なケースがあります - q=2 の場合、2 つの可能なチェッカーボードがあるため、ゼロの任意のペアに対する答えは 1 です。

ポイント 3 は、プログラム全体を最小値として O( n 2 (n 2 -3) ) にします。また、ゼロのペアごとに合理的に効率的なものが必要になることも示唆しています。これは、計算を行わずに単純に 1 億行を書き込むにはしばらく時間がかかるためです。参考までに、1 行あたり 1 秒、つまり 1x10 8秒 ~ 3 年、つまり 12 コアのボックスで 3 か月です。

ゼロのペアが与えられたエレガントな答えがあると思いますが、それに対する分析的な解決策があるかどうかはわかりません。ゼロの位置に応じて 2 つまたは 3 つの色でそれを行うことができるとすれば、マップを一連の領域に分割し、それぞれが 2 つまたは 3 つの色のみを使用するようにします。各領域の q (qC2 または qC3) の 2 または 3 に領域の数を掛け、マップを分割する方法の数を掛けます。

于 2010-11-11T06:38:07.160 に答える
0

私は数学者ではありませんが、この問題には分析的な解決策があるはずだと思います。

最初に、Q 色の NxN ボードで多くの異なる色付けが可能であることを計算します (共通のエッジを持つと定義された隣人を含め、同じ色にはなりません)。これはかなり単純な式のはずです。

次に、これらの解のうち (i,j) が 0 である解がいくつあるかを計算します。これは 1/Q の分数である必要があります。

次に、マンハッタン距離 |ik|+|jl| に応じて (k,l) が 0 である残りのソリューションの数を計算し、ボードの端までの距離と、2 で割り切れる距離のように、これらの距離の「パリティ」を計算します。 3で割り切れ、Qで割り切れます。

最後の部分が一番難しいですが、数学が得意な人ならまだいけると思います。

于 2012-06-12T16:10:54.633 に答える