Стохастический алгоритм восхождения на холм против алгоритмов первого выбора

Алгоритм поиска Hill Climbing Search является одним из семейства локальных поисков, которые основываются на лучших состояниях своих соседей. Стохастический Hill Climbing выбирает случайное лучшее состояние из всех лучших состояний в соседях, в то время как первый выбор Hill Climbing выбирает первое лучшее состояние из случайно сгенерированных соседей.

Восхождение на холм первого выбора станет хорошей стратегией, если в текущем штате много соседей.

Я цитирую Искусственный интеллект: современный подход (3-е изд.) ( 2010) Рассел, Норвиг

Стохастик при подъеме в гору выбирает случайный выбор среди движений вверх; вероятность выбора может варьироваться в зависимости от крутизны подъема. Обычно он сходится медленнее, чем самый крутой подъем, но в некоторых ландшафтах штатов он находит лучшие решения. Восхождение на холм первого выбора реализует стохастическое восхождение на холм путем случайного генерирования последователей, пока не будет сгенерирован тот, который лучше текущего состояния. Это хорошая стратегия, когда у государства много (например, тысячи) преемников.

Итак, восхождение на холм первого выбора - это особый вид стохастического восхождения на холм.

Общее восхождение на холм - это алгоритм локального поиска, который выбирает лучшее из соседа, то есть выбирает соседа с самым крутым путем и лучшим значением целевой функции. Но из-за этого он может не достичь глобального максимума и застрять на локальном максимуме. Принимая во внимание, что в случае стохастического восхождения на холм он случайным образом выбирает соседа с движением в гору, и вероятность выбора может меняться с крутизной подъема. В случае первого выбора восхождения на холм он случайным образом генерирует следующее движение и выполняет поиск пока не будет найдено состояние, которое лучше всех состояний.