雑読「問題解決力を鍛える！アルゴリズムとデータ構造」：1章 アルゴリズムとは
1章 アルゴリズムとは
1.1 アルゴリズムとは何か
問題を解くための手順のこと
年齢当てゲームの例
n個の候補があったとき、前からやるとn回の質問が必要（線形探索法）
二分探索なら圧倒的に早い
m回の質問で候補を\frac{1}{2}^mに絞り込める
Akinatorも何らかの方法で二分探索してるのかな
明らかに年齢ほど単純ではない
そもそも質問に対して2〜4通りの答えがあるのでは？いわば2〜4分探索
単なるツリーの探索なので普通はそういう呼び方はしない
4択ぐらいあるから2分ではありませんでした...
1.2 アルゴリズムの例(1)：深さ優先探索と幅優先探索
探索はあらゆるアルゴリズムの基礎
虫食い算の例
>基本的には力任せの探索アルゴリズムですが，探索順序を工夫することで劇的な性能差が出ることが魅力的です．(p.31). Kindle 版.
探索順序を工夫することで劇的な性能差が出るここがまだわからない
大前提として「最初に見つかった一つを返せばいい」という問題設定なのだと思う、ならば早く見つかる方法で探すと良い
色々応用がある
トポロジカルソート（13章）
動的計画法（5章）
ネットワークフローアルゴリズムのサブルーチン（16章）
など
グラフ上の探索と捉えると見通しが良くなる（13章でやる）
迷路のスタートからゴールまでの最短距離を計算する例
最小手順を知りたいときに便利
こっちもグラフ上の探索と捉えると見通しが良くなる（13章でやる）
最終的にグラフ上の探索としてもう一回捉え直されるけどそっちの方がむずいからまずは簡単で愚直なやり方からやるのかな
うーん、見通しが良くなるかどうかは主観だからな…
1.3 アルゴリズムの例(2)：マッチング
男女のマッチングの例
ペアになってもいいという男女の間に線が引かれている
婚活パーティー（？）とかでスコアづけをこの線と捉えても良さそう
スコアを最大化する問題の「スコアに0と1しかない特殊ケース」と捉えることはできる
問. カップル数を最大化するにはどういうペアを作ればいいでしょうか
応用例
ネット広告
レコメンド
スケジュール調整
16章でやる
1.4 アルゴリズムの記述方法
擬似コードではなくC++で書く
1.5 アルゴリズムを学ぶ意義
問題に対する解を書き下せなくても手順を与えられ得れば良い
解析解がない問題多いからなあ
章末問題
これはちゃんとやっていきたい
1.1
20歳から36未満の年齢を2分探索で当てる流れ
候補である20-35の中間地点を聞きたいので「28歳未満ですか？」と聞く
回答された部分を同様に半分にしていく
YESなら20-27の中間24未満か聞く...
1.2 0以上100未満の年齢をY/N Questionを繰り返す
6回で確実に当てられるか
No。2^6=64以下でないと6回では確実には当てられない
7回で確実に当てられるか？
Yes
1.3 虫食い算をやれ
めんどくさい
1.4 虫食い算をやれ 2
すごくめんどくさい
1.5
最大の数値の隣接領域から1ずつ引いたマスに進行していきスタート地点にたどり着いた時の経路
1.6
asearchはScrapboxの検索バーで使われている