開明堂 : kaimeido : 悩めるプログラマに効くアルゴリズム

悩めるプログラマに効くアルゴリズム

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

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

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

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

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

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

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

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

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

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

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

ミニマックス法
A は A の最善手を探そうとする (MAX レベル)
B も B の最善手を探そうとする
= B は A にとって最も不利になる手を探そうとする (MIN レベル)

自分の調べる関数が全ての手を調べて相手の立場で調べる同じ関数を
再帰呼び出しし、それが負けを認めるまで探す
(但し、これは千日手や全検索のできない場合の対処やこちらが勝てない場合の乱数による手の選択も必要となる)

反復深化を更に有効そうな場合にだけ繰り返して行う -> αβ狩り

問題を解くためのデータ構造をよく考える
例えば二次元配列の一次元化、立体の平面化、
形状のテーブル化、ボードに外周を用意など

枝狩りでの様々な条件
挟み込む (ある枝狩りの逆を考えてみる)
検索過程を表示させるロジックを組み込んで観察してみる
巨大なテーブルをハッシュ化して出現回数から絞り込む
メモリを贅沢に利用できる場合を考えてみる

指数関数時間アルゴリズム(2 ** n)よりも
多項式時間アルゴリズム(n ** 2)の方が、n の増加に伴って速くなる
(但し、後者はあまり汎用的でないことが多い)
別解として履き出し法による方法がある

下限値の多重化、下限値をそのつど合計しない(変位分だけ付け加える)

検索