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

Question

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

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

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

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

Answer 1

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

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

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