最小の移動回数でロックを開ける

Question

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

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

一つだけフリックと同方向に車輪の任意の連続シーケンスを移動することができます。これは、サブシーケンスのすべてのホイールをそのように単一のモーションで移動するのと同じ効果を持ちます。たとえば、ターゲット文字列が'zzzzzzzzz'の場合、'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 

Answer 1

この問題は、と言い換えることができる：

アルゴリズムは、以下の結果が得られなければなりません

W hatは、文字列Sを「a」のみを含む文字列に変換するための最小移動数です。

定義：

は、文字列内の同じ文字の並びとして連続したシーケンスを考えてみましょう。最も小さな連続したサブシーケンスは、当然のことながら、単一の文字です。小さなサブシーケンスを正規化すると、当然、より大きなサブシーケンスになり、最終的に単一のサブシーケンス、つまり文字列全体に到達します。に正規化する何

：

一つは文字だけUPまたはDOWNを移動することができ、そう、文字自体はUPとDOWN動きのシーケンスです。文字の表現の最悪の場合は、アルファベットの中間の文字であり、記述するには少なくともlen(alphabet)/2の移動が必要です。アルファベット{a..z}では、最悪の場合は'm'と'n'です。

私たちは移動の数を最小限にしたいので、私たちはDOWN手紙C <= mを引き出し、そしてそれらC >= nをプルアップする必要があります。したがって、正規化プロセスを最小限に抑えるためには、正規化の動きが等しいことを必要とする最大の部分シーケンスを見つける必要があります。たとえば、ターゲットがzzzzbzzzzの場合、最小方向はUUUUDUUUU - U、UP、D、DOWNです。を正規化

：各移動のため

は、カウンタは、文字列を変換するために必要な移動の最小数を得、インクリメントされます。上記の例を考えると、我々は次のステップを取ることがあります。

# = 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) 

はEDIT：

@ user1884905で指摘したように、この解決策は、提案されているように、は最適ではありません。対象文字列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'）の違いに焦点を当てるのではなく、文字列の文字間のグローバル距離を減らすことにあります。

Answer 2

これは単なる追加情報であり、最適化されている可能性があるので、これはRubensの答えに対するコメントになるはずですが、回答で私はそれをよりよく説明でき、質問者にとっても役立ちます。

私はまた、Rubensの素晴らしい逆の考えを使用します。

だから、aを別のものにローテーションする必要があるとは思えません。これが正しければ（反例はない）、間違った方向に何かを回転させるべき状況はない（私は数学的証明はないが、おそらくこれは正しい）。

したがって、U秒とD秒の各部分列は、1回の動きで毎回回転します。このアルゴリズムはO（n^2）時間はかかりません。ここでは、アルゴリズムは次のとおりです。

たちはdirection string

1. は方向列
2. を計算0
3. にカウンタを設定する方向列をスキャンルーベンスの文字列呼ぶことにしましょう。
4. UまたはD文字の連続した部分シーケンスが見つかった場合は、ターゲット文字列をaの位置で回転させ、カウンタをインクリメントします（各サブシーケンスに対して1回ずつ）。
5. 何らかの操作があった場合、このアルゴリズムはaにすべてのホイールを回転させると、それはkはアルファベットの要素の数である高々k/2スキャン、後に行われる2

に戻ってください。したがって、これは線形時間で実行されるソリューションかもしれません。

---

多分もっと少ない操作で解決策があるかもしれません。それは見つけ増加、減少または「丘状の」サブサブ配列を、最大value.For例を抽出して、単なるアイデアです：私たちは、コンピューティングせずに言うことができ、その

• abcde、
を解決するためのコスト
• ecb、
• abceeddcb

単一e

を解決するためのコストに等しい

EDIT：私はuser1884905の反例を見ました。だから私のアルゴリズムは最適な解を見つけることができませんが、正しいアルゴリズムを見つけるのに使えるので、まだ削除しません。

EDIT 2：サンプルのターゲット文字列で動作する別のアイデア：平均文字を計算することができます。これは、ターゲット文字列の文字からの距離の合計が最小のものです。上記のアルゴリズムを使ってすべての文字をここで回転させ、文字列全体をaaaaaaaaaaに回転させることができます。アルファベットはサイクリックなので、質問の2番目の例のように複数の平均文字がある可能性があります。この場合、最小距離がaから1つを選択する必要があります。