честное разбиение множества S на k разбиений

Question

Существует множество S, содержащее N целых чисел, каждое со значением 1 <= X <= 10 ^ 6. Проблема состоит в том, чтобы разбить множество S на k разделов. Значение раздела - это сумма элементов, присутствующих в нем. Разделение должно быть выполнено таким образом, чтобы общее значение множества S было справедливо распределено между k разделами. Математическое значение <em>справедливо также должно быть определено (например, цель может состоять в том, чтобы минимизировать стандартное отклонение значений разделов от среднего значения набора S (то есть суммы (S) / к))

например. S = {10, 15, 12, 13, 30, 5}, k = 3

Хорошее разбиение будет {30}, {10, 15}, {12, 13, 5}

Неверное разбиение будет {30, 5}, {10, 15}, {12, 13}

Первый вопрос - математически выразить условие, чтобы один раздел был лучше, чем другой. Второй вопрос - как решить проблему. Проблема в NP-Hard. Есть ли эвристика?

В задаче, которую я пытаюсь решить, N <= (k * logX) ^ 2 и K варьируется от 2 до 7. </p>

=============================================== ===================================

Основываясь на других связанных вопросах SO, есть две разумные функции для оценки распределения:

а) Минимизировать значение раздела с максимальным значением.

Если подумать, это не очень хорошая метрика. Рассмотрим набор {100, 40, 40}, который нужно разделить на три подмножества. Эта метрика не различает следующие два распределения, хотя одно явно лучше другого.

Распределение 1: {100}, {40}, {40} и Распределение 2: {100}, {40, 40}, {}

b) Минимизировать максимум разности любых двух значений в данном разделе, то есть минимизировать max | A-B | для любого А, В

Answer 1

Я думаю, что хорошая метрика будет:

let the result set be s1,s2,...,sk
let MAX be max{sum(si) for each i}
f({s1,...,sk}) = Sigma(MAX-sum(si)) for each i)

верх: идеальное распределение будет всегда 0!
недостаток: если нет идеального решения, лучший результат не даст 0.

жадная эвристика для этой проблемы будет:

sorted<-sort(S) (let's say sorted[0] is the highest)
s1=s2=...=sk= {}
for each x in sorted:
   s <- find_min() (*)
   s.add(x)

где find_min () даетs такое, что sum (s) <= sum (si) для каждого si. </p>

это решение даст f (метрики, определенные выше), такие что f(sol) <= (k-1)*max{S} (отсюда это доказательство для этой границы):

требование : для каждого подмножества s, MAX- sum(s) <= max{S}
доказательство - по индукции: на каждом шаге утверждение верно для временногорешение.
на каждом шаге, пусть MAX будет max {sum (si)} в начале итерации (перед сложением)!

base: the set of subsets at start is {},{},.. MAX=sum(si)=0 for each si. 
step: assume the assumption is true for iteration i, we'll show it is also true for iteration i+1:
let s be the set that x was added to, then MAX-sum(s) <= max{S} (induction assumption).
if sum(s) + x <= MAX: we are done, MAX was not changed.
else: we sorted the elements at start, so x <= max{S}, and thus if s was chosen
   (sum(si) >= sum(s) for each si) and sum(s) + x > MAX then: for each si, sum(si) + x >=
   sum(s) + x, so sum(s)+x - sum(si) <= x <= max{S}. since sum(s)+x will be the MAX next 
   iteration, we are done.

, потому что для каждого набора MAX-sum(si) <= max{S} (и, очевидно, длямаксимальное значение, MAX-sum(si)=0), в целом Sigma(MAX-sum(si)) <= (k-1)*max{S}, как и было обещано.

РЕДАКТИРОВАТЬ:
У меня было немного свободного времени, поэтому я запрограммировал обе эвристики, предложенные мной ипо @Akhil, и обе метрики, во-первых, оба результата являются окончательными (в соответствии с парным t-тестом Wilcoxon ), но что лучше, определяется тем, какую метрику вы выбираете, как ни странно, алгоритмкоторый попытался минимизировать f () (@ Akhil`s), набрал меньше для этого же f, но выше для второй метрики.

Answer 2

Пусть метрика сводит к минимуму max (sum (si) - sum (sj)), где si и sj - любые два подмножества в результирующем разбиении множества S.

Допустим, у нас есть распределение D, и нам нужно включить еще один элемент x в распределение D. Добавьте его к подмножеству s так, чтобы указанная выше метрика была минимизирована.

Не могу доказать никаких границ, но интуиция говорит, что это даст хорошее приближение к оптимальному? Кто-нибудь хорошо доказывает границы?

Answer 3

Одной эвристикой было бы распределение больших весов между сумками как можно более равномерно, оставляя достаточно меньшие веса, чтобы у вас осталась подзадача с большим количеством степеней свободы.Повторите в подпроблемах при необходимости.Эта эвристика предполагает, что ваше распределение не слишком геометрическое, например, {1000} and {100, 10, 1}, и слегка предполагает, что ваша штрафная функция будет штрафовать ноль-назначения или очень большие выбросы.

Например:

distributeFairly(numbers, bins):
    distributeFairlySubproblem(numbers, bins):
        n = len(numbers)
        numElementsToDefer = min(-n//3,20*k)  # modify as appropriate, e.g. to avoid len(toPlace)<len(toDefer)

        toDefer = numbers[-numElementsToDefer:]
        toPlace = numbers[:-numElementsToDefer]

        newBins = shoveThemIn(toPlace, copy(bins))
        return distributeFairlySubproblem(toDefer, newBins)

    initialGuess = distributeFairlySubproblem(sorted(numbers,reverse=True), [[]]*k)
    return anneal(initialGuess)