Минимальная совокупная установленная сумма

Рассмотрим эту проблему: учитывая список конечных множеств, найдите порядок который минимизирует .$s_1, s_2, s_3, \ldots$$|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$

Есть ли известные алгоритмы для этого? В чем его сложность? Я еще не смог придумать эффективный оптимальный алгоритм, но он явно не в NP-Hard.

Эта проблема на самом деле связана с проблемой планирования, известной как «Планирование с ограничением по приоритету для минимизации взвешенного времени завершения». Проблема заключается в следующем: при заданном наборе заданий, где каждое задание имеет время обработки (p) и вес (w), а для заданий определяется график приоритета. Цель состоит в том, чтобы запланировать задания на одном компьютере (без упреждающего действия) так, чтобы ограничения приоритетов были определены, а сумма взвешенного времени выполнения была минимизирована. Задача NP-трудна, и 2-аппроксимация известна.

Сокращение от задачи минимальной кумулятивной суммы до задачи планирования с ограничением по приоритетности: для каждого элемента создайте задание с p = 1, w = 0. Также для каждого набора создайте задание с p = 0, w = 1. Создайте граф приоритета так, чтобы если элемент , то должны быть запланированы , прежде чем . Я думаю, что этот особый случай проблемы планирования также NP-сложен.$e \in S$$e$$S$

Смотрите следующие ссылки,

1) http://www.win.tue.nl/~gwoegi/papers/precsum.pdf

2) http://web.engr.illinois.edu/~chekuri/papers/dam_sched.ps

Шалмоли Гупта уже объяснил, что основной проблемой является NP-Hard, поэтому я решил выяснить, разрешимы ли какие-либо особые случаи на полиномиальной основе. В конце концов, я нашел решение для частного случая множеств, которые представляют дерево, или, в более общем случае, ряд параллельного порядка путем включения подмножеств со всеми несопоставимыми множествами.

Одно свойство, которое делает вещи проще, - это если список множеств закрыт пересечением. Если , то существует оптимальный порядок, в котором s 1 предшествует s 2 . Мы можем предположить WLOG, что оптимальный порядок является линейным расширением частичного порядка, заданного включением подмножества.$s_1 \subseteq s_2$$s_1$$s_2$

Поскольку все подмножества набора появляются перед ним в порядке, это означает, что сумма, добавленная к текущей сумме данным набором, является фиксированной, независимо от того, где она появляется. Если список множеств, то дополнительные расходы из набора является количество элементов в х, которые не являются в любом подмножестве с , который появляется в S . Если один и тот же набор встречается несколько раз в S , мы можем произвольно выбрать один, чтобы идти первым, и пусть остальные будут стоить 0.$S$$S$$S$

Это означает, что эта проблема эквивалентна проблеме минимального взвешенного времени завершения при планировании одной машины с ограничениями приоритета. В этой задаче, учитывая набор заданий с весами и временами t j и частичный порядок заданий P , мы хотим найти порядок заданий, который минимизирует общее время выполнения, т.е.$w_j$$t_j$$P$

$\sum_{i=1}^{n} w_{j_i} \left(\sum_{k=1}^{i} t_{j_k}\right)$

при условии очередности . Проблема минимального совокупного набора с закрытыми множествами пересечений может быть превращена в это путем создания задания для каждого набора, где каждое задание имеет вес 1, время, равное добавочной стоимости, определенной выше, и P - порядок, заданный включением подмножества.$P$$P$

Как оказалось, эта проблема является NP-Hard для общего также. Тем не менее, некоторые специальные формы P могут быть решены за полиномиальное время.$P$$P$

Эта статья дает алгоритм для случая параллельных рядов P (который также включает в себя важный случай деревьев). К сожалению, я не смог получить доступ к этой статье, поэтому я решил попытаться изобрести ее самостоятельно. Вот что я придумал.$O(nlogn)$$P$

Для решения этой проблемы требуется несколько наблюдений.

Во-первых, при отсутствии каких-либо ограничений приоритета оптимальным решением будет просто отсортировать задания в порядке увеличения . Для простоты я буду ссылаться на это как на значение задания, сокращенноv(j). Обратите внимание, что, поскольку сортировка являетсяO(nlogn), невозможно сделать лучше, чем эта сложность.$\frac{t_j}{w_j}$$v(j)$$O(nlogn)$

Правило 1 Пусть и b такие задания, что a < b ∈ P и b покрывает a. Если v ( a ) < v ( b ) , то мы можем отбросить ограничение a < b, не влияя на оптимальное упорядочение или объективное значение.$a$$b$$a < b \in P$$v(a) < v(b)$$a < b$

Предположим, что стоит перед a в оптимальном порядке релаксированной задачи. Поскольку b изначально охватывало a, это означает, что все задания между b и a в новом порядке несопоставимы с a и b. Но поскольку b имеет более высокое значение, чем a, мы можем уменьшить объективное значение, поменяв местами b и a, противоречие.$b$$a$

Аналогично, мы можем снять ограничение в случае, когда если мы обеспечим, чтобы после сортировки по значению мы разорвали связи, обращаясь к отношениям предшествования исходной (упрощенной) задачи. Это гарантирует, что оптимальное решение, найденное для расслабленной задачи, является также оптимальным решением исходной задачи.$v(a) = v(b)$

Поэтому всякий раз, когда b покрывает a и , мы можем упростить задачу, отбросив ограничение a < b .$v(a) \leq v(b)$$a < b$

