Greedy: свободное припоминание
Подсказки на свободное припоминание по всему юниту. Сначала отвечайте по памяти, затем раскрывайте модельный ответ и сравнивайте — именно усилие припоминания закрепляет дисциплину доказательства.
Припоминание сильнее перечитывания. На каждую подсказку проговорите или запишите полный ответ по памяти, прежде чем открыть модельный. Восстановление exchange argument с нуля и есть то, что превращает его из узнаваемого в применимое.
Восстановите стержень юнита — два условия корректности greedy, три хода exchange argument, ключи сортировки для interval-задач и инвариант Gas Station — не заглядывая обратно в уроки.
- 01Какими двумя свойствами должна обладать задача, чтобы greedy был оптимален, и что означает каждое?
- 02Назовите три хода exchange argument и направление рассуждения, которое заставляет его работать.
- 03Почему в шаге обмена достаточно «не хуже» (а не «строго лучше») и почему это правильная сила утверждения?
- 04Для interval-задач какой ключ сортировки соответствует какой цели и почему каждый корректен?
- 05Чем «greedy stays ahead» отличается от exchange argument и когда вы бы его применили?
- 06В Gas Station какое глобальное условие решает о выполнимости и почему сброс кандидата-старта в i+1 безопасен?
Если вы восстановили каждый ответ по памяти, вы держите стержень юнита: greedy оптимален только при наличии greedy choice property плюс optimal substructure; exchange argument доказывает безопасность, переформировывая оптимум к greedy swap-ами «не хуже» (а отсутствующий swap сам по себе доказательство провала); interval-задачи живут или умирают по ключу сортировки — finish для максимизации, start для merging, sweep по стартам и финишам для комнат; а scan-greedy вроде Gas Station решают о выполнимости по глобальному инварианту, пока самокорректирующийся сброс находит старт за один проход.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.