1

困難な問題を解決しようとしていますが、障害にぶつかったのではないかと心配しています。解決方法のアイデアがありません。ここにいる誰かが似たようなものに出くわしたのではないかと思いました。そうでない場合でも、アルゴリズムを作成するのが好きな人は、解決策を見つけようとすることを楽しんでいると確信しています。

ソートされていない配列が与えられます。2 つの移動のいずれかを行うことができます。配列から任意の要素を取り出し、それを配列の先頭または末尾に移動します。配列が最終的にどのように見えるべきかについても与えられます。最小ステップ数で配列をソートすることになっています。

例：

 5 1 4 3 2 - > starting array
 3 1 2 5 4 - > target array

 Steps: move 5 to the end 1 4 3 2 5 
 move 3 to the beginning  3 1 4 2 5
 move 4 to the end  3 1 2 5 4

ターゲット アレイに到達しました。最小ステップ数は 3 です。

誰でもこれを解決する方法について何か考えがありますか?

4

5 に答える 5

4

秘訣は、2 つの配列間で最も長い共通部分列を見つけることだと思います (これは O(n^2) 時間で見つけることができます。これにより、移動する必要のない最大の可能な数のセットが得られます。逆に、動かさなければならない数字の可能な限り最小のセット. 動かさなければならない数字のセットを取得したら、それらを移動する方法を理解するのはかなり簡単です.

あなたの例では：

(5, 1, 4, 3, 2) と (3, 1, 2, 5, 4) の間の最長共通部分列は、(1, 4)、(1, 2)、(3, 2)、または (5 、4)。各サブシーケンスは、移動の最小数が 3 であることを示しています (ただし、選択する移動は明らかにそれぞれ異なります)。

編集

これは基本的に正しい答えだと思います (Vaughn からいくつかの変更があります)。

まず、最長共通部分列問題 (M[i][j] = source[i] と target[j] で終わる最長共通部分列の長さ) に対して、通常どおりに部分列の長さの配列を作成します。

次に、解を選択する代わりに、考えられる最長の共通部分列をすべて列挙します。

次に、ターゲット シーケンス内の最長連続ブロックの長さである各サブシーケンスにスコアを割り当てます。

この例では、次のようになります。

(1, 2) - スコア 2 (1, 4) - スコア 1 (3, 2) - スコア 1 (5, 4) - スコア 2

最大スコアのシーケンスを選択し、適切な移動命令を生成して、このシーケンスの前または後に残りの数字を移動します。

于 2013-01-10T14:42:24.717 に答える
0

私はArunMKに同意しますが、彼の説明はかなり欠けています。したがって、Cでの実装を提案します。

#include <stdio.h>
int start[] = { 5, 1, 4, 3, 2 };
int target[] = { 3, 1, 2, 5, 4 };
const int length = sizeof(start) / sizeof(*start);
int canon[length];

void dump_canon()
{
  int i;
  for (i = 0; i < length; i++)
    printf("%d ", target[canon[i]]);
  printf("\n");
}

int main()
{
  int i, j, k;

  /* First "relabel" the array so that the problems becomes: sort the array. */
  for (i = 0; i < length; i++) {
    for (k = 0; start[i] != target[k]; k++)
      /* NO-OP */;
    canon[i] = k;
  }
  printf("Start ");
  dump_canon();
  /* Search for the longuest ascending sequence without holes */
  int longuest_start;
  int longuest_length = 0;
  for (i = 0; i < length; i++) { /* Use i + longuest_length < length for optimisation */
    k = 1;
    for (j = i + 1; j < length; j++) { /* condition can be optimized */
      if (canon[i] + k == canon[j])
        k++;
    }
    if (k >= longuest_length) {
      longuest_start = canon[i];
      longuest_length = k;
    }
  }

  /* Now longuest_start has longuest_length ordered values */
  /* Increase this ordered values stride by picking a number to put just before or after it */
  while (longuest_length < length) {
    for (i = 0; i < length; i++) {
      if (canon[i] + 1 == longuest_start) {
        k = canon[i];
        for (j = i; j > 0; j--)
          canon[j] = canon[j - 1];
        canon[0] = k;
        longuest_start--;
        longuest_length++;
        printf("Take %d and move it to the beginning: ", target[k]);
        dump_canon();
      }     
      else if (canon[i] == longuest_start + longuest_length) {
        k = canon[i];
        for (j = i; j < length - 1; j++)
          canon[j] = canon[j + 1];
        canon[length - 1] = k;
        longuest_length++;
        /* XXX We just shifted a new value here, redo this index */
        i--;
        printf("Take %d and move it to the end: ", target[k]);
        dump_canon();
      }
    }
  }
}

出力は次のとおりです。

Start 5 1 4 3 2 
Take 5 and move it to the end: 1 4 3 2 5 
Take 4 and move it to the end: 1 3 2 5 4 
Take 3 and move it to the beginning: 3 1 2 5 4
于 2013-01-13T22:57:28.747 に答える
0

O(n^2) ソリューションで十分な場合、非常に単純なアルゴリズムがあります。

n 回繰り返します。ここで、n は配列の長さです。反復 i で、要素 i から n までの要素のうち、対象の配置で最も高い位置にある要素を見つけ、それを配列の先頭に移動します。

反復 1 は、最後にする必要がある要素を最初に移動します。繰り返し 2 は、最後にあるはずの要素をその直前に移動します。... 反復 n は、最初にあるはずの最後の要素を配列の先頭に移動します。

于 2013-01-10T15:03:14.857 に答える
0

A* / IDA* 検索アルゴリズムでそれを行うことができます。すでに「開始」と「目標」があり、ヒューリスティック関数は順序付けられたサブ配列の数にすることができます。新しいノードの作成は、要素の開始/終了への移行を行います...そして、アルゴリズムに魔法をかけてもらいます

于 2013-01-10T18:54:49.773 に答える
0

@High Performance Mark のアドバイスに従えば、ランキング メカニズムを廃止できます。配列の場合、再ラベル付けは (4, 2, 5, 1, 3) になります。この場合、LCS は (4, 5) と (2,3) です。したがって、これらのいずれかから直接開始して、途中のものを移動できます。

4,5 の場合: 4 より小さいものから順に見て、前に移動します。次に、5より大きいものを昇順に並べます

  • 4、2、5、1、3 (開始) --> 3
  • 3、4、2、5、1 --> 2
  • 2、3、4、5、1 --> 1
  • 1、2、3、4、5（終了）

2,3 の場合: 2 より小さいものから順に見て、前に移動します。次に、3より大きいものを昇順に並べます

  • 4、2、5、1、3 (開始) --> 1
  • 1、4、2、5、3 --> 4
  • 1、2、5、3、4 --> 5
  • 1, 2, 3. 4, 5 (終了)

それぞれに3つの動きがあります。

于 2013-01-10T22:50:44.687 に答える