2

これは宿題の質問です（申し訳ありませんが、これらが嫌われていることは承知しています）が、私も教師も実際に効率的に解決する方法を知らないため、SOの素晴らしい頭脳が私たちを助けることができるかどうかを確認するためにここに投稿したいと思いました.

乱数を含む不特定のサイズの配列が与えられます。昇順でソートする必要があります。各要素は、隣接する空きスペースに移動するか、隣接する大きな要素の上に移動できます。与えられた配列をソートするために必要な移動の最小数を返すメソッドを作成する必要があります。

先生が問題が難しすぎることに気付いたので、この問題は「オプション」とラベル付けされましたが、どのように解決されるのか興味があります. 任意のサイズの配列に関する提案 (長さ 3 の配列でもかまいません) を歓迎します。

編集：これが不明確であることを指摘していただきありがとうございます。配列を使用して、架空の現実世界の状況を表しています。コインの例を使用してみましょう: それらはすべてテーブルに一列に並べられており、指定された数の「スペース」しか配置できません。ただし、隣接する大きなコインの上に置くか、スライドさせることができます。隣接する空きスペース（おそらく山の上に移動したコインによって空になった）に。

4

3 に答える 3

1

私にとってより興味深い問題になったので、いくつかの仮定/変更を加えて問題を調べることにしました。

1) 山のどの部分からでも要素を左右に移動できます。

2) エレメントのサイズが大きいか小さいか、同じサイズかに関係なく、要素を山に積み重ねることができます。

3) スタックをどのように通過しても、小さい数値の前に大きい数値に遭遇しない限り、配列はソートされていると見なされます。したがって、_ 11 2 3 はソートされますが、_ _ 12 3 はソートされません。これは、2 が 1 の前にあると解釈できるためです。

この公理にもかかわらず、これは非常に興味深い問題につながります。

公理 A: 移動する順序は関係ありません。同じ最終結果を得るために、どのような方法でも並べ替えることができます。

公理 Ab: 配列に繰り返しがない場合は、すべての要素を最終位置に移動するだけです。

特に、局所的な調査のみで再帰性/バックトラッキングなしで解決できることを期待して戦略を開発しましたが、これが無益であることを証明したので、後で示します。

私の戦略は次のとおりです。

1) 左から右に進み、間違った方向に裏返されたペアを探します (低い数値の前に高い数値)。

2a) 1 つを見つけたときに、右側の値ですぐに満たされる空のスポットまたはスタックがある場合は、それが満たされるまで左に移動します。

2b) それ以外の場合は、左の値を右に移動します。これにより、無関心な数のスタックがある状況が作成されます。最初に、下に比較する前に、1) のロジックに従って、右に移動した値と新しい右にある値を比較します。

2bii) 下方比較を対比較と同じように扱う - 空のスポットまたはスタックに収まる場合は、低い方の値を左に移動し、そうでない場合は、高い方の値を右に移動して続行します。

例:

1231 -> スタックに収まるため、1b を左にシフトします。11 2 3 _

1321 -> 2 は空のスポット/スタックに収まらないため、3 を右にシフトします。1b は空のスポットに収まる/スタックに収まるため、左に 2 回シフトします。次に、2 は空のスポット/スタックに収まらないため、3 を右にシフトします。1 1 2 3

1132 -> 2 は左に移動できないため、3 を右にシフトします。空の場所に収まるので、左に 2 シフトします。1 1 2 3

2311 -> 1a は左に移動できないため、3 を右にシフトします。1b は空の場所に収まるため、左に 2 回シフトします。スタックするので、1a を左にシフトします。1a1b は左に移動できないため、2 を右にシフトします。1a2b は空のスポットを埋めるため、左にシフトします。11 2 3 _

ただし、これら 2 つの開始配列で問題が発生します。

23411 10手が最適、2r 3r 4r 1al*3 1bl*4で11 2 3 4 _.

23111 9 手が最適、2r*3 3r*3 1bl 1cl*2 を _ _ 111​​ 2 3 にする - 23411 戦略の反対! 1 の方が多いため、1 を少なく動かし、23 を多く動かします。

これは、この新しい問題を解決するために単純なローカル比較を行うことはできないことを示しています.

私はまだこの問題について考えています。興味をそそる方法で自明ではないように思えます。私と一緒にこれを考えることを楽しんでくれる人がいるといいのですが:)

于 2013-04-09T07:05:45.673 に答える
0

私が想定し：

  • 「ソート済み」は、スタックが 1 つ残っていることを意味します
  • 移動元スタックの最大数が移動先スタックの最小数よりも小さい場合にのみ、スタックを別のスタックに移動できます (または同等に: スタックは小さい数を一番上にしてソートする必要があり、スタックを別のスタックに移動すると全体が移動します)。他のものの上に積み重ねる）

次に、配列に複数の数値が含まれている場合、明らかに解決策はありません。また、数値の大きさは重要ではなく、ランクのみが重要です。したがって、一般性を失うことなく、配列に数値 1..n が任意の順序で含まれていると仮定できます。また、可能な動きを決定するために、スタックの一番上と一番下だけが重要です。したがって、次のものを保存するだけで十分です。

