Пример алгоритма Hill climbing

Я немного смущен алгоритмом Hill Climbing. Я хочу "запустить" алгоритм, пока не найду первое решение в этом дереве ( "a" является начальным, а h и k являются конечными состояниями), и он говорит, что числа вблизи состояний являются эвристическими значениями. Здесь дерево:

Мой вопрос: я пытаюсь запустить холм, поднимающийся по дереву, так что хорошо, мы начинаем a- > f- > g, а затем что-то заканчиваем (без результата), но я читаю, что восхождение на холме не может вернуться и сделать новый выбор ( пример j или e)? Это правильно? Если я смогу вернуться назад, то как? я имею в виду, когда мы меняем наш первоначальный выбор, мы выбираем e вместо g или j вместо f

Извините, если мой вопрос слишком прост.

Ответ 1

Обычный способ избежать застревания в локальных максимумах с Hill Climbing - использовать случайные перезагрузки. В вашем примере, если G является локальным максимумом, алгоритм остановится, а затем выберите другой случайный node для перезапуска. Поэтому, если выбраны J или C (или, возможно, A, B или D), вы найдете глобальные максимумы в H или K. Прополощите и повторите достаточно много раз, и вы найдете глобальные максимумы или что-то близкое; в зависимости от ограничений времени/ресурсов и проблемного пространства.

Обратите внимание, что локальный поиск, например Hill Climbing, не является полным и не может гарантировать обнаружение глобальных максимумов. Разумеется, преимущество состоит в том, что для этого требуется небольшая часть ресурсов. На практике и применительно к правильным проблемам это очень эффективное решение.

Ответ 2

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

Ответ 3

Скалолазание не имеет гарантии от застревания в локальных минимумах/максимумах. Тем не менее, только самая чистая форма восхождения на холм не позволяет вам либо отступить.

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

Ответ 4

одна из проблем с восхождением на холм застревает в локальных минимумах, и это происходит, когда вы достигаете F. Улучшенная версия восхождения на холм (которая фактически используется практически) заключается в том, чтобы перезапустить весь процесс, выбрав случайный node в дереве поиска и снова продолжить поиск оптимального решения. Если вы снова застряли в некоторых локальных минимумах, вам нужно снова перезапустить другой случайный node. Как правило, существует ограничение на нет. времени вы можете повторить этот процесс поиска оптимального решения. После достижения этого предела вы выбираете наименьшее из всех локальных минимумов, которые вы достигли во время процесса. Хотя он еще не завершен, но у этого есть больше шансов найти глобальное оптимальное решение.

Ответ 5

На самом деле в Hill Climbing вы обычно не отступаете, потому что вы не отслеживаете состояние (это локальный поиск), и вы будете отойти от максимумов. Ни обратное отслеживание, ни Tabu Search не помогают ответить на вопрос: первый только отталкивает вас от локальных максимумов, а последний не дает вам пересмотреть те же локальные максимумы. Также вам не удастся достичь глобальных максимумов. - Tyson Oct 16 '12 в 22:59

", где вы помните предыдущие плохие результаты и целенаправленно избегаете их" Я не могу согласиться, вы отмечаете как табу также хорошие решения, но вы не хотите повторять тот же путь снова. -

Ответ 6

Вот решение:

A → F, с наименьшей возможной стоимостью F → G со стоимостью 3, но пути нет.

Перезагрузите с наименьшей возможной стоимости, отличной от G, ну, это E, потому что E уже вставлен в очередь очереди/стека/приоритета или любую используемую структуру данных.

Таким образом, E → I, но у меня есть более высокая стоимость, чем E, поэтому вы застреваете: S

Перезапустите с наименьшей стоимости, отличной от F E и G, поэтому мы выбираем J, потому что J имеет более низкую стоимость, чем B с разницей в 2, т.е. J = 8 B = 10

J- > K со стоимостью 0, таким образом, K является целью

ПРИМЕЧАНИЕ. Предлагаемая вариация подъема холма для случайного выбора точки, но выбор наименьшей стоимости, отличной от уже посещенных узлов, лучше, чем выбор случайно.

ДРУГОЕ ПРИМЕЧАНИЕ: это то, что когда node E не посещает I, потому что у меня выше, чем E, алгоритм уже вставил его в структуру данных, поэтому выбор наименьшей стоимости, отличной от уже посещенной, создаст новую путь от I, потому что меня никогда не посещали, и, следовательно, он имеет меньшее значение, чем J, это единственный путь, который я пропустил.

Ответ 7

путь по чистому поднятию холма будет a- > J → k если вы расширяете детей слева направо, если вы разложите их справа налево, вы получите в этом локальном минимуме A → F → G, но обычно мы расширяем слева направо.