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