int[] bottom;
int[] top;

スタックをバラバラにすることはできないので、 の場合にのみスタック i をスタック j に移動するかbottom[i] + 1 == top[j]、解けない状態になってしまいます。ただし、そのような移動が可能なゲーム状態にある場合は、すぐに実行するのが最適です。これは、最終的にこれらのスタックを結合する必要があり、個々のスタックを移動する方が 2 つのスタックを移動するよりも安価だからです。

したがって、唯一の自由度は、最小限の移動回数でスタックを所定の位置に移動する方法です。現時点では、明確な貪欲なアルゴリズムは見当たりません。そのため、最適解を見つけるには、ゲームの位置をグラフにエンコードし、そのグラフに最短経路アルゴリズムを適用して、最短の一連の動きを見つける必要があるかもしれません。

于 2013-04-09T02:10:51.670 に答える
0

編集:誰もが別の問題を解決しているように見えるので、私が解決している問題を述べます (これが正しいと信じています (私たち全員ではありませんか?)): (うまくいけば物事をより簡単にするためにディスクを使用します)理解する）

それぞれが正確に 1 つのディスクを含む n 個の山が与えられた場合、これらのディスクをサイズの昇順に並べます。最終結果には、各パイルにそれぞれ 1 つのディスクが含まれている必要があります。唯一許可されている操作は、1 つのディスクを 1 つのパイルの一番上から隣接するパイルの一番上に移動することです。ただし、小さいディスクの上にディスクを配置することはできないという制約があります。ディスクを空の山に移動するか、最後のディスクを山から移動することができます。したがって、常に n 個のパイルが存在します。(1) 新しいパイルは作成されない可能性があるため、ディスクは元のシーケンスの境界外に移動することはできません。(2) 空の山が残っているため、隣接する位置が空の場合、ディスクをその位置に移動しないと、その位置を超えることはできません。

ノート：

直径 x = 数 x の円盤。

これは最も効率的な解決策ではないかもしれませんが、うまくいくはずであり、誰かに何かを与えるかもしれません.

これは純粋に反復的なプロセスです。すべてのステップの後、サイズ 1 のすべてのスタックで終了します。これは、このアプローチの根本的な非効率性である可能性があります。

解決：

以下を説明するために 1、2、および 5 を使用しますが、これはサイズの順序を示すためのものであり、同じ順序の他の数値についても同じです。

  • 並べ替えられるまで繰り返します。
    • まだ正しい位置にない最大の要素を見つけます (5この場合)
      • (実際には、最大である必要はありません。以下の形式のものであれば何でも構いませんが、要素が本来あるべき場所を超えて移動しないように注意してください)
    • 2 つのケースがあります。
      • 一番左の位置にあり、2 つのケースがあります。
        • 512...-1右に移動、5右に移動、1左に 2 つ移動、で終了152
        • 521...-1左に 2 つ移動2、右に1移動、右に 2 つ移動、5右に移動、1左に 2 つ移動、で終了152
      • 一番左の位置ではなく、2 つのケースがあります。
        • ...251...- 12 つ左に移動5、右に移動、右に移動1、で終了215
        • ...152...-2左に移動1、右に移動、1右に移動、2左に移動、で終了251(その後、前のケースからの手順を実行します)

編集2：

より効率的なソリューション:

  1. 正しい位置にない最小のディスクを見つける
  2. 右側のディスクの上に置きます
  3. すべてのディスクをそのディスク 1 位置の左に右にシフトします
  4. 最小の円盤を左にずらします (既に正しい場所にある小さい方の円盤に遭遇するまで)

可能な前処理ステップ:個別のリストに並べ替えて、最小の要素を効率的に見つける

最適化:円盤を目標位置を超えて右に移動する場合は、前の手順で右側の円盤を右に移動せずに、この円盤をその円盤の上に置きます。これを適切なタイミングで効率的に行う方法は少し複雑かもしれません。効率を上げるために、特定の動きを実行しないことも役立つ場合があります。

例：

52413

// put smallest disk (1) on disk to the right
    1
524_3

// shift disks to the left 1 position right (3 moves - moved 4, then 2, then 5)
    1
_5243

// move 1 all the way left (4 moves)
15243

// same as above for 2

   2
15_43

   2
1_543

12543

最小のディスクが一番右の位置にある場合 (現在の の場合のように3)、これは少し問題です。それを解決する2つの方法：

  • 入れ替え1て2装着（右2ヶ所、1左2ヶ所、左2ヶ所）。次に、移動する空きスポットがあります。小さい要素が 2 つ未満の場合は、オプションではありません。これらの要素は、同じ状況に遭遇した場合に備えて、さらにいくつかの要素を並べ替えるまで修正しないでください。21213

  • もし私たちが持っていれば12453、私たちは単にスロットを開くために4置くことができました（それは問題を遅らせるようなものです）。最初のソートされていないディスク (この場合) が 2 番目のディスク ( ) よりも大きい場合、上記の以前のソリューションで説明したような戦略を使用して、要素を移動してこの条件を満たすことができます。5354

于 2013-04-09T12:59:40.013 に答える