次の演習を解決しようとしています(「アルゴリズム設計マニュアル」から取得)
与えられた n 桁の番号を標準の押しボタン式電話で 2 本の指を使ってダイヤルする最も怠惰な方法を計算したいと考えています。2 本の指が * キーと # キーから始まり、あるボタンから別のボタンに指を移動するのに必要な労力は、それらの間のユークリッド距離に比例すると仮定します。合計距離が最小になるように指を動かすダイヤル方式を計算するアルゴリズムを設計します。ここで、k はキーパッドの個別のキーの数です (標準の電話では k = 16)。O(nk^3) 時間を使用してみてください
手始めに、みましょう d=d1.d2....dn be the n-digit sequence
私が思いついたアルゴリズムは、2 つの 2 次元 (nxk) 配列 L、R を使用します。
- L[a][b]:min cost to type the d[a]-digit with the left finger and having
the right finger at button b
- R[a][b]:same thing but with right and left instead.
これらの 2 つの配列を満たすために、2 つのほぼ同一の再帰関数を使用します (そのため、L の 1 つだけを投稿します)。
初めに、
- L[a+1][b]=L[a][b]+cost_from_d[a]_to_d[a+1]
つまり、右指をボタンに置き、左指を d[a] から d[a+1] に動かします。
次に、b==d[a] (つまり、右でダイヤルした最後の数字) の場合、d[a+1] を左指で入力するために、右指を d[ a] ボタンをそのまま押して、どこからでも左指を d[a+1] に移動します。
- L[a+1][b]=min(L[a+1][b],min(R[a][c]+cost_from_c_to_d[a+1]),)
このために、最初に最小コストを見つけて、左で d[a] をダイヤルし、右で d[a] をダイヤルします。次に、それを上の箇条書きの値と比較し、最小値を維持します。
配列を埋めた後、最小の L/R[n][whatever] を見つけるだけで、最小のコストを見つけることができます。
私には、このコードは正しいようです。ただし、時間の複雑さがO(nk^3)ではなくO(nk)であることを考えると、確かにいくつかのエラーが発生しました...
これらのエラーがどこにあるのか、誰にも手がかりがありますか?