6

ランダムな分割表を生成する効率的な方法は何ですか? 分割表は、各行の合計が固定され、各列の合計が固定されているような長方形のマトリックスとして定義されますが、各行と各列の合計が正しい限り、個々の要素は何であってもかまいません。

ランダムな分割表を生成するのは非常に簡単ですが、素朴なアルゴリズムよりも効率的なものを探しています。

4

4 に答える 4

6

R のnetworksisパッケージのコードを見ると役立つ場合があります。効率的な計算には凝ったマルコフ連鎖の逐次重要度リサンプリング手法が必要だと私は信じています。

編集: 関連する論文は、Chen、Diaconis、Holmes、および Liu (2005)です。著者の言葉を借りれば、「[私たち] の方法は、他の既存のモンテカルロ ベースのアルゴリズムと比較して優れており、時には桁違いに効率的です。」

于 2009-06-04T06:05:02.550 に答える
1

これは、制約充足問題(CSP) のように思えます。

基本的に、ある時点から開始して、許可された値のセットからセルの値をランダムに選択します。次に、同じ行/列内のすべてのセルの適格な値のセットを更新し、(使用している CSP ヒューリスティックに従って) 次のセルを選択して、適格な値のセットから (ランダムに) 値を割り当てます。繰り返しますが、同じ行/列のすべてのセルの適格な値のセットも更新する必要があります。適格な値のセットが空のセルに遭遇した場合は、バックトラックを行う必要があります。

ただし、許可する値の範囲によっては、「適格な値のセット」の概念をデータ構造で表現するのが難しい場合があります。

于 2009-06-04T05:06:34.723 に答える
0

あなたの素朴なアルゴリズムが何であるかわかりません。ここで私が最初に考えるのは次のとおりです。

m\cdot n線形制約のある変数は、解空間に自由度がm+nあるという期待につながります。(m-1)\cdot(n-1)-1

最初にその数の乱数を選択するとします。

  a11 a12 ... a1[n-1] b
  a21 a22 ... a2[n-1] x2-x1+b
  ... ... ... ... ... ...
a[m-1]1 a[m-1]2 ... df
   c y2-y1+c ... ge

定数x_i=\sum_{j=1}^{n-1}a_{i,j}とを定義しy_j=\sum_{i=1}^{m-1}a_{i,j}ます。

これにより、変数b、c、d、e、f、gに対する次の制約が生じます。

x_1+b=\sum_{j=1}^{n-2}a_{m-1,j}+d+f=(m-2)\cdot(c-y_1)+\sum_{\i=1 }^{m-2}y_i+g+e
y_1+c=\sum_{i=1}^{m-2}a_{j,n-1}+d+g=(n-2)\cdot(c-x_1)+\sum_{j=1} ^{n-2}x_j+f+e

これは 6 変数の線形システムです。おそらく独自の解決策があります…明日それについて取り組みます。(現時点では、Maple やその他のコンピューター代数システムが不足しています。)

于 2009-06-04T06:02:34.223 に答える