В чем разница между алгоритмами восхождения на вершину и алгоритмами поиска по ветвям и границам?

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

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

Короче говоря, восхождение на холм не гарантирует нахождения правильного ответа, но часто работает очень быстро и дает хорошие приближения. Ветви и границы всегда находят правильный ответ, но это может занять некоторое время.

Надеюсь это поможет!

Восхождение на холм работает следующим образом: Поиск в глубину с отсечением (это простая форма ветвления и привязки). ) работает следующим образом:

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