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

Что такое жадный алгоритм? В определении книги говорится, что жадный алгоритм делает оптимальный выбор на каждом шаге, чтобы найти глобально оптимальное решение проблемы. То, что этот британский старик претенциозно говорит вам, куря трубку (вот как они выглядят в моем извращенном воображении), на самом деле очень простая идея. В любой момент вашего алгоритма вместо того, чтобы перебирать все возможные решения и выбирать лучшее, просто выберите то, которое кажется лучшим. Затем на следующем шаге выберите тот, который снова кажется лучшим. Промойте и повторяйте, пока не дойдете до конца пути и просто надейтесь, что ваш локально оптимальный выбор приведет вас к глобальному оптимуму.

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

Проблема выбора деятельности

Это очень известная проблема, почти клише. Вам дается ряд действий, каждое из которых имеет определенное время начала и окончания. У них есть общий ресурс (может быть, ваше время?), И некоторые из них явно пересекаются. Ваша задача - выбрать подмножество действий с максимальной мощностью, в котором нет перекрытий.

В таблице выше дано десять занятий с указанием времени начала и окончания. Подмножество {2, 4, 8} не содержит перекрытий, в то время как подмножество {5, 6} есть. Нам нужно делать жадный выбор, чтобы найти наибольшее возможное подмножество. Вот несколько возможных жадных подходов:

  • Сначала выберите самое раннее начальное действие
  • Сначала выберите самое раннее завершающее действие
  • Сначала выберите самое короткое занятие

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

Для меня очевидно, что всегда нужно выбирать действие, которое оставляет ресурс доступным для как можно большего числа других действий. Затем давайте начнем с третьего подхода. Во-первых, вам нужно отсортировать действия по времени их выполнения. Затем повторите действия и, если текущее действие начинается после завершения предыдущего, добавьте его в набор результатов. Вот код C ++ при условии, что действия уже отсортированы.

vector<int> findMaximumSubset(vector<Activity> activities) {
    
    vector<int> result;
    result.push_back(0);
    for (size_t i = 1; i < activities.size(); i++) {
        if (activities[i].start >= activities[i - 1].finish) {
            result.push_back(i);
        }
    }
    return result;
}

Обратите внимание, что самое раннее действие появляется первым, когда два действия имеют одинаковое время выполнения. Это очень простой алгоритм, при его выполнении создается подмножество {2, 4, 8} для данной таблицы. Но подождите, оптимальное решение - это подмножество {1, 4, 7, 10}, и наш алгоритм не смог его найти!

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

Когда вы выполните код, вы увидите, что он фактически создает подмножество {1, 4, 7, 10}, что, кстати, является оптимальным решением. Очевидно, что оба подхода использовали жадные алгоритмы, но первый не дал нам оптимального решения. Бывают случаи, когда не найти оптимального решения - это нормально, но зачем это делать, если вы можете так легко достичь оптимального?

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

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

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

Проблема с рюкзаком

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

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

Давайте немного изменим задачу. После нескольких лет краж в магазинах вы теперь хотите играть в большой детской лиге и, чтобы проявить себя, вы будете участвовать в работе в банке! Не обращая внимания на предстоящие печальные события, вы вошли в хранилище банка со своим верным 10-килограммовым мешком. В хранилище находится один золотой, один серебряный и один платиновый слиток весом 4 кг, 6 кг и 2 кг соответственно. Каждый золотой слиток стоит 100 долларов, серебро - 120 долларов, платина - 60 долларов. Так что платина является наиболее ценной, затем золото и затем серебро, если рассчитывать их цену за килограмм.

Если мы применим ту же стратегию, которую использовали во времена воровства в магазинах, нам нужно сначала взять слиток платины, поскольку он является наиболее ценным на килограмм. Затем мы берем золотой слиток, что дает нам всего 160 долларов за 6 кг нашего хранилища. Мы не можем взять серебро, потому что в сумке осталось всего 4 кг. Для оптимального решения нужно было взять слитки золота и серебра, которые в сумме стоили бы 220 долларов на 10 кг вместимости мешка.

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