Алгоритм восхождения на простой пример

Question

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

Answer 5

Вот решение:

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

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

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

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

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

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

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

Answer 6

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

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

Answer 7

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