山登り法

山登り法（やまのぼりほう、）は、評価関数の極値を探索する探索アルゴリズム。最も代表的な局所探索法として知られている。最良優先探索は過去の解を管理するが、探索対象を現在の解だけに制限したものである。評価関数を使用する探索アルゴリズムとしては最も単純。

 概要 
山登り法とは「現在の解の近傍の内で最も成績の良い解」を近傍解として選び、「現在の解より近傍解の成績の方が良い場合」に近傍解と現在の解を入れ換える局所探索法の方法。極値を見つけ出すことがゴールであり、極値を見つけ出したら探索終了。局所探索法の最も単純かつ代表的な方法であり、しばしば局所探索法と同一視される。

 最小値･最大値の探索 
極値を探索するアルゴリズムのため、評価関数の最小値･最大値の探索手法としては不完全である。しかし実装が単純なため、最小値･最大値の探索としても、しばしば用いられる。

山登り法を使用して最小値･最大値を探索する方法の1つとして、ランダムに探索開始の初期値を複数選び、探索が終了し極値が見つかった後、見つけた極値の中から最小値･最大値を選ぶという乱択アルゴリズムがある。評価関数の特性として、最小値･最大値にたどり着ける初期値の割合がある程度多ければ、十分な数だけ初期値を用意すれば、最小値･最大値にたどり着ける確率は高くなるが、最小値･最大値にたどり着ける初期値の割合が非常に0に近いと、最小値･最大値を見つけ出すことは困難になる。初期値の用意の仕方としてランダムではなく、メッシュ状に均等間隔で選ぶという方法もある。

 擬似コード 
擬似コードを以下に示す。この擬似コードでは EVAL(node) の極大値を探索している。

EVAL(node)
node の評価値を返す関数
NEIGHBORS(node)
node の近傍の集合を返す関数
bestNode
探索した中での最良解

 function 山登り法(startNode)
     bestNode = startNode
     bestEval = EVAL(bestNode)
     無限ループ
         nextNode = NULL
         nextEval = 負の無限大
         for each (x in NEIGHBORS(currentNode))
             if (nextEval < EVAL(x))
                 nextEval = EVAL(x)
                 nextNode = x
         if (nextEval <= bestEval)
             return bestNode
         bestNode = nextNode

 関連項目 
 局所探索法
 最良優先探索

Category:検索アルゴリズム
Category:メタヒューリスティクス
Category:数学に関する記事