山登り法

山登り法（やまのぼりほう、英: hill climbing, HC）は、アルゴリズムの一種である。最も代表的な局所探索法として知られている。

概要

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

この方法は極値で必ず探索が収束してしまうため、探索手法としては不完全である。しかし実装が単純であり、解の探索が非常に高速であるため、しばしば用いられる。探索が収束したときは新たに初期解を選び直してから再び探索を開始することで短時間で精度の良い近似解を得ることができる。

擬似コード

擬似コードを以下に示す。ここでは現在の解を currentNode、近傍の集合を L とし EVAL(node) は node の成績を出力する関数である。

Algo (Hill Climbing)
  bestEval = -INF;
  currentNode = startNode;
  bestNode = NULL;
  for MAX times
     if (EVAL(currentNode) > bestEval)
         bestEval = EVAL(currentNode);
         bestNode = currentNode;
     L = NEIGHBORS(currentNode);
     nextEval = -INF;
     for all x in L
        if (EVAL(x) > nextEval)
             currentNode = x;
             nextEval = EVAL(x);
  return currentNode;

関連項目

• 局所探索法