Пример задач в алгоритме Simple Hill Climbing - PullRequest
Новая
       62

Пример задач в алгоритме Simple Hill Climbing

0 голосов
/ 28 марта 2019

Какие примеры приводят к тому, что Simple Hill Climbing достигает таких проблем, как локальные максимумы, гребни и переулки, а также проблемы с плато?Я попытался найти:

  • Ссылка один : что дает довольно хороший пример проблемы застревания в простых холмах Simple Hill Climbing в блочных схемах.Тем не менее, он не показывает шаги.
  • Ссылка два : которая дает шаги по поиску решения в SHC.Тем не менее, я не понимаю, как h (1) может быть -6, когда всего есть только четыре блока, и четыре из них неуместны, следовательно, только -4.Также не показаны проблемы, с которыми столкнулся SHC.
  • Ссылка три : я понимаю, как концепция достижения состояния 'g' заставляет ваш алгоритм достигать локального максимума и получатьзастрял.Тем не менее, это довольно неоднозначно, что такое состояния, и я не знаю, к какому состоянию относятся «g» и конечные состояния.

Из прочитанного мною конспекта лекции мне была дана проблема TSP.График представлял собой полный граф с четырьмя узлами: A, B, C и D. Для решения проблемы мы использовали как Simple Hill Climbing, так и Steepest-Ascent Hill Climbing.Эвристическое значение, используемое для решения этой проблемы, было общим расстоянием каждого состояния.Мы можем исследовать другие соседние состояния, переключая положения символов «ABCD», используя 6 различных комбинаций (первая буква <-> вторая, вторая <-> третья и т. Д.).Однако в приведенном примере он не показал, что именно «застряло на локальном максимуме».Ни он, ни проблема с гребнями и переулками, ни проблема с плато.

Может ли кто-нибудь дать мне пример того, как мы достигаем этих проблем и каковы эти проблемы на самом деле в примерах (я понимаю определение каждой проблемы: здесь и здесь )?Для справки ниже приведен образ проблемы TSP, о которой я упоминал: TSP Map

1 Ответ

1 голос
/ 28 марта 2019

Когда вы совершаете простую прогулку по холмам, этот хребет ищет подъем, это будет неэффективно, так как будет идти в направлении x или y, т.е. следовать линиям на этом рисунке.Это приводит к зигзагообразному движению.

Чтобы достичь этого состояния при произвольной начальной позиции, алгоритм оценивает 4 позиции (x + 1, y) (x-1, y) (x, y+1) (x, y-1) (для шага 1) и фото самое высокое.Таким образом, он начнет двигаться к гребню.

Давайте проиллюстрируем это поведение предыдущей картинкой.Учитывая начало в начале координат (0,0) и шаг 1. Тонкие темные линии, пересекающиеся на поверхности, являются единичной точкой ((0,1), (0,2), ..., (1,0), ...) изображения через функцию.Алгоритм выбирает в этих точках, но только те, которые непосредственно смежны (потому что он движется вдоль оси). Это путь, по которому он пойдет.(простите мои плохие навыки рисования).

В ссылке 2, чтобы вычислить эвристическую функцию, вы оцениваете каждый блок, если блок не на своем месте (иначе говоря, не в нужном индексе в стопке), каждый блок под нимдобавить -1, в противном случае каждый блок под ним добавить +1.h (1) = -3 -2 -1 (A находится не на своем месте, под ним 3 блока, поэтому -3, то же самое для B, но 2 блока, поэтому -2, C -1 и D не имеют блока под ним, поэтому не добавляетчто угодно)

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

Надеюсь, я понял ваш вопрос.

...