Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность/Надёжность
Здесь показаны различия между двумя версиями данной страницы.
— |
algoritmy:hill-climbing [2012/08/12 23:01] (текущий) Степан Митькин создано |
||
---|---|---|---|
Строка 1: | Строка 1: | ||
+ | ==== Поиск восхождением к вершине (Hill Climbing) ==== | ||
+ | Алгоритм поиска восхождением к вершине находит такую комбинацию параметров, | ||
+ | при которой значение целевой функции максимально (или минимально). | ||
+ | |||
+ | Восхождение к вершине можно применять, когда: | ||
+ | - Состояние имеет вид набора из нескольких параметров. | ||
+ | - Необходимо найти такое состояние, в котором целевая функция достигает максимума (или минимума). | ||
+ | |||
+ | Поиск начинается из случайной точки. | ||
+ | |||
+ | Перечень следующих состояний, доступных из текущего, строится путём | ||
+ | изменения каждого из параметров по очереди. | ||
+ | То есть каждое следующее состояние отличается от предыдущего только в одном | ||
+ | параметре. | ||
+ | |||
+ | Следующим состоянием из списка доступных выбирается то, | ||
+ | для которого целевая функция максимальна. | ||
+ | |||
+ | Алгоритм останавливается, когда нет таких соседних состояний, | ||
+ | которые имеют значение целевой функции большее, чем у текущего узла. | ||
+ | |||
+ | Алгоритм может работать неэффективно или даже не найти решение для некоторых | ||
+ | пространств поиска. Например, для тех, которые имеют несколько локальных | ||
+ | максимумов (несколько холмов). | ||
+ | Другая опасность -- плато, а также гребни, которые не параллельны одной из координатных осей. | ||
+ | |||
+ | Для борьбы с этим применяют разные дополнительные средства, такие как | ||
+ | несколько перезапусков алгоритма. | ||
+ | |||
+ | ** ДРАКОН-схема поиска восхождением к вершине: ** \\ | ||
+ | {{:algoritmy:hill-climbing-ru.png}} \\ | ||
+ | Скачать исходник в формате [[http://drakon-editor.sourceforge.net/|DRAKON Editor]]: [[http://sourceforge.net/projects/drakon-editor/files/examples/hill-climbing-ru.drn/download|hill-climbing-ru.drn]] | ||
+ | |||
+ | |||
+ | ** ДРАКОН-схема поиска восхождением к вершине на гибридном языке ДРАКОН-Lua: ** \\ | ||
+ | {{:algoritmy:hill-climbing-drakon-lua.png}} \\ | ||
+ | Скачать исходник в формате [[http://drakon-editor.sourceforge.net/|DRAKON Editor]]: [[http://sourceforge.net/projects/drakon-editor/files/examples/hill-climbing.drn/download|hill-climbing.drn]] Из этого файла можно сгенерировать работающий скрипт на Lua. | ||
+ | |||
+ | Степан Митькин |