文字列探索 A B C D X Y E F X Y Z G H I J R [ ] S [ ] 1 2 3 4 5 6 7 8 9 10 11 12 … M 配列の サイズ M N X Y Z X Y Z i = 1 比較開始位置 i = M – N + 1 X Y Z 検索文字列 S を、 文字列 R から検索 i > ( M – N + 1) 処理 ※ テキストでは、 終了条件を記載 for ( i = 1 ; i ≦ M – N + 1 ; ++ i ) { } 処理 4
5 文字列探索 A B C D X Y E F X Y Z G H I J R [ ] S [ ] 配列の サイズ M N X Y Z j = 1 … N 比較位置 検索文字列 S を、 文字列 R から検索 for ( i = 1 ; i ≦ M – N + 1 ; ++ i ) { } 処理 for ( j = 1 ; j ≦ N ; ++ j ) { if ( R[ i + j – 1 ] ≠ S[ j ] ) { break ; } } if ( j > N ) { P ← i ; break ; } // 見つけた i
6
参考： 文字列検索アルゴリズム 力まかせ法 (p. 4, 5 の方法) O( n m ) KMP 法 (Knuth-Morris-Pratt) O( n + m ) BM 法 (Boyer-Moore) O( n + m ) n ： テキストの長さ m ： 検索文字列の長さ ( p. 4, 5 では M ) ( 〃 N )
空白除去 7 A B C D E F X Y Z R [ ] 1 2 3 4 5 6 7 8 9 10 11 12 … N 配列の サイズ N N A B C D E F X Y Z S [ ] i j j = 1 for ( i = 1 ; i ≦ N ; ++ i ) { } if ( R[ i ] ≠ “空白” ) { S[ j ] = R[ i ] ; // S[ ] にコピー ++ j ; } ※ テキストより簡単
文字列挿入 8 A B C D E F G H R [ ] 1 2 3 4 P … M A B C D E F G H R [ ] 挿入後 1 … N 文字列 R の P の位置に、 文字列 S を挿入 R [ ] の P 以降を ずらす S [ ] を 挿入 S [ ] for ( i = M ; i ≧ P ; -- i ) { } R [ i + N ] = R [ i ] ; // 後ろからずらす for ( j = 1 ; j ≦ N ; ++ j ) { } R [ P + j - 1 ] = S [ j ] ; X Y Z
9
文字列処理 (その他) 文字列連結 R [ ]， S [ ] の順に、文字列を T [ ] にコピー 文字列置換 R [ P ]，R [ P + 1 ]，… に、 文字列 S [ ] をコピー R [ ] S [ ] T [ ] R [ ] S [ ]
最短経路問題
10 応用： 列車の乗り換え検索 カーナビのルート検索
11
最短経路問題 (入力) 有向グラフ G = ( V, E )， 辺の距離 c ： E → N 始点 s， 終点 t 1 2 3 4 5 30 20 70 30 90 50 120 始点 1， 終点 5
Dijkstra のアルゴリズム (初期化) s から節点 v への距離 D [ s ] ← 0 D [ v ] ← ∞ (s 以外の節点) 1 2 3 4 5 30 20 70 30 90 50 120 始点 1， 終点 5 ∞ ∞ ∞ ∞ 0
14
u ← 未確定の節点で、s からの距離が最小の もの (s からの距離 D [ u ] が確定) 1 2 3 4 5 30 20 70 30 90 50 120 始点 1， 終点 5 ∞ ∞ ∞ Dijkstra のアルゴリズム ∞ 0 ※ 最初は、全節点が未確定
15
u に隣接するすべての節点 v に対し、D [ v ]を更新 D [ v ] ← min { D [ v ]， D [ u ] + c ( ( u, v ) ) } 1 2 3 4 5 30 20 70 30 90 50 120 始点 1， 終点 5 ∞ ∞ ∞ s … → u → v Dijkstra のアルゴリズム 0 ∞ 20 30 120
16
(初期化) s から節点 v への距離 D [ s ] ← 0 D [ v ] ← ∞ (s 以外の節点) u ← 未確定の節点で、s からの距離が最小の もの (s からの距離 D [ u ] が確定) u に隣接するすべての節点 v に対し、D [ v ]を更新 D [ v ] ← min { D [ v ]， D [ u ] + c ( ( u, v ) ) } すべての節点が確定するまで、 2，3 を繰り返す Dijkstra のアルゴリズム (まとめ) 他の初期化方法もある 更新時に、u を覚えると、最短経路を求められる
u ← 未確定の節点で、s からの距離が最小の もの (s からの距離 D [ u ] が確定) Dijkstra のアルゴリズム 1 2 3 4 5 30 20 70 30 90 50 120 始点 1， 終点 5 ∞ ∞ ∞ 0 ∞ 20 30 120
19
u に隣接するすべての節点 v に対し、D [ v ]を更新 D [ v ] ← min { D [ v ]， D [ u ] + c ( ( u, v ) ) } Dijkstra のアルゴリズム 1 2 3 4 5 30 20 70 30 90 50 120 始点 1， 終点 5 ∞ ∞ ∞ 0 ∞ 20 30 120 70 110
20
u ← 未確定の節点で、s からの距離が最小の もの (s からの距離 D [ u ] が確定) Dijkstra のアルゴリズム 1 2 3 4 5 30 20 70 30 90 50 120 始点 1， 終点 5 ∞ ∞ ∞ 0 ∞ 20 30 120 70 110
Comments