Алгоритм разбиения массива на P-подмассивы сбалансированной суммы

Ответ 1

Рабочий код ниже (я использовал php-язык). Этот код сам определяет количество деталей;

$main = array(2,4,6,1,6,3,2,3,4,3,4,1,4,7,3,1,2,1,3,4,1,7,2,4,1,2,3,1,1,1,1,4,5,7,8,9,8,0);
$pa=0;
for($i=0;$i < count($main); $i++){
$p[]= $main[$i];
if(abs(15 - array_sum($p)) < abs(15 - (array_sum($p)+$main[$i+1])))
{
$pa=$pa+1;
$pi[] = $i+1;
$pc =  count($pi);

$ba = $pi[$pc-2] ;

$part[$pa] = array_slice( $main,  $ba, count($p));
unset($p);
}
}
print_r($part);
for($s=1;$s<count($part);$s++){
echo '<br>';
echo array_sum($part[$s]);
}

код выводит частичные суммы, как показано ниже

13
14
16
14
15
15
17

Ответ 2

Во-первых, давайте формализовать вашу проблему оптимизации, указав ввод, вывод и меру для каждого возможного решения (надеюсь, это вас интересует):

Учитывая массив A положительных целых чисел и положительное целое число P, разделите массив A на P неперекрывающихся подмассивов таким образом, чтобы разница между суммой каждого подмассива и совершенной суммой подмассивов (сумма (A)/P ) минимальна.

Вход: массив A положительных целых чисел; P - положительное целое число. Выход: массив SA неотрицательных целых чисел P, представляющих длину каждого подматрицы A, где сумма этих длин субарарей равна длине A.
Измерение: abs (sum (sa) -sum (A)/P) минимально для каждого sa ∈ {sa | sa = (A _i,..., A _{я + SA j}) для я = (Σ SA _j), j от 0 до P-1}.

Ввод и вывод определяют набор допустимых решений. Мера определяет меру для сравнения нескольких действительных решений. И так как искали решение с наименьшей разницей в идеальном решении (проблема минимизации), измерение также должно быть минимальным.

С помощью этой информации довольно легко реализовать функцию measure (здесь, на Python):

def measure(a, sa):
    sigma = sum(a)/len(sa)
    diff = 0
    i = 0
    for j in xrange(0, len(sa)):
        diff += abs(sum(a[i:i+sa[j]])-sigma)
        i += sa[j]
    return diff

print measure([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], [3,4,4,5]) # prints 8

Теперь найти оптимальное решение немного сложнее.

Мы можем использовать алгоритм Backtracking для поиска действительных решений и использовать функцию измерения для оценки их. Мы в основном стараемся использовать все возможные комбинации неотрицательных целых чисел P, которые суммируются до длины (A), чтобы представить все возможные допустимые решения. Хотя это гарантирует, что вы не пропустите правильное решение, это в основном подход грубой силы с выгодой, что мы можем опустить некоторые ветки, которые не могут быть лучше, чем наше, но лучшее решение. Например. в приведенном выше примере нам не нужно было бы тестировать решения с помощью [9,...] (меру > 38), если у нас уже есть решение с мерой ≤ 38.

Следуя рисунку псевдокода из Википедии, наша функция bt выглядит следующим образом:

def bt(c):
    global P, optimum, optimum_diff
    if reject(P,c):
        return
    if accept(P,c):
        print "%r with %d" % (c, measure(P,c))
        if measure(P,c) < optimum_diff:
            optimum = c
            optimum_diff = measure(P,c)
        return
    s = first(P,c)
    while s is not None:
        bt(list(s))
        s = next(P,s)

Глобальные переменные P, optimum и optimum_diff представляют экземпляр проблемы, содержащий значения для A, P и сигмы, а также оптимальное решение и его меру:

class MinimalSumOfSubArraySumsProblem:
    def __init__(self, a, p):
        self.a = a
        self.p = p
        self.sigma = sum(a)/p

Далее мы задаем функции reject и accept, которые достаточно просты:

def reject(P,c):
    return optimum_diff < measure(P,c)
def accept(P,c):
    return None not in c

Это просто отвергает любого кандидата, чья мера уже больше, чем наше, но оптимальное решение. И принимали какое-либо действительное решение.

Функция measure также слегка изменена из-за того, что c теперь может содержать значения None:

def measure(P, c):
    diff = 0
    i = 0
    for j in xrange(0, P.p):
        if c[j] is None:
            break;
        diff += abs(sum(P.a[i:i+c[j]])-P.sigma)
        i += c[j]
    return diff

Остальные две функции first и next немного сложнее:

def first(P,c):
    t = 0
    is_complete = True
    for i in xrange(0, len(c)):
        if c[i] is None:
            if i+1 < len(c):
                c[i] = 0
            else:
                c[i] = len(P.a) - t
            is_complete = False
            break;
        else:
            t += c[i]
    if is_complete:
        return None
    return c

def next(P,s):
    t = 0
    for i in xrange(0, len(s)):
        t += s[i]
        if i+1 >= len(s) or s[i+1] is None:
            if t+1 > len(P.a):
                return None
            else:
                s[i] += 1
            return s

В принципе, first либо заменяет следующее значение None в списке либо 0, если это не последнее значение в списке, либо остаток для представления действительного решения (небольшая оптимизация здесь), если его последнее значение в списке или возвращает None, если в списке нет значения None. next просто увеличивает самое правое целое на единицу или возвращает None, если приращение будет нарушать общий предел.

Теперь вам нужно создать экземпляр проблемы, инициализировать глобальные переменные и вызвать bt с корнем:

P = MinimalSumOfSubArraySumsProblem([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], 4)
optimum = None
optimum_diff = float("inf")
bt([None]*P.p)

Ответ 3

Если я не ошибаюсь здесь, еще один подход - это динамическое программирование.

Вы можете определить P [pos, n] как минимально возможное "штраф", накопленное до позиции pos, если были созданы n подмассивов. Очевидно, существует некоторая позиция pos 'такая, что

P [pos ', n-1] + штраф (pos', pos) = P [pos, n]

Вы можете просто свернуть значение по pos '= 1..pos.

Наивная реализация будет выполняться в O (N ^ 2 * M), где N - размер исходного массива и M - количество делений.

Ответ 4

Мне интересно, будет ли работать следующее:

Перейдите влево, как только sum > sigma, перейдете на две части, одна из которых включает значение, которое его перетаскивает, а другое - нет. Рекурсивно обрабатывать данные вправо с помощью rightSum = totalSum-leftSum и rightP = P-1.

Итак, в начале, sum = 60

2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1

Тогда для 2 4 6 7, sum = 19 > sigma, поэтому разделите на:

2 4 6     7 6 3 3 3 4 3 4 4 4 3 3 1

2 4 6 7     6 3 3 3 4 3 4 4 4 3 3 1

Затем мы обрабатываем 7 6 3 3 3 4 3 4 4 4 3 3 1 и 6 3 3 3 4 3 4 4 4 3 3 1 с помощью P = 4-1 и sum = 60-12 и sum = 60-19 соответственно.

В результате, я думаю, O (P * n).

Это может быть проблема, когда 1 или 2 значения на сегодняшний день являются самыми большими, но для любого значения >= сигма мы можем, вероятно, просто поместить это в свой собственный раздел (предварительная обработка массива, чтобы найти их, может быть лучшей идеей (и соответственно уменьшить сумму)).

Если это сработает, оно должно, мы надеемся, минимизировать ошибку суммы квадрата (или близко к ней), которая кажется желаемой мерой.

Ответ 5

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

