6

車輪のシステムで作られたロックを考えてみましょう。各ホイールには順番に 26 文字のアルファベットがあり、各ホイールは で初期化されてい'a'ます。ホイールを 1 つ上に動かすと、そのホイールの表示はアルファベットの次の文字に移動します。一方、ホイールを下に動かすと、表示がアルファベットの前の文字に切り替わります。例えば：

['a'] ->  UP  -> ['b']
['b'] -> DOWN -> ['a']
...
['z'] ->  UP  -> ['a']
['a'] -> DOWN -> ['z']

フリックするだけで、隣接するホイールのサブシーケンスを同じ方向に移動できます。これは、サブシーケンスのすべてのホイールを 1 回のモーションでそのように動かすのと同じ効果があります。たとえば、ターゲット ストリングが の場合、'zzzzzzzzz'に変更する 1 つの動きは、一連のホイール全体を から に変更し'a'、ターゲット ストリングに到達してロックを開きます。'z''a''z'

ロックを開くための最小移動回数を決定するにはどうすればよいですか? この問題の動的な解決策はありますか? アルゴリズムは、次の結果を生成する必要があります。

           Target string         | # moves
   ______________________________ __________
1 | abcxyz                       |    5
2 | abcdefghijklmnopqrstuvwxyz   |   25
3 | aaaaaaaaa                    |    0
4 | zzzzzzzzz                    |    1
5 | zzzzbzzzz                    |    3

ケース 1、ターゲットabcxyz:

aaa[aaa] -> DOWN -> aaazzz
aaa[zz]z -> DOWN -> aaayyz
aaa[y]yz -> DOWN -> aaaxyz
a[aa]xyz ->  UP  -> abbxyz
ab[b]xyz ->  UP  -> abcxyz

ケース 5、ターゲットzzzzbzzzz:

[aaaaaaaaa] -> DOWN -> zzzzzzzzz
zzzz[z]zzzz ->  UP  -> zzzzazzzz
zzzz[a]zzzz ->  UP  -> zzzzbzzzz
4

2 に答える 2

4

この問題は、次のように言い換えることができます。

文字列 S を 'a' のみを含む文字列にするには、最小何回移動しますか?

定義:

連続したサブシーケンスは、文字列内の等しい文字のシーケンスと考えてください。連続する最小のサブシーケンスは、当然、1 文字です。小さなサブシーケンスを正規化すると、当然、最終的にはより大きなサブシーケンスになり、最終的には単一のサブシーケンス、つまり文字列全体に到達します。

何に正規化するか:

キャラクターを動かすことができるのは UP または DOWN だけなので、キャラクター自体は UP と DOWN の一連の動きです。文字の表現の最悪のケースは、アルファベットの真ん中の文字であり、少なくともlen(alphabet) / 2移動を記述する必要があります。アルファベット{a..z}では、最悪のケースは'm'と'n'です。

移動回数を最小限に抑えたいので、下の文字C <= mを引き、上に引き上げる必要がありますC >= n。したがって、正規化プロセスを最小限に抑えるには、同等の正規化移動を必要とする最大のサブシーケンスを見つける必要があります。たとえば、ターゲットがある場合、最小限の方向は、上はU、下は D でzzzzbzzzzあることがわかります。UUUUDUUUU

正規化:

移動ごとにカウンターがインクリメントされ、文字列の変換に必要な移動の最小数が得られます。上記の例を考慮すると、次の手順を実行できます。

# = 0 | zzzzbzzzz | UUUUDUUUU  (choose the smallest subsequence to normalize)
# = 1 | zzzzazzzz | UUUUDUUUU  (since 'a' is the base character, we choose
                              the move that increases the largest subsequence;
                              if 'a' was the first or last character,
                              moving it would simply be overhead)
# = 2 | zzzzzzzzz | UUUUUUUUU  (choose the subsequence to normalize)
# = 3 | aaaaaaaaa | _________  (choose the subsequence to normalize)

ターゲット文字列を使用した別の例abcxyz:

# = 0 | abcxyz | _DDUUU  (choose the smallest subsequence to normalize)
# = 1 | aabxyz | __DUUU  (choose the smallest subsequence to normalize)
# = 2 | aaaxyz | ___UUU  (choose the smallest subsequence to normalize)
# = 3 | aaayza | ___UU_  (choose the smallest subsequence to normalize)
# = 4 | aaazaa | ___U__  (choose the smallest subsequence to normalize)
# = 5 | aaaaaa | ______  (choose the smallest subsequence to normalize)

編集：

@ user1884905 が指摘したように、提案されているこのソリューションは最適ではありません。ターゲット string の場合mn、アルゴリズムは最適解に至りません。

# = 0  | mn | DU  (choose the smallest subsequence to normalize)
# = 1  | ln | DU  (choose the smallest subsequence to normalize)
# = 2  | kn | DU  (choose the smallest subsequence to normalize)
...
# = 12 | an | _U  (choose the smallest subsequence to normalize)
# = 13 | ao | _U  (choose the smallest subsequence to normalize)
# = 14 | ap | _U  (choose the smallest subsequence to normalize)
...
# = 24 | aa | __  (choose the smallest subsequence to normalize)

次の手順では必要な移動が少ないため、これは最適ではありません。

#0    #1    #2    ...    #12
mn -> mm -> ll -> ... -> aa

おそらく、貪欲なアルゴリズムの最適な下位構造は、そのような文字と基本ケース ( ) の違いに焦点を当てるのではなく、文字列から文字間のグローバルな距離を縮めることにあります'a'。

于 2013-06-11T23:15:40.680 に答える