平成２６年度秋期午後のアルゴリズム問題である問８の私の解き方・考え方について解説していきます。
問題
IPAの公式サイトで公開されています。このページでは問８についての解説を行います。
https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2014h26_2/2014h26a_fe_pm_qs.pdf
問題の概要
２つの文字列の差異を測る指標である編集距離に関する問題です。
エディットグラフの生成方法と最短移動距離の求め方については設問を解いていく前に理解しておいたほうが良いとおもいます。
エディットグラフの生成方法
エディットグラフの生成方法については、特に(2) – ① – (c)の具体例を考えておくと理解しやすいです。
Str1[X]とStr2[Y]が同じ文字の場合に、(X, Y)から(X+1, Y+1)まで斜線が描かれることになります。
例えば、下で青枠で囲った(2, 0)から(3, 1)までの斜線はStr1[2]とStr2[0]が両方とも”c”であるために描かれたものになります。
同様に緑枠で囲った(2, 5)から(3, 6)までの斜線はStr1[2]とStr2[5]が両方とも”c”であるために描かれたものになります。
他の斜線についても同じ理由で描かれています。
最短移動距離の求め方
こちらは問題文の(4)に説明が記載されています。具体的に図２を用いて(2, 2)までの最短移動距離D[2, 2]の求め方を見ていきましょう。
Str1[1]とStr2[1]が同じ文字（両方とも”b”）のため、(1, 1)から(2, 2)には斜線が引かれています。
ですので(2, 2)に行くための経路と移動距離は下記の3通りになります。
（その座標よりも右上方向にある座標からの移動は必ず移動距離が大きくなってしまいますので候補から外す）
- (1, 2)から距離1で移動：D[1, 2] + 1
- (2, 1)から距離1で移動：D[2, 1] + 1
- (1, 1)から距離0で移動：D[1, 1]
この３つから一番移動距離が小さいものがD[2, 2]と考えられます。
もう一つの例として(3, 2)までの最短移動距離D[3, 2]の求め方を見ていきましょう。
Str1[2]とStr2[1]が違う文字のため、(2, 1)から(3, 2)には斜線が引かれていません。
ですので(3, 2)に行くための経路と移動距離は下記の2通りになります。
- (2, 2)から距離1で移動：D[2, 2] + 1
- (3, 1)から距離1で移動：D[3, 1] + 1
この２つから一番移動距離が小さいものがD[3, 2]と考えられます。
つまり、D[X, Y]は、Str1[X-1]とStr2[Y-1]が同じである場合、下記の３つの中から最小となる値となり、
- D[X – 1, Y – 1]
- D[X – 1, Y] + 1
- D[X, Y – 1] + 1
Str1[X-1]とStr2[Y-1]が違う場合、下記の２つの中から最小となる値となります。
- D[X – 1, Y] + 1
- D[X, Y – 1] + 1
この辺りを頭に置いて設問を考えていきましょう。
スポンサーリンク
設問１
[ a ]と[ b ]に関してはちょうど問題の概要で説明した内容になります。D[X, Y]が、
- D[X – 1, Y – 1]
- D[X – 1, Y] + 1
- D[X, Y – 1] + 1
の３つの中から最小となる値となるのは「Str1[X – 1]とStr2[Y – 1]が同じ文字」の場合です。したがって[ a ]の答えは「Str1[1] = Str2[1]」です。
また、二つの文字列の編集距離は座標(0, 0)から座標(Str1Len, Str2Len)までの最短距離となり、その最短距離はD[Str1Len, Str2Len]に格納されています。したがって二つの文字列の編集距離はD[Str1Len, Str2Len]であり、[ b ]の答えはD[Str1Len, Str2Len]となります。
設問２
設問2は実際にStr1を”peace”、Str2を”people”とした時のプログラムの実行結果が問われている問題です。
[ c ]についてはエディットグラフの作成の仕方を理解した上で、Str1[X]とStr2[Y]とで同じ文字となるXとYを見つけ出し、それに対応する「座標(X, Y)から座標(X + 1, Y + 1)の斜線」が存在するグラフを選択肢ア〜オから選べば解けるはずです。具体的にはStr1[X]とStr2[Y]は下記のX・Yの6パターンで同じ文字となります。
- X = 0、Y = 0
- X = 0、Y = 3
- X = 1、Y = 1
- X = 1、Y = 5
- X = 4、Y = 1
- X = 4、Y = 1
↑この全組み合わせに対応する(X, Y)から(X + 1, Y + 1)へ斜線が引かれているグラフが解答となります。ア・イ・エに関しては(0, 0)から(1, 1)の斜線がありMせんし、オに関してはStr1[0]とStr2[1]の文字が異なるため、(0, 1)から(1, 2)への斜線があるのがおかしいですし、他にも不要な斜線がたくさんあります。
一方、オに関しては上で挙げた６つの座標全てから斜線が引かれていますのでオが正しいグラフと言えます。したがって[ c ]の答えはオとなります。
続いて[ d ]を解いていきましょう。αはStr1[X]とStr2[Y]が同じ場合に実行されます。Str1[X]とStr2[Y]が同じになるのは上で挙げた６パターンの場合のみですので、αは６回実行されることになります。したがって[ d ]の答えは６です。
[ e ]はβが実行される回数を答える問題です。βはStr1[X]とStr2[Y]が異なる場合に実行されます。Str1の文字列長が５、Str2の文字列長が６であり、Str1[X]とStr2[Y]が同じなのは６パターンですので、βは２４回（５×６ー６）実行されることになります。したがって[ e ]の答えは２４です。 [ f ]はStr1とStr2の編集距離すなわち最短移動距離となります。プログラムを実際に動かした時にD[Str1Len, Str2Len]の値が何になるかを考えれば答えは導け出せます。またエディットグラフが分かっていますので、最短移動距離がいくらになるかをグラフから読み取ることも可能です。例えば下記のピンク色の矢印で示す経路は最短移動距離となる経路になります（他の経路で最短移動距離となるものは他にもあります）。
斜線は移動距離が０ですので、最短移動距離は５となります。したがって[ f ]の答えは５です。
解いてみた感想
編集距離という概念を初めて知ったのでいい勉強になった問題でした。
グラフを使って距離を求めるというプログラムになっていますので処理のイメージも湧きやすくて解きやすかったです。
★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください！
基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ
本ページの図・プログラム・問題文について
図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。
出典：平成２６年度 秋期 基本情報技術者試験（FE）試験区分 午後 問８
アルゴリズム問題の対策（PR）
過去問を解いてみて感触はいかがだったでしょうか？
全く分からなかった...という方もいらっしゃるかもしれません。はっきりいってアルゴリズム問題は、特に慣れないと難易度は高いです。
なので、こういった方にはもっと "簡単なアルゴリズム問題を解いて慣れていく" ことをオススメします。で、この簡単なアルゴリズム問題を解くのにオススメの本が下記の うかる！ 基本情報技術者 [午後・アルゴリズム編] です。
オススメする理由は、特に本の前半部分で難易度の低いアルゴリズムの紹介や解説が行われているところです。こういったアルゴリズムの動作などを実際にトレースして追ってみたりすることで簡単な問題からアルゴリズム問題に慣れていくことができます。
また、「アルゴリズムとは？」といったアルゴリズム入門から解説してくれているので、プログラミングをやったことない方にも親切な内容になっています。
アルゴリズム問題に全く手がつかないというような方は、まずは上記のような本でアルゴリズムに慣れるのがオススメです。
慣れてきたら、あとは実際の過去問を解いて "さらに考える力を養う" ＆ "実際のアルゴリズム問題に慣れる" のが良いと思います。
私のサイトでも過去問の解説をしていますので是非参考にしてください。私の解説だけでなく、他の人の解説も参考にしたいような場合には、下記のような過去問の参考書もオススメです（アルゴリズム問題だけでなく、全問題の解説も充実しています）。