Правило 2 Предположим, что мы знаем, что b следует сразу после a в оптимальном решении. Мы можем объединить a и b в новый узел c с и t c = t a + t b , одновременно сжимая poset P соответствующим образом.$w_c = w_a + w_b$$t_c = t_a + t_b$$P$

Оптимальное объективное значение новой задачи отличается на постоянную от исходного объективного значения (в частности, ), однако эта константа не зависит от упорядочения и, следовательно, на оптимальное упорядочение не влияет. Мы можем восстановить оптимальное решение старой проблемы путем принятия оптимального решения новой задачи и замены гр с в б .$w_at_b$$c$$ab$

Правило 3 Предположим, что в оптимальном решении экземпляра задачи следует непосредственно перед b и v ( a ) > v ( b ) . Теперь предположим, что мы создаем более крупный экземпляр задачи, добавляя новые задания с новым poset, сформированным из серии или параллельной композиции с оригиналом. Всегда найдется оптимальное решение для более крупной проблемы, когда a предшествует b .$a$$b$$v(a) > v(b)$$a$$b$

Предположим иначе. Пусть оптимальное решение содержит . Поскольку P был образован последовательным параллельным составом, мы знаем, что все x i s несопоставимы с a и b . Объедините все узлы x i в новый узел x ′, используя правило 2. Теперь рассмотрим v ( x ′ ) . Если v ( х ' ) ≤ об ( в ) , то мы можем своп$a, x_1, x_2, \ldots, b$$P$$x_i$$a$$b$$x_i$$x'$$v(x')$$v(x') \leq v(a)$ ибез увеличения значения целевого. Аналогично, если V ( х ' ) ≥ v ( б ) , можно поменять местами х ' и б . Следовательно, v ( a ) < v ( x ' ) < v ( b ) . Но v ( a ) > v ( b ) , противоречие.$x'$$a$$v(x') \geq v(b)$$x'$$b$$v(a) < v(x') < v(b)$$v(a) > v(b)$

Используя правило 2 и правило 3, мы уже можем получить простой, но неоптимальный алгоритм . Поскольку P - это параллельный порядок рядов, предположим, что входные данные содержат древовидное представление P, где каждый узел представляет композицию серии или параллельную композицию, а листья - это отдельные задания. Мы можем найти оптимальное решение с обходом дерева по предварительному порядку, сохранив инвариант, что оптимальным решением для каждой подзадачи является цепочка в порядке возрастания значения.$O(n^2)$$P$$P$

Предположим, что - последовательная композиция подзадач с позами P 1 и P 2 . Пусть оптимальные решения имеют порядок C 1 и C 2 . Оптимальным решением P является, очевидно, объединение этих цепей. Однако возможно, что первое задание в C 2 имеет более низкое значение, чем последнее задание в C 1 . Чтобы сохранить инвариант, что решение представляет собой отсортированную цепочку, мы используем правило 3 + правило 2 для объединения конечных точек, пока они не находятся в отсортированном порядке.$P$$P_1$$P_2$$C_1$$C_2$$P$$C_2$$C_1$

Если вместо этого является параллельной композицией, мы просто берем отсортированные цепочки S 1 и S 2 и объединяем их в новую отсортированную цепочку. Благодаря инварианту это действительно.$P$$S_1$$S_2$

К сожалению, этот алгоритм . Чтобы получить алгоритм O ( n l o g n ) , нам нужно лениво вычислять цепочки, используя правило 1.$O(n^2)$$O(nlogn)$

В частности, если подзадача содержит только узлы, где ограничения приоритета совпадают с порядком значений, то мы можем полностью забыть ограничения приоритета и смотреть только на значения. Это обеспечивается тем же инвариантом, который гарантировал, что решения отсортированы по цепочкам в предыдущем алгоритме.

Вместо того, чтобы вычислять отсортированную цепочку для каждой подзадачи, мы представляем оптимальное решение для подзадачи в виде пары кучи Фибоначчи, одной кучи min и одной кучи max, каждая из которых содержит все задания в подзадаче. Это означает, что мы можем выскочить из минимального или максимального элемента решения за логарифмическое время.

Как и прежде, мы делаем обход предзаказа. Где - состав последовательностей, мы изучаем максимальное задание первой пары кучи и минимальное задание второй пары кучи. Если их значения не в порядке, мы извлекаем их и объединяем их, используя правило 2 и 3. Затем мы сравниваем вновь созданное задание с новыми конечными точками и продолжаем выталкивать и объединять, пока они не в порядке. Как только конечные точки больше не будут иметь значения не по порядку, мы можем смело забыть ограничение приоритета серии благодаря правилу 1. Затем мы просто помещаем вновь созданные задания, если они есть, в кучу, затем объединяем кучи, чтобы создать пару кучи, представляющую решение к P сам.$P$$P$

Для параллельной композиции мы просто объединяем пары кучи. Новая минимальная куча - это объединение минимальной кучи из каждой подзадачи, а также с максимальной кучей. Обратите внимание, что кучи Фибоначчи можно объединять в постоянное время.

Как только у нас есть пара кучи, представляющая решение всей проблемы, мы можем найти фактическое упорядочение решения, выталкивая минимальную кучу, пока она не станет пустой. После этого мы отменяем все подстановки правила 2, чтобы получить решение исходной задачи.

$O(nlogn)$