開明堂：読んだ：高橋謙一郎『悩めるプログラマに効くアルゴリズム』

高橋謙一郎
悩めるプログラマに効くアルゴリズム

問題の性質を読み解く
無駄な検索を切り詰めるために工夫する
プログラムの基本形を掴む

検索対象となる範囲を広げていく/詰めていく
既に調べたものを調べない

再帰では必ず終着点を用意する
問題を小さく分割し、それを再帰によって繰り返す -> 分割統治
仮定を追って駄目になったら元に戻ってやり直す -> バックトラッキング
バックトラッキングでの検索の打ち切り -> 枝狩り
局所的な解を足がかりにして別の場所を解いていく -> 制約伝播

枝狩りの条件を更に考える
バックトラックの中で枝狩りと制約伝播を使ってみる
選択肢の少ない方から処理を行う

再帰は最短解ではないかもしれない深さ優先検索
これに対し足元を全て調べてから次の深さを調べる -> 幅優先検索
この場合には検索結果を保存する大きな保存場所が必要

その大きなテーブルの照合にハッシュなどを利用する
ある局面をハッシュ値に変換する関数 -> ハッシュ関数
ハッシュ地が既に使われていた場合の再計算 -> 再ハッシュ
(再ハッシュの回数を減らすために保存場所は必要量の 2 割増しくらい確保する)

自分の結果表示の前に親局面を表示させるという再帰の使い方

保存場所が見積もれない場合のあふれのチェック
終了局面が複数ありえる場合のチェック (局面を登録するか条件チェックするか)
再ハッシュの回数を調べハッシュ関数を改良する

深さ優先検索で深さに制限をつけながら検索 -> 反復深化
(幅優先検索では格納場所のためのメモリなどを必要とするため)
(但し、逆に検索時間がかかる)

堂々巡りの場合の一手の手戻り(一手で親局面に戻る)の防止

反復深化での枝狩り法として下限値枝狩り法がある
最低限に必要な手数から下限値を得てそれ以上は調べない

ミニマックス法
A は A の最善手を探そうとする (MAX レベル)
B も B の最善手を探そうとする

全文検索

Translate into