参考文献:http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm 少し分かりづらいように思ったので、補足エントリ的な。 *** 問題 ある文章Aに対して削除・挿入・編集を行い文章Bを作成する。そのときのAとBの差分を求めよ。(DIFF) 解法のアウトライン DIFFは最小エディット問題に還元する事で解く事ができる。 最小エディット問題とは、文章Aを編集(挿入・削除・編集)する事によって文章Bにするときに、その最小の編集を求めよという問題。 例 あいうえお→あえいうえおあお (太字→挿入/アンダーライン→削除の意) あえいうえおあお(最小) あいうえおあえいうえおあお(最小でない) 解法 エディットグラフを作成 文章AをA1A2A3...AMとする 文章BをB1B2B3...BNとする (0,0) ~ (M,N)の大きさの方眼グラフを用意する 全てのAx = Byに対して(x-1,y-1)→(x,y)に斜め線を引く グラフに重みを与えます。 横線縦線の重みは各々1です。 斜め線の重みは0です。 (0,0)→(M,N)に一番軽く到達できるルートが最小エディットと一致します。 実例です。 アルゴリズム その1 (0,0)から順に重みを求めていきます。 点(x,y)へは点(x-1,y-1), (x-1,y),(x,y-1)から到達可能なので適当に斜めに、下のような感じで順番に求めていきましょう。 Cost(0,0) = 0 Cost(1,0) = 1Cost(0,1) = 1 Cost(2,0) = 2 Cost(1,1) = 1 Cost(0,2) = 2 ... Cost(1,1) = min(Cost(0,0)+0, Cost(0,1)+1, Cost(1,0)+1) みたいな感じですね。 その2 「基本的な考え方」 Cost0で到達可能範囲を求める→Cost1で→Cost2で・・・という風に順番にゴールにたどり着くまで繰り返す方法です。Cost0 = ((0,0))Cost1 = ((1,0), (0,1), (1,1))...その1より若干早いですね。 O(ND)のGreedyアルゴリズム やり方を説明します。 エディットグラフに対角線を2k[=2*max(M,N)]+1本ほど引きます。 それぞれの対角線の名前を-k~kとします。 k=x-yです。参考文献とx軸y軸方向が違うので注意してください。 今後は、この対角線ベースで色々考えます。 V[k,D] = D回の操作で到達可能な最深のy座標と定義します。 V[k,0], V[k,1]を順々に求めていき
となったときにその経路=最短となります。 このアルゴリズムでは、このV[k,D]の値はV[k-1, D-1], V[k+1,D-1]から求められます。 つまり、対角線k上においてCostDでたどり着ける点は、お隣の対角線k-1,k+1にCost(D-1)でたどり着いた点からCost1でやってくる所に限られるという事です。 少し詳しく説明すると、対角線k, コストDにおける最深点は対角線k-1,コストD-1の最深点から横方向に1動いた後に斜め移動をできるだけ繰り返した場所もしくは対角線k+1,コストD-1の最深点から下方向に移動し、そのいちからできるだけ斜めに移動した点、のどちらかになります。 この特徴を利用して以下のように組み立てます。 端っこの処理とか、Vの宣言とか省略してるので適当に。 for D in range(0,M+N): for k in range (-D, D): V[k,D] = calc_depth(V[k-1,D-1], V[k+1,D-1]) if V[k,D] == N and N+k==M: return ソースは参考文献のものが分かりやすいです。 探索例) その4
O(NP)は最遠点を優先的に探索するという事ですね。 読んでません(笑) Start blogging by creating a new post. You can edit or delete me by clicking under the comments. You can also customize your sidebar by dragging in elements from the top bar.
|