Есть задача, которую необходимо решить, но нет особых познаний в области алгоритмов.
Поэтому прошу всех, кто «увидит» решение, или понимает в какую сторону смотреть (что
почитать/изучить), задать мне вектор для мысли.
Описание задачи.
Необходимо ежедневно формировать стек «Предложение — Сегмент» для совершения рассылки.
Сущности
Сегменты адресов (С = {1, 2, ..., n})
Вся база адресов делится на множество сегментов, каждый сегмент состоит из определенного
количества адресов. Допустим: всего в базе 9 млн. адресов, они разделены на 9к сегментов
по 1000 адресов каждый.
Предложения (П = {1, 2, ..., n})
Каждое отправленное письмо содержит в себе какое-то предложение (услуга/товар). По
сути, предложение — это шаблон письма. Допустим мы имеем в данный момент 9 предложений.
Ограничения
Отправка одного предложения может осуществляться с интервалом «не чаще, чем 1 раз
в 3 дня».
Поясню: если сегодня мы совершили рассылку предложения 1 (П1) сегментам с 1го по
100й, то в следующий раз мы можем совершить рассылку по П1 только через 3 дня, не ранее.
По идее каждый день можно рассылать любое количество предложений, но если предложений
9, тогда получается не более 3 предложений.
Отправка одного предложения одному сегменту может осуществляться «не чаще, чем 1
раз в 3 месяца».
Если взять за основу пояснение из предыдущего ограничения, получаем — сегментам с
1 по 100 предложение 1 мы сможем повторно отправить не раньше, чем через 90 дней.
Ежедневный лимит по отправленным письмам — 300 000.
Исходя из того, что в сегменте 1000 адресов, следует, что ежедневно мы можем задействовать
300 сегментов. Следует отметить, что уложится в 300к отправок (±) очень важно, т.е.
превышение или недобор необходимо свести к минимуму.
Каждый день одному сегменту можно отправить только одно предложение.
Т.е. нельзя сегменту 1 отправить несколько разных предложений в один день.
Дополнительные условия/требования
На основе статистики рассылки каждому сегменту и предложению устанавливается определенный
вес (коэффициент эффективности). Стек рассылки на сегодня должен формироваться с учетом
них, т.е. максимально эффективные пары «Сегмент-Предложение» приоритетнее.
Количество предложений и сегментов может меняться (например: получатель отписался
от рассылки; появились новые предложения). Новым сегментам/предложениям дается некая
«фора», т.е. чтобы определить эффективность, их необходимо «обстрелять», поэтому они
должны фигурировать в стеке на ближайшие 3 дня.
Таким образом мы должны каждый день получить стек, подобный этим:
День 1.
С101 … С200: П1
С201 … С300: П2
С301 … С400: П3
День 2.
С401 … С550: П4
С551 … С700: П5
День 3.
…
Это для примера, не стоит от этого отталкиваться.
Помимо формирования самого стека, необходимо также понимать — что будет происходить
при изменении количества предложений/сегментов. Не получится ли так, что рано или поздно
появятся дыры в расписании, т.е. дни, когда стек формировать будет не из чего.
Начал смотреть в сторону теории расписаний, но, есть подозрения, что могу ошибиться.
Ответы
Ответ 1
Я бы использовал Рулетку.
https://en.wikipedia.org/wiki/Fitness_proportionate_selection
В основном этот алгоритм применяется для генетики, чтобы вывести генотипы следующего
поколения на основе наиболее успешных фенотипов, но может применятся и для рассылки
email, если опустить все, что нам не интересно из генетики (скрещивание, например).
Идея такая - у каждого генотипа (сегмент, предложение) есть функция успешности -
Fitness (подходящесть).
Формируем все возможные генотипы (сегмент1, предложение1), (сегмент1, предложениеM),
(сегментN,предложениеM)
Всего таких будет M*N (300*9).
Дальше, для каждого генотипа выводится фенотип по правилам.
Например, есть примерно следующие правила, по порядку:
Аддитивные:
Всем +1
Новый +10
Эффективный +10 (или +какой-то вес).
Не отправлялось данному сегменту без учета предложения X дней: +(X*F) F - экспериментальный
коэффициент. Прибавляем баллов тем, кому давно ничего не отправлялось.
Мультипликативные (множим на 0):
Отправлялось в последние три дня: * 0
Данное предложение данному сегменту отправлялось менее месяца назад: * 0
Например, получаем такие значения:
(1,1) -> 11
(1,2) -> 1
(2,1) -> 21
(2,2) -> 0
Те, кто набрал в итоге 0 отбраковываем.
Теперь рисуем рулетку.
Рулетка размечается так: Fitness каждого фенотипа это кол-во фишек, которые "игрок"
выложил. Фишки раскладываются так, чтобы занять весь круг. На самом деле, мы можем
задать размер круга так, чтобы заведомо точно вместить все фишки.
Если "фишкки" не целочисленные, то считаем что это длина сегмента окружности в пропорции.
Суммируем Fitness всех фенотипов, и получаем (11 + 1 + 21) = 33 - это длина окружности.
1) Кидаем шарик: i = random(1,33)
Например, i = 13
*****************|<- шарик выпал сюда, берем (2,1)
0|*****11****|1|**********21*********|33
Значит, набираем в рассылку (2,1), если ее у же там нет.
Если мы набрали достаточную рассылку (размер успешной популяции, в терминах генетики),
то отсылаем, и ждем день, иначе переходим на 1)
У этого алгоритма есть проблема - он не масштабируется от размера популяции, тоесть
для вычисления куда попал шарик нужно суммировать в среднем N*M/2 элементов (наш размер
популяции).
Это все сворачивается в более эффективный алгоритм, если мы будем не просто шарик
кидать, а продолжать "катить" его:
(1,1) -> 11 11
(1,2) -> 1 12
(2,1) -> 21 33
(круг)
(1,1) -> 11 44
(1,2) -> 1 45
(2,1) -> 21 66
И шарик двигаем каждый раз на случайное число от 1 до K например. K - достоточно
большое, например - максимальный балл, иначе можем набрать некачественную популяцию.
В этом случае алгоритм будет за линейное время работать.
Можно было бы вместо случайных чисел использовать просто сортировку по баллам, и
брать первые 300k, но это грозит тем, что решение будет осциллировать.
Этот алгоритм эффективно будет работать пока число генотипов существенно больше числа
разрешенных рассылок в день, хотя бы вдвое, и если это будет не так, нужно будет как-то
учесть. Иначе шарик на конечном этапе будет кататься "по пустому кругу". Как вариант
- если такая ситуация возникает, то круг переделывается из остатков, и алгоритм запускается
снова.
Чем хорошо такое решение - можно независимо от алгоритма регулировать правила, веса,
коэффициенты и запреты (умножение на ноль).
