アルゴリズムって何だろう？ - 上智大学 情報理工学部 情報理工学科

アルゴリズムって何だろう？
（2009年11月14日版）
上智大学 理工学部 情報理工学科
宮本 裕一郎
アルゴリズムって何だろう？
アルゴリズム【algorithm; algorism】
（アラビアの数学者アル＝フワリズミーの名に因む）
①アラビア記数法
②問題を解決する定型的な手法・技法．
コンピューターなどで，演算手続きを指示する規則．
算法．
「広辞苑（第六版）」より
問題とアルゴリズムの例
★有名でない話
☆リーグ戦（総当り戦）スケジュール表の作成
☆（DVD）レンタル問題
☆とらわれの１０人と悪魔のゲーム
☆安定結婚問題とその解法
★有名な話
☆最大公約数とユークリッドの互除法
☆偽金貨を天秤で見つける方法
☆嘘つき族と正直族の島
☆並べ替え（sorting）
リーグ戦スケジュール表の作成
リーグ戦スケジュール表の作成
1
チーム
A
B
C
D
E
F
G
H
I
J
2
3
日
4 5
6
7
8
9
A～Jの
10チームが
総当りで対戦
各チームは
1日に1試合
9日で
全試合が
完了する
スケジュール表を
作成せよ
作成途中のリーグ戦スケジュール表
チーム
A
B
C
D
E
F
G
H
I
J
1
B
A
D
C
F
E
H
G
J
I
2
D
C
B
A
H
I
J
E
F
G
3
F
E
J
G
B
A
D
I
H
C
日
4 5
H J
G I
F H
I E
J D
C G
B F
A C
D B
E A
6
7
8
9
６チームリーグ戦スケジュール表の作成
チーム
日
1 2 3 4
A B D
B A C
C D B
D C A
E F
F E
5
このままでは
2日目のチームEとFの
対戦相手がいない！
「てきとうに作ればうまくいく」
というわけではないらしい
リーグ戦スケジュール表作成法：Circle Method
A
B
B E
F
C
A
E
F
C
B
D C
C
D
1
2
3
4
5
A
F
C
E
B
D
B
E
F
D
A
C
C
D
A
F
E
B
D
C
E
B
F
A
E
B
D
A
C
F
F
A
B
C
D
E
D
since 1847
D
A
F
E
E
B
F
A
E
D
A
C
F
B
作成途中のリーグ戦スケジュール表再び
チーム
A
B
C
D
E
F
G
H
I
J
1
B
A
D
C
F
E
H
G
J
I
2
D
C
B
A
H
I
J
E
F
G
3
F
E
J
G
B
A
D
I
H
C
日
4 5
H J
G I
F H
I E
J D
C G
B F
A C
D B
E A
6
7
8
9
この表の続きを埋めても
表の完成は不可能
不可能性の確認
→グラフ理論の利用
出典：
宮代隆平，総当りリーグ戦とグラフ理論，
オペレーションズ・リサーチ，52 (2007)，547-550
ちょっとだけグラフ理論紹介
Planarity.net
http://www.planarity.net/
TSP Games
http://www.tsp.gatech.edu/games/
アルゴリズムと公式
リーグ戦スケジュール表の作成アルゴリズム
→ Circle Method
三角形の面積＝底辺の長さ×高さ÷2
これはアルゴリズム？
アルゴリズムの厳密な定義はないが
極端に短いものはアルゴリズムと呼ばないみたい
「必ず止まる」という条件がつくことが多い
DVDレンタル問題
（DVD）レンタル問題
嫁がDVD化されている名作映画を見たいと言い出した．
DVDレンタル１回： ３５０円
DVD購入：
３５００円
嫁は気まぐれなので，
この先何回「見たい」と言うかわからない．
レンタルするべきか？購入するべきか？
レンタル作戦：毎回レンタル
購入作戦：初回に購入
中間作戦：９回目まではレンタル，１０回目に購入
作戦の評価基準：
作戦の支出は完璧な支出と比べて
最悪の場合，何倍くらい悪くなりそう？
レンタル作戦と購入作戦の考察
レンタル作戦の最悪の場合
嫁がDVD化されている名作映画を見たいと言い出した．
嫁が1000回「見たい」と言う
DVDレンタル１回： 350円
＝
1[ゴールド]
自分の支出＝1000
DVD購入：
3500円
＝
10[ゴールド]
完璧な支出＝10
嫁は気まぐれなので，
自分は完璧に比べて100倍悪い可能性あり
この先何回「見たい」と言うかわからない．
レンタルするべきか？購入するべきか？
レンタル作戦：毎回レンタル
購入作戦：初回に購入
中間作戦：９回目まではレンタル，１０回目に購入
購入作戦の最悪の場合
嫁が1回だけ「見たい」と言う
作戦の評価基準：
自分の支出＝10
作戦の支出は完璧な支出と比べて
完璧な支出＝1
最悪の場合，何倍くらい悪くなりそう？
自分は完璧に比べて10倍悪い可能性あり
中間作戦の考察
回数 1
自分 1
完璧 1
2
2
2
3
3
3
4
4
4
5
5
5
6
6
6
7
7
7
8
8
8
9
9
9
10 11 12 13 14 15
19 19 19 19 19 19
10 10 10 10 10 10
レンタル作戦：毎回レンタル
→ 完璧の100倍悪い可能性あり
購入作戦：初回に購入
→ 完璧の10倍悪い可能性あり
中間作戦：９回目まではレンタル，１０回目に購入
→ 完璧の1.9倍悪い可能性あり
実は，中間作戦があらゆる作戦の中で最良の作戦
→最悪の敵（嫁）を想定
オンラインアルゴリズム
この先何が起こるかわからないけれど，
わからないなりにがんばるアルゴリズム
応用：コンピューター内部のキャッシュとか
キーワード：スキーレンタル問題，
オンラインアルゴリズム，
競合比
出典：失念（ただし有名）
キーワードで検索すればいろいろ見つかる
囚われの10人と悪魔のゲーム
とらわれの１０人と悪魔のゲーム
解放を賭けて１年に１回悪魔とゲーム
悪魔は囚人番号（1～10）が書かれたカードを裏にして横一列に配置
1 裏
2 裏
3 裏
4 裏
5 裏
6 裏
7 裏
8 裏
9 10
裏
裏
とらわれの１０人と悪魔のゲーム
解放を賭けて１年に１回悪魔とゲーム
悪魔は囚人番号（1～10）が書かれたカードを裏にして横一列に配置
3 裏
7 裏
2 裏
1 裏
5 裏
9 裏
4 裏 10
6
裏
裏 裏
各人と悪魔が以下を1対1で行う：
囚人は高々5枚のカードを選んで表にする
表にしたカードにその囚人の番号があれば囚人の勝ち
そうでなければ悪魔の勝ち
最後に悪魔はすべてのカードを裏にする
人間が全員勝ったら全員解放
人間が１人でも負ければ全員とらわれたまま
悪魔はゲーム中にカードの配置を変えない（裏にするだけ）
ゲームが始まったら人間同士は意思疎通できない
人間はカードに細工などできない
悪魔のゲームとてきと～なアルゴリズム
解放を賭けて１年に１回悪魔とゲーム
悪魔は囚人番号（1～10）が書かれたカードを裏にして横一列に配置
てきと～なアルゴリズム：
各人がランダムにカードを選択
3 裏
7 裏
2 裏
1 裏 裏 裏 裏 10
裏
裏 裏
1人目が悪魔に勝つ確率＝1/2
各人と悪魔が以下を1対1で行う：
囚人は高々5枚のカードを選んで表にする
2人目までが悪魔に勝つ確率＝1/2x1/2＝1/4
表にしたカードにその囚人の番号があれば囚人の勝ち
そうでなければ悪魔の勝ち
最後に悪魔はすべてのカードを裏にする
10人目までが悪魔に勝つ確率
人間が全員勝ったら全員解放
＝1/2x1/2x1/2x1/2x1/2x1/2x1/2x1/2x1/2x1/2
人間が１人でも負ければ全員とらわれたまま
＝1/1024 < 0.1%
悪魔はゲーム中にカードの配置を変えない（裏にするだけ）
ゲームが始まったら人間同士は意思疎通できない
人間はカードに細工などできない
悪魔のゲームと工夫したアルゴリズム
解放を賭けて１年に１回悪魔とゲーム
悪魔は囚人番号（1～10）が書かれたカードを裏にして横一列に配置
3 裏
7 裏
2 裏
1 裏
5 裏
9 裏
4 裏 10
6
裏
裏 裏
各人と悪魔が以下を1対1で行う：
工夫したアルゴリズム：
以下のステップ1～3を，
囚人は高々5枚のカードを選んで表にする
表が5枚になるまで，あるいは
表にしたカードにその囚人の番号があれば囚人の勝ち
自分の番号が出るまで繰り返す
そうでなければ悪魔の勝ち
ステップ1：囚人番号xの人間は左からx番目を表にする
最後に悪魔はすべてのカードを裏にする
ステップ2：最後に表にしたカードの番号をyとする
人間が全員勝ったら全員解放
ステップ3：左からy番目のカードを表にする，ステップ2へ
人間が１人でも負ければ全員とらわれたまま
悪魔はゲーム中にカードの配置を変えない（裏にするだけ）
ゲームが始まったら人間同士は意思疎通できない
人間はカードに細工などできない
工夫したアルゴリズムが意味するもの
3 裏
7 裏
2 裏
1 裏
5 裏
9 裏
4 8 10
6
裏
裏 裏
サイクルはカードの配置で決まる
サイクルの長さが5以下ならば絶対に人間が勝つ
7
工夫したアルゴリズム：
以下のステップ1～3を，
8
2
4 表が5枚になるまで，あるいは
6
自分の番号が出るまで繰り返す
ステップ1：囚人番号xの人間は左からx番目を表にする
5
ステップ2：最後に表にしたカードの番号をyとする
1
3
9
10
ステップ3：左からy番目のカードを表にする，ステップ2へ
人間が負けるカード配置
3 裏
7 裏
2 裏
1 4 裏
9 5 8 10
6
裏
裏 裏
5
4
7
サイクルはカードの配置で決まる
6
サイクルの長さが6以上ならば絶対に悪魔が勝つ
2
1
3
8
9
10
人間が解放される確率
悪魔が勝つ確率
＝長さ6以上のサイクルができる確率
1 10
=
∑
10 C k ⋅ (k − 1)!⋅(10 − k )!
10! k =6
3 裏
7 裏
2 裏
1 4 裏
9 5 8 10
6
裏
裏 裏
10
1
10!
=∑ ⋅
⋅ (k − 1)!⋅(10 − k )!
k = 6 10! (10 − k )!⋅k!
10
1
=∑
k =6 k
5
7
1
1 1
= +  + + = 0.645...
6
9 10
4
8
2
人間が解放される確率
＝長さ6以上のサイクルができない確率
9
1＝1－0.654…
3 ＝ 0.34… ＞1/3
6
10
てきと～なアルゴリズムとの比較
てきと～な
アルゴリズム
0.3
確 0.2
率 0.1
0
工夫した
アルゴリズム
0.4
0.3
確 0.2
率
0.1
0
全員勝たなければ
意味がない
9人以下が勝つ確率は
低くてよい
0 1 2 3 4 5 6 7 8 9 10
勝つ人間の数
工夫の鍵：
でも，
悪魔がカードを
意地悪に並べ続けたら
どうする？
0 1 2 3 4 5 6 7 8 9 10Reference： “Names in boxes” in
資料協力：齊藤廣大さん
勝つ人間の数
Seven puzzles you think you must not have heard correctly,
by Peter Winkler.
http://math.dartmouth.edu/~pw/solutions.pdf
楽しんでいただけましたでしょうか？
アルゴリズムとは？ → 問題の解法
いろいろな問題に対するいろいろなアルゴリズムがある
パズルを解くようなおもしろさもアルゴリズム設計の醍醐味
論理的思考，数理的基礎知識がそれなりに必要
高校生でも読める推薦図書：
最短経路の本，R. ブランデンベルク (著), P. グリッツマン (著), 石田 基広 (翻訳) ，
シュプリンガー・ジャパン，2007年．
組合せ最適化「短編集」，久保 幹雄 (著), 松井 知己 (著)，朝倉書店，1999年．