sum=CalculateSum(vector)
Read P
sigma=sum/P
initialize P vectors, with names vector_partition[i], i=1..P
list_vector initialize a list what pointed this P vectors
initialize a diferences_vector with dimension of P
//that can easy visualize like a vector of vectors
//construct a non-recursive backtracking algorithm
function Deviation(vector) //function for calculate deviation of elements from a vector
{
  dev=0
  for i=0 to Size(vector)-1 do
  dev+=|vector[i+1]-vector[i]|
  return dev 
}
iteration=0
//fix some maximum number of iteration for while loop
Read max_iteration
//as the number of iterations will be higher the more it will get  
//a more accurate solution
while(!IsEmpty(vector))
{   
   for i=1 to Size(list_vector) do
   {
       if(IsEmpty(vector)) break from while loop
       initial_deviation=Deviation(list_vector[i])
       el=SelectElement(vector) //you can implement that function using a randomized   
                               //choice of element
       difference_vector[i]=|sigma-CalculateSum(list_vector[i])|
       PutOnBackVector(vector_list[i], el)
       if(initial_deviation>Deviation(difference_vector))
          ExtractFromBackVectorAndPutOnSecondVector(list_vector, vector)
    }
    iteration++
    //prevent to enter in some infinite loop
   if (iteration>max_iteration) break from while loop    

} Вы можете изменить это, добавив сначала, если приращение какого-либо кода с суммой вычисленного отклонения.     aditional_amount = 0     Итерация = 0     в то время как     {        ...        если (initial_deviation > Отклонение (difference_vector) + additional_amount)            ExtractFromBackVectorAndPutOnSecondVector (list_vector, vector)        если (итерация > max_iteration)        {           Итерация = 0           aditional_amout + = 1/some_constant        }      итерация ++      // удалить второй, если из первой версии     }

Ответ 6

Вы можете использовать алгоритм Max Flow.

Ответ 7

Ваша проблема очень похожа на, или же, как и минимальная проблема планирования расписания, в зависимости от того, как вы определяете свою цель. В случае, если вы хотите минимизировать максимум |sum_i - sigma|, это именно та проблема.

Как указано в статье в Википедии, эта проблема NP-полная для p > 2. Graham алгоритм планирования списка оптимален для p <= 3 и обеспечивает коэффициент приближения 2 - 1/p. Вы можете проверить статью в Википедии для других алгоритмов и их приближения.

Все алгоритмы, приведенные на этой странице, либо решаются для другой цели, неправильной/субоптимальной, либо могут быть использованы для решения любой проблемы в NP:)

Ответ 8

Это очень похоже на случай одномерной проблемы упаковки bin, см. http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml. В связанной книге "Руководство по разработке алгоритмов" , Skienna предлагает подход, снижающий первый подход. То есть определите размер вашего бункера (mean = sum/N), а затем выделите самый большой оставшийся объект в первый ящик, в котором есть место для него. Вы либо доходите до точки, где вам нужно начать заполнять бункер, или если вам повезет, вы получите идеальную форму. Как заявляет Лэсена, "первое снижение имеет интуитивное обращение к нему, поскольку мы сначала собираем громоздкие объекты и надеемся, что маленькие объекты могут заполнить трещины" .

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

Ответ 9

Я недавно нуждался в этом и сделал следующее:

• создать начальный массив массивов sub-массивов длины, подсчитанных подсчетами вспомогательных массивов. вспомогательные массивы также должны иметь свойство суммы. т.е. [[sum:0],[sum:0]...[sum:0]]
• сортировать основной массив по убыванию.
• найдите подматрицу с наименьшей суммой и вставьте один элемент из основного массива и увеличьте свойство sum sub arrays на вставленное значение элемента.
• повторите элемент 3 до конца основного массива.
• возвращает массив initial.

Это код в JS.

function groupTasks(tasks,groupCount){
  var  sum = tasks.reduce((p,c) => p+c),
   initial = [...Array(groupCount)].map(sa => (sa = [], sa.sum = 0, sa));
  return tasks.sort((a,b) => b-a)
              .reduce((groups,task) => { var group = groups.reduce((p,c) => p.sum < c.sum ? p : c);
                                         group.push(task);
                                         group.sum += task;
                                         return groups;
                                       },initial);
}

var tasks = [...Array(50)].map(_ => ~~(Math.random()*10)+1), // create an array of 100 random elements among 1 to 10
   result = groupTasks(tasks,7);                             // distribute them into 10 sub arrays with closest sums

console.log("input array:", JSON.stringify(tasks));
console.log(result.map(r=> [JSON.stringify(r),"sum: " + r.sum]));