平成26年(H26)秋期 基本情報技術者試験 アルゴリズム問題 解き方解説

平成26年度秋期午後のアルゴリズム問題である問8の私の解き方・考え方について解説していきます。

問題

IPAの公式サイトで公開されています。このページでは問8についての解説を行います。

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2014h26_2/2014h26a_fe_pm_qs.pdf

問題の概要

2つの文字列の差異を測る指標である編集距離に関する問題です。

エディットグラフの生成方法と最短移動距離の求め方については設問を解いていく前に理解しておいたほうが良いとおもいます。

エディットグラフの生成方法

エディットグラフの生成方法については、特に(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, 2)までの最短移動距離D[2, 2]の求め方を見ていきましょう。

Str1[1]Str2[1]が同じ文字(両方とも”b”)のため、(1, 1)から(2, 2)には斜線が引かれています。

ですので(2, 2)に行くための経路と移動距離は下記の3通りになります。

(その座標よりも右上方向にある座標からの移動は必ず移動距離が大きくなってしまいますので候補から外す)

  1. (1, 2)から距離1で移動:D[1, 2] + 1
  2. (2, 1)から距離1で移動:D[2, 1] + 1
  3. (1, 1)から距離0で移動:D[1, 1]

この3つから一番移動距離が小さいものがD[2, 2]と考えられます。

もう一つの例として(3, 2)までの最短移動距離D[3, 2]の求め方を見ていきましょう。

Str1[2]Str2[1]が違う文字のため、(2, 1)から(3, 2)には斜線が引かれていません。

ですので(3, 2)に行くための経路と移動距離は下記の2通りになります。

  1. (2, 2)から距離1で移動:D[2, 2] + 1
  2. (3,  1)から距離1で移動:D[3, 1] + 1

この2つから一番移動距離が小さいものがD[3, 2]と考えられます。

つまり、D[X, Y]は、Str1[X-1]とStr2[Y-1]が同じである場合、下記の3つの中から最小となる値となり、

  • D[X – 1, Y – 1]
  • D[X – 1, Y] + 1
  • D[X, Y – 1] + 1

Str1[X-1]とStr2[Y-1]が違う場合、下記の2つの中から最小となる値となります。

  • D[X – 1, Y] + 1
  • D[X, Y – 1] + 1

この辺りを頭に置いて設問を考えていきましょう。

スポンサーリンク

設問1

[   a   ]と[   b   ]に関してはちょうど問題の概要で説明した内容になります。

D[X, Y]が、

  • D[X – 1, Y – 1]
  • D[X – 1, Y] + 1
  • D[X, Y – 1] + 1

の3つの中から最小となる値となるのは「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

設問2は実際にStr1を”peace”、Str2を”people”とした時のプログラムの実行結果が問われている問題です。

[   c   ]についてはエディットグラフの作成の仕方を理解した上で、Str1[X]Str2[Y]とで同じ文字となるXYを見つけ出し、それに対応する「座標(X, Y)から座標(X + 1, Y + 1)の斜線」が存在するグラフを選択肢ア〜オから選べば解けるはずです。

具体的にはStr1[X]Str2[Y]は下記のXYの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)への斜線があるのがおかしいですし、他にも不要な斜線がたくさんあります。

一方、オに関しては上で挙げた6つの座標全てから斜線が引かれていますのでオが正しいグラフと言えます。したがって[   c   ]の答えはオとなります。

続いて[   d   ]を解いていきましょう。αはStr1[X]Str2[Y]が同じ場合に実行されます。Str1[X]Str2[Y]が同じになるのは上で挙げた6パターンの場合のみですので、αは6回実行されることになります。したがって[   d   ]の答えは6です。

[   e   ]はβが実行される回数を答える問題です。βはStr1[X]Str2[Y]が異なる場合に実行されます。Str1の文字列長が5、Str2の文字列長が6であり、Str1[X]Str2[Y]が同じなのは6パターンですので、βは24回(5×6ー6)実行されることになります。したがって[   e   ]の答えは24です。

[   f   ]はStr1Str2の編集距離すなわち最短移動距離となります。プログラムを実際に動かした時にD[Str1Len, Str2Len]の値が何になるかを考えれば答えは導け出せます。またエディットグラフが分かっていますので、最短移動距離がいくらになるかをグラフから読み取ることも可能です。

例えば下記のピンク色の矢印で示す経路は最短移動距離となる経路になります(他の経路で最短移動距離となるものは他にもあります)。

斜線は移動距離が0ですので、最短移動距離は5となります。したがって[   f   ]の答えは5です。

解いてみた感想

編集距離という概念を初めて知ったのでいい勉強になった問題でした。

グラフを使って距離を求めるというプログラムになっていますので処理のイメージも湧きやすくて解きやすかったです。

★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください!

基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ

本ページの図・プログラム・問題文について

図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。

出典:平成26年度 秋期 基本情報技術者試験(FE)試験区分 午後 問8

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です