«При подготовке к сражению я всегда находил, что планы бесполезны, но планирование - обязательно.»
- Дуайт Д. Эйзенхауэр
Часто ли вы задаетесь вопросом: как найти идеальный баланс между строгим планированием и спонтанностью в жизни? Многие стремятся к идеальной структуре, четким планам и неукоснительному их выполнению. Другие же полагают, что мир слишком хаотичен для планирования, предпочитая действовать по наитию.
Я же придерживаюсь концепции "контролируемого хаоса" и принципа ограниченной рациональности Герберта Саймона:
Рациональные экономические агенты не будут тратить чрезмерные ресурсы на отыскание оптимального решения.
Мы не всегда можем найти идеально оптимальное решение за адекватное время, поэтому нам приходится искать компромисс между точностью и скоростью. А иногда у нас для принятия абсолютно верного решения может просто не хватать информации. Поэтому приходится довольствоваться прогнозами, которые могут быть ошибочными. Так как же быть?
На этот вопрос дают ответ приближенные и онлайн алгоритмы. Они становятся незаменимыми инструментами для эффективного решения задач в условиях ограниченного времени, информации и ресурсов.
Приближенные алгоритмы
Представьте, что вы гениальный предприниматель Алексей и вам нужно собрать команду для разработки стартапа. У вас есть множество компетенций, которые нужно покрыть, чтобы стартап состоялся.
Для этого необходимо, чтобы на каждую компетенцию нашелся хотя бы один член команды, который ей владеет. А люди часто могут владеть несколькими компетенциями сразу. При этом за свои знания они могут требовать повышенную зарплату. Необходимо найти такую команду, чтобы обязательно покрывались все требуемые компетенции, а затраты на выплаты ей были минимальны.
Эта задача называется задачей о покрытии множествами. И, как правило, на решение таких задач может уходить до неприличия много времени, так как идеально она решается лишь через полный перебор.
Но мы можем пожертвовать точностью решения и быстро получить ответ, который даст нам команду покрывающую все компетенции, но требует больше денег для содержания по сравнению идеальным вариантом. Для этого в начале жестко математически формализуем задачу.
Задача о покрытии множествами
Дано: конечное множество U из n элементов, набор его подмножеств S = { S_1, ..., S_k} и веса подмножеств c: S -> Q.
Найти: минимальный по весу поднабор из S, покрывающий множество U.
Здесь U - это покрываемый набор компетенций, а S - множество потенциальных членов нашей команды. Каждый из них желает за участие в команде соответствующую зарплату ("вес"). Требуемую зарплату i-м работником мы обозначим за c(S_i).
А теперь прикинем число "влоб" перебираемых комбинаций для решения этой задачи. Пусть у нас имеется k знакомых (кол-во элементов множества S). Во всех комбинациях каждый из наших знакомых будет иметь два свойства: либо он в нашей команде, либо нет. Следовательно, мы имеем 2^K комбинаций. А если учесть, что почти у всех людей в среднем 100 контактов в их круге общения, то получается, что на поиск команды потребуется примерно 10^21 секунд (из расчета, что наш машина перебирает 10^9 комбинаций в секунду) или примерно 3 ×10^13 лет. Думаю, ни у кого столько времени нет. Для этого и нужный приближенный алгоритмы ;)
Решение задачи
В 1979 году Хватал предложил жадный алгоритм для задачи о покрытии множествами. Суть его в том, что на каждом этапе набора людей в команду мы высчитываем их «неэффективность». Она равна требуемой зарплате делённой на число навыков, которые есть у сотрудника, но нет у нас в команде. И на каждом шаге мы добавляем в команду сотрудника с самой низкой «неэффективностью». Реализация этого принципа выглядит так:
Этот же алгоритм, реализованный на языке программирования Python:
Определение
Пусть I - это некоторая задача минимизации, тогда алгоритм решающий задачу обозначим за A. Значение минимума, которое находит алгоритм будем называть величину A(I), а через OPT(I) минимальное значение для задачи.
Тогда полиноминальный алгоритм А будем называть ρ-приближенным алгоритмом для задачи минимизации, если для любых начальных условий задачи минимизации I выполняется неравенство:
Другими словами, находя минимум алгоритмом A мы ошибаемся не более чем в ρ раз. Теперь докажем, что алгоритм Хватала является приближенным!
Доказательство
Для начала докажем простую лемму:
Таким образом, мы можем окончательно заключить, что алгоритм приближенный, причем ρ=H_n
Рассмотрим на частных случаях как работает алгоритм и как соотносятся оптимальные значения и значения достигаемые алгоритмом.
Примеры
Для наглядности снова рассмотрим пример из программы. Рассмотрев все alpha_i, мы выбираем множество {7, 8}, так как его неэффективность наименьшая равная [стоимость множества]/[количество уникальных элементов в множестве] = 3/2 = 1.5
Аналогично выбираем множество {3, 4, 9, 10} c неэффективностью 7/4 = 1.75. Множество {2, 3, 5} содержит элемент 3, который уже покрыт предыдущим множеством, но несмотря на это он является самым эффективным с характеристикой alpha_i = 6/2.
Таким образом, приближенные алгоритмы могут быть достаточно эффективным методом получения "достаточно хорошего" решения задачи. Однако во многих задачах зачастую даже истинность получаемых данных может ставиться под вопрос. Например, что если мы на вход получаем информацию от оракула? Он может ошибаться, например, если в качестве оракула выступает нейросеть или какой-то аналитик/прогнозист. Для ненадежных данных существует следующее семейство алгоритмов.
Онлайн алгоритм
Концепция онлайн-алгоритма естественным образом вытекает из теории приближенных алгоритмов. Даже многие определения в этой области устроены схожим образом.
Чтобы лучше представить какие задачи решает этот алгоритм давайте представим, что мы приехали на горнолыжный курорт. Допустим, не знаем заранее сколько будем кататься (сколько дней погода будет это позволять). А имеем только прогноз. Мы можем либо в какой-то из дней купить лыжи за b рублей и кататься бесплатно, либо арендовать их за 1 рубль в день. Наша задача по итогу за все дни пребывания на горнолыжной базе потратить как можно меньше денег.
Допустим, Ваш коллега (оракул), который часто ездит по горнолыжным курортам, предположил, что хорошая погода продержится еще Y дней. Фактическое число дней пребывания мы же примем за X. Разницу фактического числа дней пребывания и прогноза обозначим за M = |X-Y|.
Рассмотрим самое наивное решение, что будет если полностью положиться на прогноз коллеги. Вы же ему доверяете не так ли? =)
Определение 1
Пусть ALG - решение которое отыскивает алгоритм по предоставленным данным M, а OPT - оптимальное решение которое отыскивает алгоритм, если предоставленные данные истинны. Тогда конкурентным соотношением будем называть c(M) = ALG(M)/OPT, где M - это ошибка предсказателя.
Тогда мы будем называть алгоритм r-согласованным, если с(0) = r. То есть он отображает насколько хорошо алгоритм справляется с задачей относительно оффлайн, когда ошибка предсказания нулевая.
Решение 1
Давайте, тогда если число дней Y будет больше b, то мы покупаем лыжи в первый день, а иначе будем только арендовать. Мы получим 1-устойчивый алгоритм:
Вроде как все ничего, но если разобраться все случаи, то окажется, что если наш коллега не сильно ошибся с прогнозом погоды, то все в порядке и мы получаем оптимальное решение.
А если же ошибка велика, то у нас вылазит сумма OPT+M, в которой если M устремить на плюс бесконечность, то мы от оптимального значения отдалимся тоже на бесконечность. То есть было бы ошибкой всецело доверять нашему "коллеге". Как же быть?
Определение 2
Дело в том, что при составлении онлайн-алгоритма для оценки его качества одной лишь согласованности не достаточно. Необходимо, ввести некий критерий, который будет как-то характеризовать независимость решения алгоритма от ошибки.
Возвращаясь к предыдущей терминологии, введем такое понятие как k-устойчивость. Мы говорим, что алгоритм k-устойчивость, если для любой ошибки M выполняется неравенство c(M) <= k. Таким образом, решение 1 не является устойчивым.
С новым знанием рассмотрим другое решение задачи!
Решение 2
Давайте все-таки вспомним, что наш коллега не всегда верно прогнозирует, а иногда и просто врет. Но другого источника информации у нас нет...
Поэтому введем параметр p, который лежит в множестве (0; 1) и характеризует наше доверие коллеге. Тогда мы можем в зависимости от значения параметра принимать разные решения:
Такой алгоритм является (1+1/p)-устойчивый и (1+p)-согласованный. Доказывается это по аналогии с решение 1 через разбор частных случаев.
ЗАМЕЧАНИЕ: благодаря введению параметра p мы можем варьировать доверие прогнозу, а, следовательно, балансировать между устойчивостью и согласованностью.
Заключение
Таким образом, идея о приближенных и онлайн алгоритмах в полной мере характеризует баланс между управлением хаоса и порядком. Задачи, которые решаются этими подходами, очень много и часто мы даже не догадываемся об их использовании в реальной жизни. Так, например, для оптимальной работы процессора могут использоваться онлайн алгоритмы для составления расписания работ, чтобы параллельные вычисления происходили быстрее.
Однако, разбор математической "подноготной" не было моей главной целью в статье. Главным образом, я хотел наглядно продемонстрировать, какие подходы можно использовать, чтобы значительно упростить себе жизнь =)
Читайте также
Источники
- Ravi Kumar, Manish Purohit, Zoya Svitkina "Improving Online Algorithms via ML Predictions"
- Chvatal V. "A greedy heuristic for the set covering problem"
