狠狠撸

アルゴリズムのイメージを擬人化する
AtCoder株式会社代表取締役
高橋直大
2014/11/10
1

?AtCoder Inc. All rights reserved.
2
はじめに
2014/11/10

内容について
?初心者向きの内容になります。
–ガチ勢は聞いても勉強にならないかも
–可愛いキャラが後半に出てくるので、それ目当ても可
?一応教育コンテンツです
–擬人化をすることで良いこともあるんです。
?気になった点は即突っ込んでください。
–擬人化、一人でしてもつまらないので、属性追加とか大歓迎です
2014/11/10
3

4
アルゴリズムをなぜ擬人化するのか？
2014/11/10

なぜ擬人化？
?アルゴリズムが擬人化出来ない人は、そのアルゴリズムを理解しているとは言えない！
–アルゴリズムを十分に理解している人は、アルゴリズムの擬人化が上手
?もちろん、全員が全員擬人化しているわけではありません
–逆に、あまり理解していないアルゴリズムは、上手く擬人化できない
?知らないアルゴリズムは擬人化出来ない！
2014/11/10
5

擬人化をしよう！
?擬人化をするために必要なことは？
–アルゴリズムの特徴を、出来るだけ多く捉える！
?特徴が解らないと、安易な擬人化しか出来ません。
–アルゴリズムを、別の視点から見てみる！
?こういう入力の時はどう？
?ああいう入力の時はどう？
?そういった視点から、キャラクターの性格が形成されていく
?こうした複数の視点を積極的に探していくことで、アルゴリズムを深く理解し、問題を解く能力が向上する！
–競技プログラミングに直結するとは限りません
2014/11/10
6

7
ブルートフォース
2014/11/10

?総当たりアルゴリズム
–力づくで全部調べる
?全てを力で解決する
–蟻本さえも丸めて武器にしてしまう
?だが、完全な脳筋キャラなのだろうか？
2014/11/10
9

?ブルートフォースは劣ったアルゴリズム？
–そんなことはありません！
?計算量が問題ないのであれば、最もバグりにくく、コード量も短くて済むことが多い！
?力づくで解決できない問題ももちろんあるが、力づくで良いのであれば、それが最も楽
2014/11/10
10

?ブルートフォースは、「力づくで解決できる時にだけ出てくる仕事人！」
–蟻本も持ってるし、脳筋キャラでも勉強してる！
–自分の役立つポイントは、彼が一番理解しています。
?もしブルートフォースを組んでTLEしたら、ブルートフォースが悪いのではなく、悪いのはあなたです！
2014/11/10
11

ブルートフォースおまけ
?なんで女の子じゃないの？
–マッチョな女の子とか嬉しくないじゃん！！！！
?ほんとは男２女２にしてねって言われたからです。
?女の子としてイメージすると、また違ったキャラ付に出来るかもしれない！
–それはご来場の皆様にお任せします！
2014/11/10
12

13
深さ優先探索
2014/11/10

深さ優先探索
?深さ優先探索は勇者である
–色々なところに、主人公的な要素が存在する！！！
2014/11/10
15

深さ優先探索
?「解に辿り着いたとしても、その解が最短である保障がない点」
–とりあえず答えにはたどり着くけど、普段の仕事はいい加減
?これだけ見ると「決して優等生なキャラクターではない」という部分が強調される。
?ヒーローの日常は多少不真面目なくらいが良い！
2014/11/10
16

深さ優先探索
?「グラフが膨大でも、解に辿り着けることがある」
–真面目に最短路を探すようなアルゴリズムでは、とても解に辿り着けないような膨大なグラフでも、解に辿り着けることがある。
?例えば、6*6のスライドパズルの探索とか
–単純な実装では大抵上手くいかないけれども、ちょっとした工夫で一気に探索結果が変わるのも魅力的
2014/11/10
17

深さ優先探索
?「たまに空回りする」
–グラフの形によっては、同じところで無限ループを起こしてしまう
?ちょっとだめなところがあるのもポイント！
–大事な仲間（メモリーちゃん）に覚えてもらうことにより、空回りを起こさなくなる！
?いわゆるメモ化再帰
2014/11/10
18

深さ優先探索
?他にも色々な主人公要素が存在する
–初期パーティ
?アルゴリズムを学ぶ上で、「探索」は最初に身に着けるツールです。最初から出てくること程、主人公らしい要素はありません。
–目の前のことを無視できない。
?隣接ノードのうち最も評価が高いものから探索する、というのはよくおこなわれる手法であり、それをすることにより、遠くの良い解よりも、近くの解に近づき易くなります。
2014/11/10
19

深さ優先探索おまけ
?もし深さ優先探索が女の子だったら？
–ヤンデレっぽい子にした気がします
?一人の男性に嵌ると、そこで無限ループを起こして抜け出せない
–サークルクラッシャー的な子の可能性もあり
?親しくなった男性の友人と次々に親しくなっていく
?そういう目で見ると、探索系アルゴリズムは全部真人間ではなくなってしまうので、もうちょっと違った目線で見てあげたほうが良いと思います＞＜
–もちろん女勇者でも良い
2014/11/10
20

21
幅優先探索
2014/11/10

幅優先探索
?委員長タイプの女の子！
–真面目！かわいい！
2014/11/10
23

幅優先探索
?委員長タイプの女の子！
–全員に対して平等です。
?始点からの距離に対して近い順に探索します。
?偏ったりはしません。
–常にきっちりと仕事をこなします。
?出力される解は必ず最短であることが保障されている
2014/11/10
24

幅優先探索
?やることが増え過ぎちゃうと対応できない
–解までが遠いと、絶対に解に辿り着けない
?目回してあわあわってなりそうでかわいい
–あんまり工夫の余地がない
?探索順を弄っても、そんなに探索効率は変わらない
–凄く工夫するとダイクストラやA*になるが、これはもはや別物
–融通の利かない感じがかわいい
?深さ優先探索と大体正反対！
2014/11/10
25

26
ビームサーチ
2014/11/10

ビームサーチ
?「ビーム」の名が表す通り、魔法少女ちゃん！！
–杖からビームを打つよ！
2014/11/10
28

ビームサーチ
?「ビーム」の名が表す通り、魔法少女ちゃん！！
–杖からビームを打つよ！
????みたいな設定なわけがないです！！！
2014/11/10
29

ビームサーチ
?そもそもビームサーチってどういうアルゴリズム？
–良い状態を上位K個まで保持する
?貪欲法だと、「最も良いものを選ぶ」
?ビームサーチは、「上からK個を残す」
–何が嬉しいの？
?貪欲法だと上手くいかない問題はたくさんある
?でも、貪欲法だと「ある程度上手くいく」問題もたくさんある
?だったら、貪欲法で候補になるのをたくさん持っておけば、もっと上手くいきやすいよね！って発想
2014/11/10
30

ビームサーチ
?ビームサーチって地味じゃない？
–「ビーム」は、探索のループ毎に、「常にK個のノードを探索する」→「幅が一定」だからビームって呼ばれてるだけ
?それなのに、「ビームサーチ」とかかっこいい名前がついてる
こんなかっこいい
ビームは打てない！
2014/11/10
31

ビームサーチ
?結論：ビームサーチはコスプレ少女である
–ビームなんて打てない！魔法も使えない！
–コスプレしているだけ！
2014/11/10
32

ビームサーチ
?では、ビームサーチちゃんは本当はどんな子なのか？
–ビームサーチちゃんは、地方から出てきて都会に出てきた、一人暮らしの大学1年生である！
?書いて貰った段階では高校生だったんだけど、なんとなく大学１年生にしました
2014/11/10
33

ビームサーチ
?一人暮らしの貧乏な女の子
–狭い部屋に一人で住んでる
–お金がないので、コスプレ衣装を自分で作っている
?前に作ったコスプレ衣装を参考に、改良したものを新たに作る
–狭い部屋に住んでいるので、ものがあまり置けない
?お気に入りの上位K着だけを残して、残りは捨ててしまう
?地味なのに頑張ってるのが可愛い！
?幸薄っぽいのが可愛い！！！
2014/11/10
34

35
最後に
2014/11/10

今回のまとめ
?ブルートフォースくん
–力づくで押し切るのが得意です。使い方は考えましょう
?深さ優先探索くん
–とりあえずチューニングすればなんとかしてくれます。最適解とかを出したい時は無理だけど
?幅優先探索ちゃん
–きっちりしてるけど、探索空間が膨大な時に注意しよう
?ビームサーチちゃん
–かわいい！地味かわいい！
–意外と単純、簡単なアルゴリズムです！こわくないよ！
?魔法使いだって考えると怖いけど、所詮コスプレ少女だよ！
2014/11/10
36

さいごに
?今回の擬人化の説明は、「イラストにあった特徴」だけを取り出しています。
–よって、アルゴリズムの全ての特徴が生かせているわけではない
?例えば、深さ優先探索は、「辞書順最小」とかは見つけられる
?一人が擬人化するだけでは、全ての特徴を列挙出来ない
–一部の特徴は、擬人化することでむしろ見えなくなってしまう
?これを解決するには、みんなでそれぞれアルゴリズムを擬人化し、共有すれば良い！
2014/11/10
37

狠狠撸

アルゴリズムのイメージを拟人化する

More Related Content

アルゴリズムのイメージを拟人化する