|
|
| (не показаны 2 промежуточные версии этого же участника) |
| Строка 22: |
Строка 22: |
| | Hint: Можно через «Рюкзак-выполнимость» или «SUBSET-SUM» | | Hint: Можно через «Рюкзак-выполнимость» или «SUBSET-SUM» |
| | | | |
| − | [[Category:Задачи для желающих улучшить оценку]] <br> | + | [[Категория:Нерешенные задачи]] |
| − | решение, предложенное Дыкало Андреем
| + | [[Категория:Теоретические задачи]] |
| − | | + | |
| − | Как известно, задача «разбиения» на два равных по весу множества NP-полная. Возможность сведения задачи «разбиения» к задаче «мультипотоковое расписание», сформулированной в условии, означает NP-полноту второй задачи.
| + | |
| − | | + | |
| − | Сведение:
| + | |
| − | | + | |
| − | Пусть на входе задачи «разбиение» мы имеем n-натуральных чисел, интерпретируемых как веса предметов: A={a(1),a(2),..,a(n)}.
| + | |
| − | | + | |
| − | Обозначение: C=0.5 * [<big>Σ</big><sub>i</sub> {a(i) + (a(i)+1 mod 2)} + (<big>Σ</big><sub>i</sub> {a(i) + (a(i)+1 mod 2)} + 1 mod 2)]. (Четное число)
| + | |
| − | | + | |
| − | Для каждого i-ого предмета составим систему ограничений, i из {1,2,3,..,n}:
| + | |
| − | | + | |
| − | начать_не_раньше(i) = 1;
| + | |
| − | | + | |
| − | закончить_не_позже(i) = C;
| + | |
| − | | + | |
| − | размер_фильма(i) = a(i) + (a(i)+1 mod 2); (Если четное, то прибавить 1, иначе - прибавить 0.)
| + | |
| − | | + | |
| − | Далее, если <big>Σ</big><sub>i</sub> {a(i) + (a(i)+1 mod 2)} - нечетная, то добавим еще один фильм размера 1.
| + | |
| − | | + | |
| − | {{remark|[[User:StasFomin|Стас Фомин]] 02:38, 22 December 2011 (MSK): Нет, мы не можем этого делать! Прочитайте внимательно условие — мы ограничиваем только ширину всего канала, мы не имеем права в постановке задач ограничивать пропускную способность для каждой отдельной закачки! Это решатель задачи о закачках нам выдает полосы для каждой задачи!}}
| + | |
| − | | + | |
| − | {{remark|[[User:maintwister|Дыкало Андрей]] 22:32, 22 December 2011 (MSK): Окей, переформулирую вход и "пересведу" задачу. Полагаю, что закачиваться могут несколько фалов одновременно с ограничением Σширина_канала(i) не больше МаксКанал в любой момент времени.}}
| + | |
| − | | + | |
| − | | + | |
| − | {{remark|1=[[User:StasFomin|Стас Фомин]] 23:19, 22 December 2011 (MSK): «размер_фильма(i) = a(i) + (a(i) mod 2);» — без шансов. Вот задача «A=[2,3,5]» с очевидным решением. У вас это превратится в задачу передать фильмы по [2,4,6] (12 условных гигабайт), за 5 часов × 2 гига/час = 10 гигов, что нерешаемо}}
| + | |
| − | | + | |
| − | {{remark|[[User:maintwister|Дыкало Андрей]] 09:00, 23 December 2011 (MSK): Размеры фильмов были написаны с опечаткой.}}
| + | |
| − | | + | |
| − | {{remark|1=[[User:StasFomin|Стас Фомин]] 13:41, 23 December 2011 (MSK): Все равно не поможет. Берем «A=[2,4,6]» с очевидным решением, вы получаете фильмы [3,5,7], гиг с задачей прокачать суммарных 15 гиг по каналу 2 за шесть часов. — нерешаемо}}.
| + | |
| − | | + | |
| − | {{remark|[[User:maintwister|Дыкало Андрей]] 15:00, 23 December 2011 (MSK): Решение исправлено. Изменилось определение не только количество фильмов, но и параметр C}}
| + | |
| − | | + | |
| − | | + | |
| − | {{remark|1=[[User:StasFomin|Стас Фомин]] 01:47, 29 December 2011 (MSK):
| + | |
| − | Определение
| + | |
| − | C=0.5 * [Σi {a(i) + (a(i)+1 mod 2)} + (Σi {a(i) + (a(i)+1 mod 2)} + 1 mod 2)]
| + | |
| − | | + | |
| − | вынесло мне мозг, но насколько я понял, для
| + | |
| − | входа 4,6,8,2 мы получим [5,7,9,3], а С=½*(12+16)=14. ???
| + | |
| − | }}
| + | |
| − | {{remark|[[User:maintwister|Дыкало Андрей]] 17:25, 29 December 2011 (MSK): Правильно. То есть если сумма [Σi {a(i) + (a(i)+1 mod 2)} нечетная, то добавть фильм размера один}}
| + | |
| − | | + | |
| − | Получили условия задачи о расписании. Дополним их заданием «МаксКанал»:
| + | |
| − | | + | |
| − | МаксКанал = 2;
| + | |
| − | | + | |
| − | Таким образом, вход задачи о «разбиении» полиномиально сведен ко входу задачи о расписании, т. к. каждому предмету соответствует O(1) операций формирования условия задачи о расписании.
| + | |
| − | | + | |
| − | Доказательства однозначности ответов:
| + | |
| − | | + | |
| − | Утверждение 1: Если расписание существует, то ни одна из загрузок не осуществляется с шириной_канала = МаксКанал = 2.
| + | |
| − | | + | |
| − | Пусть при сформулированных условиях задачи о расписании нашлось расписание<br> такое, что хотя бы одна загрузка производится с шириной канала 2.<br> Пусть номер этой загрузки 1 (предположил, не умаляя общности). В силу<br> условий преобразования входов задачи все загрузки имеют нечетный размер.<br> На закачку номер 1 выделена ширина 2 и время t(1) >= (a(1) + [a(1)<br> mod 2])/2 + 1. Время на закачки <br> T >= t(1) + ({a(2)+[a(2)+1mod2]}+{a(3)+[a(3)+1mod2]}+...+{a(n)+[a(n)+1mod2]})/2 > C. Таким образом, T>C, но T<=C.<br> Получили противоречие, доказывающее справедливость утверждения.
| + | |
| − | | + | |
| − | Вопрос задачи: существует ли расписание такое, что все загрузки осуществляемы им?
| + | |
| − | | + | |
| − | Или формально с учетом УТВЕРЖДЕНИЯ 1: существует ли разбиение задач на два <br> множества таких, что суммарное время на выполнение каждого множества задач не превосходит С.
| + | |
| − | | + | |
| − | Или аналитически:
| + | |
| − | | + | |
| − | Существует ли S—подмножество весов A, удовлетворяющее условию:
| + | |
| − | max{Σ<sub>S</sub>a{i}, Σ<sub>A/S</sub>a{i}} <= C.
| + | |
| − | | + | |
| − | Утверждение 2: если выполняется max{Σs a{i}, ΣA/S a{i}} <= 0.5 * ΣA a(i), то Σ<sub>S</sub> a{i} = Σ<sub>A/S</sub>a{i}.
| + | |
| − | | + | |
| − | Доказательство:
| + | |
| − | | + | |
| − | x = Σ<sub>s</sub>a{i}, z = Σ<sub>A/S</sub>a{i}, C = 0.5 * Σ<sub>A</sub> a(i), тогда
| + | |
| − | | + | |
| − | z = 2C — x
| + | |
| − | | + | |
| − | неравенство переписывается в виде:
| + | |
| − | | + | |
| − | max{x, 2C-x} <= C
| + | |
| − | оно имеет единственное решение при x = C.
| + | |
| − | | + | |
| − | То есть если решение существует, то существует S и Σs a{i} = ΣA/S a{i}.
| + | |
| − | | + | |
| − | Таким образом, если ответ задачи «расписания» ДА, то и ответ задачи «разбиение» ДА.
| + | |
| − | | + | |
| − | Если же ответ первой «НЕТ», то не существует такого множества S, для которого
| + | |
| − | | + | |
| − | выполняется: Σ<sub>s</sub> a{i} = Σ<sub>A/S</sub> a{i}.
| + | |
| − | | + | |
| − | Ч.Т.Д.
| + | |
Представим распределенный сервис стриминга видеофильмов.
Центральный сервер с полной БД фильмов получает от периферийных кеширующих узлов запросы
на требуемые фильмы и ориентировочные сроки, когда люди собираются их посмотреть.
Однако пропускная способность от сервера с дисками к внешнему миру ограничена, и требуется составить работающее расписание отгрузки фильмов.
И говорит «OK» (или «Паника-Паника!» в противном случае),
если существует такое расписание из n команд отгрузки, соответствующих заданию (1<=i<=n
):