2

宿題 (C++) に問題があります。完全な解決策を求めているわけではありませんが、正しい方向に傾けることが役立つ場合があります。:)

NxN ボード (最大 N = 100) とそのボードに 1x2 の図形 (キューブ) があります。立方体は片側が赤く、反対側が青く塗られています。立方体のデフォルトの位置は、ボードの左上隅、青い面が上です。

B B . .
. . . .
. . . .
. . . .

(4x4 の例、B は青を表します)

黒板に石（障害物）がある可能性があります。 私のフィギュアでできる動き：

  • 時計回りに 90/180/270 度回転させます。
  • 立方体を右/左/上/下の端で反転させて、「上向きの色」を変更できます

たとえば、デフォルトの位置で右反転を使用すると、次のようになります。

. . R R
. . . .
. . . .
. . . .

次に、90度回転を使用します。

. . R .
. . R .
. . . .
. . . .

次に、左にフリップを使用します。

. B . .
. B . .
. . . .
. . . .

もちろん、回転時や反転時は石に着地できません。したがって、問題は - ボードの特定の構成 (フィギュアの位置と石の位置)に対して、最小数の移動と戻りを使用して、デフォルトの位置 (青い面が上向き!) で「立方体を家に持ち帰る」プログラムを作成することです。可能であれば 1、不可能であれば 0 を返します。

この問題は興味深いと思いますが、少し混乱していることを認めなければなりません。特にブルーサイド/レッドサイドの部分。通常の最短経路アルゴリズムの言語で使用できるこれらの動きを「翻訳」する方法が本当にわかりません (そして、これらのいずれも使用したことがありません)。だから、私はあなたが与えることができるすべてのアドバイスに感謝します！:)

4

3 に答える 3

1

考えられる各1x2ブロックと色（赤または青）の組み合わせを頂点として解釈し、エッジとして移動することができます。1回の移動で他の組み合わせから特定の1x2ブロックと色の組み合わせ（頂点）に到達できる場合は、これら2つの組み合わせの間に接続（エッジ）があります。次に、結果のグラフで、指定された構成と「ホーム」構成の間の最短経路を見つける必要があります（移動のコストはどの移動を実行しても同じであるため、おそらく幅優先探索）。

さらに進みたい場合は、グラフトラバーサル中にヒューリスティックを使用する高度なグラフ検索アルゴリズムを使用できます（ヒューリスティックは、黒板に障害物がないと仮定して、目的地に到達するために必要な最小移動量です）。たとえば、A*アルゴリズムを使用できます。

于 2012-05-27T23:41:32.260 に答える
1

まず、正確な最適パスを見つけるように求められるため、ダイクスタのアルゴリズムを使用します。

このアルゴリズムには、次のものが必要です。

  1. 次の可能な動きを与える関数。
  2. 位置がすでに訪問されたかどうかを知らせる関数。
  3. 各パスの合計コストを表示する関数。
  4. そしてもちろん、最終位置に到達したことを知らせる機能

初期位置が与えられると、立方体は正確に 7 つの新しい位置に到達できます。可能なものを選択するのは簡単です。

G は単純に、これまでに行った移動の数 + 次の移動の 1 です:)

ハッシュテーブルを使用して、訪問した位置を追跡します。(これはおそらく最も書きにくい関数です) が、今は深く考える必要はありません。単純なベクトルと用語ごとの比較で十分です。コードが実行されたら、これを最適化できます。

最後に、立方体が青い面を上にして最初の位置にあるかどうかを確認する必要があります。

于 2012-05-27T23:26:15.773 に答える
0

この種の問題に対処するとき、最初にすべきことは、問題の状態の表現を見つけることです。この場合、次のものが必要です。

  1. 図の左上の位置を表す2つの整数
  2. 図の色（赤/青）を表す1つのブール値
  3. 図の方向を表す1つのブール値（水平/垂直）

ビットマスクに精通している場合は、これを行うために32ビット整数のみを使用する必要があります（x位置に8ビット、y位置に8ビット、残りに2ビット）。このように、比較演算子を実装する必要はありません。 または、これらの3つの情報と、これに関する厳密な順序の比較を 使用して、単純な構造体（と呼びますstate）を定義します（これは、を入力する場合にのみ必要stateですstd::set。

この後、 BFSを使用してこの問題を解決できます。

そのためには、次のものが必要です。

  1. すでにアクセスしたstd::map<state,state>位置をキーに保存し、元の位置を値に保存します（c ++ 11を使用でき、ビットマスクを使用して状態を保存する場合は、にmap置き換えます）unordered_map
  2. std::queue<state>処理する状態をプッシュおよびポップアップするA。
  3. 与えられた状態から到達可能なすべての可能な状態を決定するためのいくつかのコード（つまり、ボードの寸法を考慮して、すべての可能な動きを実装します）

擬似コード：

   map<state,state>  visited;
   queue<state> to_be_processed;

   visited.insert( initial_state,initial_state); //you are not coming from anywhere
   to_be_processed.push ( initial_state);
   
   while(!to_be_processed.empty()) {

              state cur = to_be_processed.pop();
              if ( cur == end_state) //you are done
              {
                    //to get the path from initial_state to end_state you have just to walk visited in the inverse order.
                    return 1;
              }
              for ( i = every possible state reachable from cur) {
                    if (visited.count(i) != 0) continue; //already visited
                    to_be_processed.push(i);
                    visited.insert(i,cur); //i has been visited, and you reached i from cur
              }

   }
   return 0; //if you get here, no way

障害物が存在すると、問題のコーディングがより困難になりますが、概念的には違いはありません。

この場合、ある状態から別の状態に移行するために支払うコストは常に同じであるため、BFSが機能することに注意してください。

于 2012-05-28T02:02:50.007 に答える