6

14-15 パズルの実装に興味があります。 代替テキスト

昇順で 0 ～ 15 の値を持つ配列を作成しています。

S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

今、私がやりたいのは、それらをシャッフルして、パズルの新しいインスタンスを作成することです。ただし、「奇妙な順列」でボードを作成すると、解決できないことはわかっています。

ウィキペディアによると、偶数順列でパズルを作成する必要があります。これは、偶数回のスワップを確実に行う必要があることを意味していると思いますか?

フィッシャー・イェーツをどのように変更して、最後に順列が均等になるようにしますか? 配列内のすべての要素に対してスワップを行うと、16回のスワップになり、偶数順列になると思います。ただし、自分自身とのスワップについて心配する必要はありますか? 有効なパズルがあることを確認する他の方法はありますか?

4

5 に答える 5

4

Fischer-Yates を使用できるはずです。

  • Fischer-Yates を使用してランダム順列を生成します。
  • 偶数かどうかを確認します。
  • 偶数でない場合は、順列の最初の 2 つの要素を交換します。

偶順列 P = x1 x2 .... xn を考えてみましょう。

Fischer yates は、確率 1/n! で P を生成します。

x2 x1 ... xn を確率 1/n! で生成します。

したがって、上記のプロセスが順列 P を生成する確率は 2/n! = 1/(n!/2)

n!/2 は偶数順列の数です。

したがって、上記のプロセスは、同じ確率で偶数順列を生成します。

順列が偶数かどうかを確認するには、順列の反転数のパリティを数えます。

于 2010-05-22T21:07:08.897 に答える
1

ここですでに答えられていることがわかったものは次のとおりです。

「この問題は基本的に、標準的なシャッフル アルゴリズムに少しひねりを加えたものに要約されます。

重要な観察は、15 パズルが解けるためには、順列のパリティと空白の正方形のパリティが同じでなければならないということです。

最初に、その目的のために標準アルゴリズムを使用してランダム順列を作成します。たとえば、クヌース シャッフル アルゴリズム: Random Permutations

Knuth のシャッフル (または Fisher-Yates shuffle ) を使用する利点は、数の交換が必要なため、順列のパリティを簡単に追跡できることです。各スワップは、パリティを保持するか ( swap 1 & 3 の場合)、パリティを変更します ( swap 1 & 2 の場合)。

置換のパリティと同じパリティに空白の正方形を配置すると、完了です。順列のパリティが奇数の場合、ブランクを奇数の正方形 (ランダムに選択された 1,3,5,...) に配置します。順列のパリティが偶数の場合は、空白を偶数の正方形に配置します。」

また、「実際には、連続して生成される約 4 つの順列ごとに、2 つの偶数順列と 2 つの奇数順列で構成されるため、反復ごとのコストも無視できます。」

このサイトもチェックできます: http://eusebeia.dyndns.org/epermute

于 2012-05-20T08:20:46.163 に答える
0

私は実際にアルゴリズム自体を変更しようとはしませんが、おそらくこのアプリケーションでは意味がありません。私が見たところ、2つのオプションがあります。

  1. 順列が均等になるまでシャッフルし直してください。これにより、おそらく平均で順列の半分 (まあ、それよりも少し多く) が破棄されますが、余分な作業は無視できる可能性が非常に高くなります。
  2. ゲームの動き自体を使用してボードをシャッフルします。つまり、数百のランダムな動きをするだけです。すべての部品を取り出して再組み立てするわけではないため、解決できない状態を生成することはできません。
于 2010-04-16T14:47:45.477 に答える
0

Fisher-Yates は、任意の要素を他の要素と交換できる能力に依存しています。これはパズルの物理に反するので、ここでは使用できないと思います。

単純な解決策は、手動で行うことを行い、空のタイルに隣接するタイルの 1 つをランダムに選択して、それと交換することです。良いシャッフルを得るために必要なスワップの回数はわかりません。

于 2010-04-16T14:48:01.020 に答える