山登り法とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 山登り法の意味・解説 

山登り法

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/02/20 01:54 UTC 版)

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

概要

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

最小値・最大値の探索

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

山登り法を使用して最小値・最大値を探索する方法の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

関連項目




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「山登り法」の関連用語

山登り法のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



山登り法のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの山登り法 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS