4

0 としてマークされ、空きとして扱われる 1 つのボックスを除いて、それぞれ非ゼロ整数が割り当てられた m*m ボックスがあるボードがあります。空きボックスの垂直方向と水平方向の隣人のみが、その場所を空きとして残して、それに向かって移動できます。 .このパズルを解くには、空のボックス (ゼロとマークされたボックス) が最後 (ボードの右下隅) になるように、値の昇順でボックスを配置する必要があります。しかし、他のすべてのエンジニアと同様に、私たちは非常に怠け者であり、最小ステップ数で解決します。

では、バックトラックを除いて、どのようなアプローチに従うべきでしょうか。

m は 500 のオーダーです。つまり、500x500 ボードです。

4

1 に答える 1

0

配列を並べ替えるだけで、目標の状態を見つけることができます。目標の状態がg、パズルを解くためのシンプルだが非効率的なアルゴリズムであるとします。

void solve()
{
    if(current_state == g)
        return;

    foreach(choice c in shifting_choices)
    {
      // shift neighbour
      apply choice;
      solve();
      undo choice;
    }
}

上記のアルゴリズムchoicesでは、基本的にブロックに囲まれたブロックを移動していzerothます。

アルゴリズムを改善するには、A* (ベストファースト) を使用できます。最適な選択を見つけるために、 を使用できますManhattan Distance。基本的に、パズル内であるブロックから別のブロックに到達するために必要な手順です。以下を検討してください。

6 2 1
5 0 3
4 7 8

上記の状況では、移動できますが、2, 5, 3, 7最適な移動を見つけるには、目標の状態を考慮してください。

8 7 6
5 4 3
2 1 0

ブロックをブロックに移動するとzeroth、2 つのブロックの位置が変わります。目標状態内の位置からこれら 2 つのブロックのマンハッタン距離の合計を計算します。最小合計内での選択が最も望ましいでしょう。

Moving 2: 2 + 3 = 5

Moving 3: 1 + 1 = 2

Moving 7: 1 + 1 = 2

Moving 5: 1 + 2 = 3

以前の位置を確認することで、3 と 7 の間のタイを破ることができます。3 は適切な場所にあったため、7 がローカルで最も最適な選択になります。

于 2013-02-15T09:09:16.283 に答える