山登り法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
探索 > 局所探索法 > 山登り法

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

概要[編集]

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

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

擬似コード[編集]

擬似コードを以下に示す。ここでは現在の解を currentNode、NEIGHBORS(node) は node の近傍の集合を返す関数、EVAL(node) は node の評価値を返す関数である。評価値の大きなノードを探索している。

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

関連項目[編集]