Подготовка к собеседованию: жадные алгоритмы

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

Жадные алгоритмы — это алгоритмы, которые принимают локально оптимальное решение в надежде, что при принятии этого локально оптимального решения он в конечном итоге найдет глобальный оптимум. Однако при жадном образе мышления часто глобально оптимальное значение оказывается не тем, которое создается. Вместо этого данный ответ часто может быть немного неоптимальным по сравнению с другими факторами. Например, максимальное целое число в вопросе случайного дерева.

Проблемы, в которых жадные алгоритмы работают хорошо, - это когда в вопросе есть свойство жадного выбора или оптимальная подструктура, частично похожая на DP, однако, в отличие от жадных алгоритмов DP, жадные алгоритмы не пересматривают прошлый выбор. Это, очевидно, имеет свои плюсы и минусы, которые следует учитывать в разных ситуациях. Благодаря своим свойствам жадные алгоритмы также относительно быстры с временной сложностью в десять раз O (n log (n)) или O (n). Кроме того, по сравнению с другими алгоритмами, он также более прост, его легко визуализировать и реализовать.

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

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

Некоторые популярные жадные алгоритмы, за которыми вам следует следить в этих интервью по программированию и даже в возможных проектах в будущем, — это проблема выбора действий, проблема раскраски графа, дикстры (однако это объединение нескольких алгоритмов, одним из которых является жадный алгоритм). ) и многое другое.

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

Источники: