Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность/Надёжность
Здесь показаны различия между двумя версиями данной страницы.
Следующая версия | Предыдущая версия | ||
algoritmy:annealing [2012/08/30 21:45] Степан Митькин создано |
algoritmy:annealing [2012/08/30 22:04] Степан Митькин Починил ссылку. |
||
---|---|---|---|
Строка 1: | Строка 1: | ||
+ | ==== Поиск симуляцией отжига ==== | ||
+ | |||
Симуляция отжига - алгоритм поиска, сочетающий эвристику и случайность. | Симуляция отжига - алгоритм поиска, сочетающий эвристику и случайность. | ||
Эвристика указывает перспективное направление поиска. | Эвристика указывает перспективное направление поиска. | ||
Строка 13: | Строка 15: | ||
Температура достигает низшей точки при завершении поиска. | Температура достигает низшей точки при завершении поиска. | ||
- | Работа алгоритма начинается со случайно выбранного состояния. | + | Алгоритм: |
- | Для текущего состояния находятся соседние доступные состояния. | + | * Работа алгоритма начинается со случайно выбранного состояния. |
- | Из доступных состояний случайным образом выбирается следующее. | + | * Для текущего состояния находятся соседние доступные состояния. |
- | Близость состояния к цели оценивается эвристической функцией. | + | * Из доступных состояний случайным образом выбирается следующее. Близость состояния к цели оценивается эвристической функцией. |
- | Если следующее состояние ближе к цели, чем текущее, то оно делается текущим. | + | * Если следующее состояние ближе к цели, чем текущее, то оно делается текущим. |
- | Если нет, то решение следовать худшему выбору или взять какое-нибудь другое состояние принимается с некоторой вероятностью. | + | * Если нет, то решение следовать худшему выбору или взять какое-нибудь другое состояние принимается с некоторой вероятностью. Эта вероятность зависит от температуры. Чем температура выше, тем больше вероятность согласиться на менее выгодное направление. |
- | Эта вероятность зависит от температуры. | + | |
- | Чем температура выше, тем больше вероятность согласиться на менее выгодное направление. | + | |
Из-за понижения температуры к концу поиска невыгодные состояния исследуются реже. | Из-за понижения температуры к концу поиска невыгодные состояния исследуются реже. | ||
Строка 26: | Строка 27: | ||
В конце алгоритм производит тонкую настройку решения. | В конце алгоритм производит тонкую настройку решения. | ||
Точность, с которой эвристическая функция делает оценки, очень важна для производительности алгоритма. | Точность, с которой эвристическая функция делает оценки, очень важна для производительности алгоритма. | ||
+ | |||
+ | **Реализация поиска симуляцией отжига на гибридном языке ДРАКОН-Lua:** \\ | ||
+ | {{:algoritmy:anneal.png?1000|}} \\ | ||
+ | Скачать исходник в формате [[http://drakon-editor.sourceforge.net/|DRAKON Editor]]: [[http://sourceforge.net/projects/drakon-editor/files/examples/anneal.drn/download|anneal.drn]] Из этого файла можно сгенерировать работающий скрипт на Lua. | ||
+ | |||
+ | Степан Митькин | ||
+ |