Как обнаружить жадные алгоритмы [Технические вторники]

Одна из самых востребованных тем.

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

Основные моменты

В этом посте будут рассмотрены следующие идеи:

Что делает жадный алгоритм. Жадные алгоритмы жадны, потому что они не смотрят вперед. Они принимают наилучшее решение на данный момент, не задумываясь о том, может ли худший вариант сейчас привести к лучшим результатам позже. С математической точки зрения, жадные алгоритмы всегда максимизируют локальные оптимумы за счет частого пропуска глобального оптимума.
Как выявлять жадные алгоритмы. Используя список вопросов и соображений, вы можете эффективно определять вопросы с помощью жадных алгоритмов.
Как добиться успеха в этом — Практика. Много практики.

Этот пост изменит вашу жизнь. Приготовься.

Будьте готовы к первоклассному контенту.

Что делает жадный алгоритм?

Я мог бы дать вам теоретическое определение (я сделал это в основных моментах), но большинству из вас это не нужно. Если вам это интересно, я могу провести еще один математический понедельник, посвященный математическим свойствам жадных алгоритмов. Так что вместо этого наслаждайтесь этой прекрасной графикой, которую я взял из Википедии.

Жадные алгоритмы часто встречаются в ИИ и теории принятия решений. Когда ситуация очень сложная и нужно учитывать слишком много факторов, жадные алгоритмы могут стать отличной альтернативой тому, чтобы что-то сделать. Задача коммивояжера — отличный пример. Однако вопросы в интервью в стиле Leetcode намного проще и обычно могут быть оптимально решены с помощью жадных алгоритмов. Так как же узнать, подходит ли вопрос для жадного подхода? Давайте взглянем.

Как обнаружить жадные алгоритмы?

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

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

Почему это правда? Вспомните, как мы определили жадное решение. Это будет идти для локальных оптимумов над глобальными оптимумами. Если оптимальные решения всех ваших подзадач являются частью вашего решения, то использование локальных оптимумов приведет к лучшему решению в глобальном масштабе.

Лучший способ проверить это — ответить на ваш вопрос и смоделировать алгоритмы на небольших входных данных. Это поможет вам быстро определить структуру.

Наряду с этим, есть несколько наводящих вопросов, которые помогут вам обнаружить жадные алгоритмы. Рассмотрим следующее-

Есть ли у меня выбор между различными альтернативами в какой-то момент? Для изучения вариантов существуют жадные алгоритмы.
Приводит ли этот выбор к подзадачам, которые можно решить индивидуально?
Смогу ли я использовать решение подзадачи для решения общей проблемы?

Эта дискуссия довольно интересная. Он исследует идеи, упомянутые здесь, с еще несколькими примерами.

Как стать хорошим

Это самая скучная часть бюллетеня. Постоянные читатели точно знают, что я собираюсь сказать. Вам нужно будет применить эту структуру для множества жадных вопросов, чтобы развить свою интуицию в этой теме.

Продолжая практиковаться, убедитесь, что вы анализируете проблемы, чтобы сделать эту процедуру более комфортной. Работая с этим, вы обнаружите, что ваши навыки становятся намного лучше.

Я создал Упрощенную технологию, используя новые методы, полученные в результате обучения нескольких людей в ведущих технологических компаниях. Информационный бюллетень предназначен для того, чтобы помочь вам добиться успеха, избавив вас от часов, потраченных впустую на посредственные ресурсы или на рутинную работу с Leetcode. Легко найти ваши потребности удовлетворяются в одном месте. У меня есть политика 100% удовлетворенности, поэтому вы можете попробовать ее без риска для себя. Используйте кнопку ниже, чтобы получить скидку 20 % на целый год. Использование этой скидки снизит цены-

800 индийских рупий (10 долларов США) → 533 индийских рупии (8 долларов США) в месяц

8000 индийских рупий (100 долларов США) → 6400 индийских рупий (80 долларов США) в год

Получи скидку 20% на 1 год

Если вам нравится то, что я пишу, я был бы очень признателен за анонимный отзыв. Вы можете оставить его здесь.

В комментариях ниже поделитесь темой, на которой вы хотите сосредоточиться. Мне было бы интересно узнать, и я расскажу о них. Чтобы узнать больше о новостной рассылке, ознакомьтесь с подробной информацией О странице + часто задаваемые вопросы.

Если вам понравился этот пост, обязательно заполните этот опрос. Это анонимно и займет 2 минуты вашего времени. Это поможет мне лучше понять вас, что позволит улучшить содержание.

https://forms.gle/XfTXSjnC8W2wR9qT9