В чем разница между жадным и крутым алгоритмами?

У меня есть слайды, где сравниваются 2 версии алгоритмов локального поиска: жадный и крутой.

Жадный: сгенерировать решение x; повторить { для каждого y в N(x) в случайном порядке { if f(y< /strong>) > f(x) тогда x = y; } } пока не было найдено лучшего решения

Самый крутой: сгенерировать решение x; повторить { найти наилучшее решение y в N(x); если f(y) > f(x) то x = у; } пока не было найдено лучшего решения

Но везде в Интернете я читал, что жадный метод ищет лучшее (не первое лучшее найденное) решение. Итак - какая разница? И: какая версия верна?


mathematical-optimization minimization
person Marcin Robaszyński    schedule 24.10.2011    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Я согласен, что жадный также будет означать самый крутой, поскольку он пытается сделать локально оптимальный выбор. Для меня разница в том, что понятие наискорейшего спуска/градиентного спуска тесно связано с оптимизацией функций, в то время как жадность часто звучит в контексте комбинаторной оптимизации. Однако оба описывают одну и ту же «стратегию».

На мой взгляд, эти понятия не очень хорошо подходят для описания поведения, которое вы хотите описать. Я предпочитаю термины лучшее улучшение и первое улучшение локальный поиск. Как жадный локальный поиск, так и метод наискорейшего спуска были бы лучшим улучшением методов локального поиска.

С регулярными выражениями жадность имеет аналогичное значение: рассмотрение максимально возможного совпадения с выражением с подстановочным знаком. Также было бы неправильно утверждать, что жадное сопоставление сработает при первой возможности.

person Andreas    schedule 24.10.2011
comment
en.wikipedia.org/wiki/Hill_climbing: в простом восхождении на холм первым ближайшим узлом является выбираются, в то время как при восхождении на холм с самым крутым подъемом сравниваются все преемники и выбирается ближайший к решению и en.wikipedia.org/wiki/ (восхождение на холм — жадный алгоритм). Похоже, крутой какой-то жадный. - person Marcin Robaszyński; 26.10.2011