基本情報技術概論 I 演習 (第６回)
アルゴリズム と データ構造
埼玉大学 理工学研究科
堀山 貴史
1
午後の問題への対応
長文にメゲない
読み飛ばしは、思いこみ違いの原因
色々なアルゴリズムを知っておく
暗記ではなく、アイデアを把握
アイデアを実現する手順を考える
2
文字列処理
暗記ではなく、考え方の練習
3
検索文字列 S を、
文字列探索 文字列 R から検索
1 2 3 4 5 6 7 8 9 10 11 12 …
M
配列の
サイズ
R[ ] A B C D X Y E F X Y Z G H I J
M
S[ ] X Y Z
N
X Y Z
i=1
i=M–N+1
比較開始位置
for ( i = 1 ; i ≦ M – N + 1 ; ++ i ) {
※ テキストでは、
終了条件を記載
処理
}
i > ( M – N + 1)
処理
4
文字列探索
検索文字列 S を、
文字列 R から検索
配列の
サイズ
i
R[ ] A B C D X Y E F X Y Z G H I J
X Y Z
S[ ]
M
N
j = 1 … N
比較位置
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 ; }
// 見つけた
5
参考：
力まかせ法 (p. 4, 5 の方法)
O( n m )
KMP 法 (Knuth-Morris-Pratt)
文字列検索アルゴリズム
O( n + m )
BM 法 (Boyer-Moore)
O( n + m )
n ： テキストの長さ
( p. 4, 5 では M )
m ： 検索文字列の長さ
(
〃
N)
6
空白除去
1i 2 3 4 5 6 7 8 9 10 11 12
R[ ]
A B C D E F
…
N
X Y Z
S[ ] A B C D E F X Y Z
配列の
サイズ
N
N
j
j=1
for ( i = 1 ; i ≦ N ; ++ i ) {
}
if ( R[ i ] ≠ “空白” ) {
S[ j ] = R[ i ] ; // S[ ] にコピー
++ j ;
}
※ テキストより簡単 7
文字列 R の P の位置に、
文字列挿入 文字列 S を挿入
1 2 3 4 P … M
R[ ] A B C D E F G H
R[ ]
挿入後 A B C D
S[ ]
E F G H
X Y Z
(1) R [ ] の P 以降を ずらす
1 … N
(2) S [ ] を 挿入
for ( i = M ; i ≧ P ; -- i ) {
R [ i + N ] = R [ i ] ; // 後ろからずらす
}
for ( j = 1 ; j ≦ N ; ++ j ) {
R[P+j-1]=S[j];
}
8
文字列処理 (その他)
文字列連結
R [ ]， S [ ] の順に、文字列を T [ ] にコピー
R[ ]
T[ ]
S[ ]
文字列置換
R [ P ]，R [ P + 1 ]，… に、
文字列 S [ ] をコピー
S[ ]
R[ ]
9
最短経路問題
応用： 列車の乗り換え検索
カーナビのルート検索
10
最短経路問題 (入力)
有向グラフ G = ( V, E )， 辺の距離 c ： E → N
始点 s， 終点 t
1
30
2
70
3
120
20
30
50
4
90
始点 1， 終点 5
5
11
ダイクストラ
Dijkstra のアルゴリズム (アイデア)
節点 v への最短経路
ｓ
u
ｖ
この部分は、節点 u への最短経路になっている
つまり、近い側の最短経路が分かれば、
遠い側の最短経路も分かるようになる
12
ダイクストラ
Dijkstra のアルゴリズム (アイデア)
s に近い順に、節点への距離を確定させていく
1
30
2
70
3
120
20
30
50
4
90
始点 1， 終点 5
5
13
Dijkstra のアルゴリズム
1. (初期化) s から節点 v への距離
D[ s ] ← 0
D [ v ] ← ∞ (s 以外の節点)
0
1
∞
30
2
70
∞
3
120
20
30
50
4
∞
90
始点 1， 終点 5
5
∞
14
Dijkstra のアルゴリズム
2. u ← 未確定の節点で、s からの距離が最小の もの
(s からの距離 D [ u ] が確定)
※ 最初は、全節点が未確定
0
1
∞
30
2
70
∞
3
120
20
30
50
4
∞
90
始点 1， 終点 5
5
∞
15
Dijkstra のアルゴリズム
3. u に隣接するすべての節点 v に対し、D [ v ]を更新
D [ v ] ← min { D [ v ]， D [ u ] + c ( ( u, v ) ) }
s…→u→v
0
1
30
30 ∞
2
70
∞
3
120
20
30
50
4
20 ∞
90
始点 1， 終点 5
5
∞ 120
16
Dijkstra のアルゴリズム (まとめ)
1. (初期化) s から節点 v への距離
D[ s ] ← 0
D [ v ] ← ∞ (s 以外の節点)
他の初期化
方法もある
2. u ← 未確定の節点で、s からの距離が最小の もの
(s からの距離 D [ u ] が確定)
3. u に隣接するすべての節点 v に対し、D [ v ]を更新
D [ v ] ← min { D [ v ]， D [ u ] + c ( ( u, v ) ) }
更新時に、u を覚えると、最短経路を求められる
4. すべての節点が確定するまで、 2，3 を繰り返す
17
Dijkstra のアルゴリズム
続きを、自分でやってみてください
0
1
30
30 ∞
2
70
∞
3
120
20
30
50
4
20 ∞
90
始点 1， 終点 5
5
∞ 120
18
Dijkstra のアルゴリズム
2. u ← 未確定の節点で、s からの距離が最小の もの
(s からの距離 D [ u ] が確定)
0
1
30
30 ∞
2
70
∞
3
120
20
30
50
4
20 ∞
90
始点 1， 終点 5
5
∞ 120
19
Dijkstra のアルゴリズム
3. u に隣接するすべての節点 v に対し、D [ v ]を更新
D [ v ] ← min { D [ v ]， D [ u ] + c ( ( u, v ) ) }
0
1
30
30 ∞
2
70
∞ 70
3
120
20
30
50
4
20 ∞
90
始点 1， 終点 5
5
∞ 120 110
20
Dijkstra のアルゴリズム
2. u ← 未確定の節点で、s からの距離が最小の もの
(s からの距離 D [ u ] が確定)
0
1
30
30 ∞
2
70
∞ 70
3
120
20
30
50
4
20 ∞
90
始点 1， 終点 5
5
∞ 120 110
21
Dijkstra のアルゴリズム
3. u に隣接するすべての節点 v に対し、D [ v ]を更新
D [ v ] ← min { D [ v ]， D [ u ] + c ( ( u, v ) ) }
0
1
30
30 ∞
2
70
∞ 70
3
120
20
30
50
4
20 ∞
90
始点 1， 終点 5
5
∞ 120 110
22
Dijkstra のアルゴリズム
2. u ← 未確定の節点で、s からの距離が最小の もの
(s からの距離 D [ u ] が確定)
0
1
30
30 ∞
2
70
∞ 70
3
120
20
30
50
4
20 ∞
90
始点 1， 終点 5
5
∞ 120 110
23
Dijkstra のアルゴリズム
3. u に隣接するすべての節点 v に対し、D [ v ]を更新
D [ v ] ← min { D [ v ]， D [ u ] + c ( ( u, v ) ) }
0
1
30
30 ∞
2
70
∞ 70
3
120
20
30
50
4
20 ∞
90
始点 1， 終点 5
5
∞ 120 110 100
24
Dijkstra のアルゴリズム
2. u ← 未確定の節点で、s からの距離が最小の もの
(s からの距離 D [ u ] が確定)
0
1
30
30 ∞
2
70
∞ 70
3
120
20
30
50
4
20 ∞
90
始点 1， 終点 5
5
∞ 120 110 100
25
Dijkstra のアルゴリズム
3. u に隣接するすべての節点 v に対し、D [ v ]を更新
D [ v ] ← min { D [ v ]， D [ u ] + c ( ( u, v ) ) }
0
1
30
30 ∞
2
70
∞ 70
3
120
20
30
50
4
20 ∞
90
始点 1， 終点 5
5
∞ 120 110 100
26
27
28
この教材のご利用について
この文面は、TOKYO
TECH OCW の利用
条件を参考にしました
この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を
求めることなく、無償で自由にご利用いただけます。講義、自主学習は
もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。
非商業利用に限定
この教材は、翻訳や改変等を加えたものも含めて、著作権者の許
諾を受けずに商業目的で利用することは、許可されていません。
著作権の帰属
この教材および教材中の図の著作権は、次ページ以降に示す著
作者に帰属します。この教材、または翻訳や改変等を加えたもの
を公開される場合には、「本教材 (or 本資料) は
http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です
(or 教材を改変したものです」 との旨の著作権表示を明確に実施
してください。なお、この教材に改変等を加えたものの著作権は、
次ページ以降に示す著作者および改変等を加えた方に帰属しま
す。
同一条件での頒布・再頒布
この教材、または翻訳や改変等を加えたものを頒布・再頒布する
場合には、頒布・再頒布の形態を問わず、このページの利用条件29
この教材のご利用について
配布場所
http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/
この powerpoint ファイルの著作者
堀山 貴史 2007-2011 [email protected]
改変等を加えられた場合は、お名前等を追加してください
図の著作者
p. 4 ～ 26
堀山 貴史
30
© Copyright 2024 ExpyDoc
