Дорогие программисты-алгоритмисты! Я перезабыл всё что выучил в ВУЗе, и вообще глуповат. Подскажите, о чём думать/куда смотреть в задаче: разместить периодические точки на отрезке, так чтобы они не пересекались (= «этот минутный телеролик должен идти каждые 5 минут, этот каждые 10, этот каждые 8 — в каком порядке их показывать?»). Простое «отсортировать и разложить рекурсивно» работает в простом случае, и бесконечно навсегда в случае если один из роликов положить невозможно (там экспоненциальное, если я правильно понимаю, кол-во вариантов).
То есть это где-то в районе, вероятно, задач замощения — но не вполне. ‎- а меня почему-то забыли
точки? или всё-таки отрезки разной длины? у телероликов два параметра -- длина и требуемая периодичность, или они все минутные? ‎- middle out-of-sight
пока решаем простейший вариант (все ролики строго минутные) ‎- а меня почему-то забыли
а что хочется заполнить? бесконечную прямую? тогда это невозможно, например, если среди периодов роликов есть хотя бы пара взаимно простых, рано или поздно они попадут в один слот. ‎- middle out-of-sight
^ this, но точность периода будет влиять только на расчёты с заказчиком (успели/не успели сделать оговорённое количество показов), поэтому можно ролики впихивать не совсем точно. ‎- сияю как лес
нет, заполнить надо сутки. при этом каждый ролик описан как «показать с 9:00 до 14:00, 5 раз в час». про «можно впихивать не совсем точно» пока не думаем, интересно эээ Алгоритмическое Решение :) ‎- а меня почему-то забыли
(если бы все ролики надо было показывать все сутки, то математику несложно придумать. а вот с этим ограничением «этот только утром, этот только вечером, а этот весь день, а этот с середины утра» и т.д. — начинается чехарда) ‎- а меня почему-то забыли
ранец? (knapsack problem) ‎- BSOD bluez
↑ да по описанию вроде похоже, а какой стороной его сюда натягивать, я что-то не соображу. ‎- а меня почему-то забыли
Такая идея родилась: в общем, можно адаптировать решение задачи с рюкзаком, но тут есть некоторая проблема с отсутствием общей метрики. В задаче с рюкзаком это суммарная ценность, здесь тоже возможно понадобится нечто подобное. Итак, есть у нас дискретный таймлайн разбитый на минуты. (Array[1..n]). Допустим есть три вида роликов: А — каждые 5 минут, В — каждые 8 минут, С — каждые 10 минут. В i-ой ячейке у нас есть список возможностей дойти до этой минуты: например, вариант 1: показать 10 роликов А, 5 роликов В и 3 С. Или 5 А, 4В, 4С. В общем случае мне кажется надо оставлять только топ-20 допустим в каждой ячейке, чтобы не уходить в экспоненту по памяти. Алгоритм следующий: j:=0 to n, смотрим варианты из j-ой ячейки (допустим там есть A5 B7 C3). Дальше в j+5 дописываем вариант A6B7C3 (то бишь показали в j-ом таймслоте ролик A), в j+8 пишем A5B8C3 (показали ролик B), в j+10 пишем A5B7C4 (показали ролик С). Две проблемы с этой идеей: неочевидно как оценить какой из вариантов лучше, тут понадобится система относительных весов. Ну и вторая в том, что из-за того, что мы отсеиваем какие-то из вариантов не глядя их подробно, возможны какие-то вырожденные случаи, когда на самом деле замощение есть, а мы его пропустили из-за нашей эмпирической метрики. По времени у нас сложность получается в районе O(n * m * k), где n длина отрезка, m количество разных видов точек, k количество хранимых вариантов в каждом таймслоте. EDIT: немного подумав, осознал, что надо ещё чуть больше информации хранить, в предыдущем примере вместо j+5-й ячейки, писать в следующие пять, при этом хранить ещё сколько минут мы не можем показывать ролик А. Короче, проще набросать решение будет, чем объяснить. ‎- mark
Интерфейс комментирования в этом вашем френдфиде просто атас. Простите за неровный почерк, как говорится. ‎- mark
https://gist.github.com/markiz/3acfed09f8adf2cc4a635308805e2a54 вот такая идея короче, особо не тестил, мог где-то незначительно ошибиться, в куче мест можно оптимизировать, но в целом вроде работает ‎- mark
@markizko ой, привет! вчитываюсь :) ‎- а меня почему-то забыли
↑↑ да, я что-то такое и делал, кстати. Проблемы возникают, когда для каждого ролика ещё и определяются время начала и конца показа. ‎- а меня почему-то забыли
на самом деле, мне всё время кажется, что должна быть какая-нибудь Формула вместо «перебрать все и подобрать место», но ... ‎- а меня почему-то забыли
Какого рода проблемы? ‎- mark
Что-то у вас knapsack problem решается вдруг полиномиально, когда задачка-то вообще NP-complete. Как я понимаю, https://en.wikipedia.org/wiki/Knapsack_problem#Solving уже прочитано? ‎- 9000
@markizko ща покажу своё решение (и тестовые данные) ‎- а меня почему-то забыли
https://gist.github.com/zverok/d11d4c89fe76de1e28e47a06aeaf4bf2 — вот там всё «решается» (= не уходит в бесконечный цикл), но некоторые из вариантов — позорно долго; мне всё кажется, там как-то можно _посчитать_ «возможно положить/невозможно положить» более Научно. ‎- а меня почему-то забыли
@9000 "The O(nW) complexity does not contradict the fact that the knapsack problem is NP-complete, since W, unlike n, is not polynomial in the length of the input to the problem. The length of the W input to the problem is proportional to the number of bits in W, log W, not to W itself." ‎- mark
@markizko: I meant the «По времени у нас сложность получается в районе O(n * m * k), где n длина отрезка, m количество разных видов точек, k количество хранимых вариантов в каждом таймслоте» fragment. Still looks polynomial to me. ‎- 9000
@9000 n == W из рюкзака ‎- mark
@9000 ну и я сразу оговорился, что это не оптимальный алгоритм, а жадный. Как решить оптимально — не знаю. ‎- mark
Оптимально в смысле укладки — полным перебором, например, сложность вроде как факториальная :) В википедии есть ссылка на квази-полиномиальный приближённый алгоритм, мне кажется, похожий на приведенный вами. Вообще нам же не нужно строго оптимальное решение, нам нужно ограничить ошибку и распределить её по времени поравномернее (такой dithering). Тогда алгоритм может смотреть на историю последних N циклов и разрешать некоторые неопределённости более дёшево, из соображений, что в прошлый раз такой-то ролик крутили чуть чаще его строго оптимальной частоты, в этот раз можно пожертвовать именно им (и отсечь всё дерево выяснения оптимальности этого участка решения). ‎- 9000
@9000 это в общем выглядит разумно, но главная проблема примерно та же: нужно сравнивать два разных варианта размещения и выбрать тот из них, который больше подходит. Например, в одном покажут 5 раз А, 2 раза В и 3 С, а в другом 3А5В4С. Если у нас есть метрика, которую мы можем использовать, то можем оптимизировать по ней. Надо будет друзей-олимпиадников поспамить, мб они чего скажут полезного. ‎- mark
Метрика, кмк, как раз есть: мы знаем идеальные (теоретические, вероятно, недостижимые) частоты показа и знаем статистику предыдущих показов. Можно посмотреть, какой вариант насколько приближает фактические частоты последних показов + этого показа к идеальным (типа среднеквадратичное отклонение). ‎- 9000
Знакомый выдал следующее: «Легко за полином от числа минут в сутках. Двудольный граф: слева пары (ролик, номер слота этого ролика в сутках), справа минуты. Ребро если эта минута в этом интервале. Ну и паросочетание найти)». В первом приближении звучит очень разумно, учитывая, что минут в сутках всего 1440. Только как искать паросочетание он написать забыл, уехав в закат. ‎- mark
Ну паросочетание-то тривиально: https://ru.m.wikipedia.org/wiki/Паросочетание ‎- alf
Кажется, допёр; на паросочетания есть алгоритм куна. Чуть подробнее насчёт того, что слева, а что справа. Справа минуты, от 0 до 1440. Слева tuples вида (ролик, слот). Слот в данном случае определяется так: первые пять минут — это первый пятиминутный слот, вторые пять минут — слот номер два. Заведомо большая часть рёбер будет для нас недоступна, потому что например, (A, 0) -> 1339 не имеет смысла (нулевой слот может быть связан только с первыми пятью минутами справа). ‎- mark

2015-2016 Mokum.place