Визуальный язык ДРАКОН
Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность/Надёжность
Инструменты пользователя
algoritmy:hill-climbing
Различия
Здесь показаны различия между двумя версиями данной страницы.
| — |
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. | ||
| + | |||
| + | Степан Митькин | ||
algoritmy/hill-climbing.txt · Последние изменения: 2012/08/12 23:01 — Степан Митькин