Резюме
В этой теме вы узнали, что такое жадные алгоритмы.
В жадном алгоритме на каждом шаге выбирается локально оптимальное решение.
Иногда такое решение может подходить не только для конкретного шага, но и для всей задачи.
Если вы нашли корректное жадное решение, скорее всего сложность этого алгоритма небольшая.
Иногда жадные алгоритмы применяют для нахождения приближённых решений. С таким алгоритмом можно быстро получить ответ близкий к оптимальному.
Вы познакомились с задачей о рюкзаке. Дан набор предметов, каждый из которых имеет стоимость и вес. И есть рюкзак, в который поместятся предметы общим весом не больше определённого порога. Нужно уложить как можно больше ценных вещей в рюкзак. Мы рассмотрели жадный алгоритм, который интуитивно кажется верным, но не решает задачу для любых входных данных.
Сложность решения задачи, которое подразумевает полный перебор, O(2ⁿ).
Также вы рассмотрели пример с радиостанциями. Требовалось установить наименьшее количество радиостанций, при этом трансляция должна быть во всех населённых пунктах. Это задача покрытия множества.
Существуют разные варианты формулировки задачи о покрытии множества.
Например, для выполнения задания нужен набор навыков. Есть группа людей, каждый из которых владеет некоторыми из них. Нужно сформировать наименьшую подгруппу, достаточную для выполнения задания. То есть такую, которая включает в себя носителей всех необходимых навыков.
Общая формулировка задачи такая. Дано произвольное множество и набор его подмножеств. Нужно найти такое объединение подмножеств, чтобы они в совокупности покрывали всё множество, и при этом их число было наименьшим возможным.
С помощью полного перебора задачу можно решить за O(2ⁿ).
Вы изучили жадный алгоритм, который находит приближённое решение за O(n²).
Также мы сформулировали задачу, в которой нужно доставлять на все сервера обновления софта оптимальным способом. Не забывайте про эту задачу. Она еще встретится далее в курсе.
Кроме этого, вы узнали, что в множестве из n элементов 2ⁿ подмножеств.
Разобрались, как найти вероятность события. Для этого нужно число благоприятных исходов разделить на общее число возможных исходов.
А тем временем Гоша с друзьями попал в Трешландию, где их ждёт много приключений!