Блог пользователя watson

Метод отжига
Автор watson, 13 лет назад, По-русски

Недавно узнал об этом методе..Прочитал.Не сильно понял.11 класс.

Скажите где можно почитать об этом или оюьясните пожалуйста.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Google Андрей Лопатин Метод отжига, первая ссылка.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      мне бы попроще я читал эту статью
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Суть мне ясна,непонятно как считаются функция G (то есть куда переходить) и как сяитать переходим или нет
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится
        Если я правильно понял о чем Вы, то функция G не приводится, потому что она зависит от конкретной задачи. Это может быть какое-то локальное изменение, часто случайное. Как считать переходим или нет. Вообще что мы хотим сделать? Мы хотим максимизировать / минимизировать какую-то функцию. Для определенности минимизировать. Тогда перейдем с вероятностью Это обеспечивает, то что если функция уменьшилась, то мы всегда перейдем, иначе иногда. Причем, так как T убывает со временем, то чем меньше времени осталось и чем сильнее мы ухудшим функцию, тем менее вероятен переход. Кроме таких можно выбирать другие функции, это описано в предложенной выше статье. Для подбора конкретных переходов, функций, констант типа максимальной и минимальной температуры и.т.д нужно много времени и конкретная задача.

        UPD: Кстати для подбора этих вещей можно использовать еще один отжиг.

        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Теперь твой комментарий - вторая ссылка =)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Google вообще теперь очень оперативно индексирует codeforces. Авторитетный источник получается :).
        → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится
Насколько я понял Метод отжига, на практике он заключается в следующем:

Есть функция от n аргументов, которую можно посчитать за приемлемое время (O(n), O(n^2), ...), и нам нужно найти точку, в которой достигается минимум (максимум) этой функции.
Действуем так:
1) заводим параметр "температура" T = (число, зависящее от задачи, часто "амплитуда" возможных аргументов)
2) генерируем случайно начальное состояние
3) в цикле, пока (не нашли ответ) или (пока T > eps)
3a) из существующего состояния получаем новое, путем случайных изменений, зависящих от T (чем температура больше, тем изменения больше)
        3b) считаем значение функции в получившемся состоянии
3c) если значение меньше предыдущего то берем новое состояние за текущее,
иначе берем его с некоторой вероятностью, также зависящей от T
        3d) уменьшаем T, например так: T *= 0.99;

В общем все. Если повезет, то минимум будет найден.
Насчет того, как принимать решение о переходе на новое состояние (для поиска min):
s1 - текущее состояние, f1 - значение функции в s1, аналогично s2, f2 - новое состояние и значение функции в нем.
Если (f2 <  f1) или (rand() < exp( (f1 - f2) / T )  ), то
s1 = s2;
rand() - случайное значение из [0..1]

Попрактиковаться можно здесь: http://informatics.mccme.ru/moodle/mod/statements/view.php?id=1975 
    
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    > s1 - текущее состояние, f1 - значение функции в s1, аналогично s2, f2 - новое состояние и значение функции в нем.

    > Если (f1 < f2) или (rand() < exp( (f1 - f2) / T ) ), то
    > s1 = s2;

    Ошибочка... если ищется максимум, то во втором условии должно быть ( rand() < exp((f2 - f1) / T) ), если же ищется минимум - то в первом должно быть ( f2 < f1 ).

    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Роскошь, суров)) Отжигать будешь на всероссе, чую)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А что? Я помню кто-то говорил что в прошлом году набрал 98 отжигом по задаче про вершинное покрытие.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я всегда знал, что это полезно, но считал, что этот алгоритм действительно сложен (по сравнению даже с группой А ЛКШ). Может я не прав...
А Виталик действительно крут
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
В TopCoder Marathones очень часто дают задачи на использование подобных универсальных методов глобальной оптимизации. Знание "генетических алгоритмов" и "метода иммитации отжига" и умение их качественно реализовывать может принести достаточно высокий рейтинг. Например, прошлым летом, целых 3 (MM60, TCO10-1, TCO10-2) идущих подряд матча решались модификациями вышеуказанных методов. И я практически уверен, что после этого каждый третий из них тоже мог решаться... Для попадания в top-10 хватало выбрать нужный метод (как правило, из двух :)), аккуратно реализовать и придумать некоторые ускорения, отсечения и хаки, чтобы перегнать остальные top-50, которые делали примерно то же самое :)
→ Ответить