Размер задачи
Давайте сначала рассмотрим наихудший случай:
У вас есть 10 столбцов и 5 (полных) строк на столбец.Должно быть понятно, что вы сможете получить (с соответствующим количеством населения для каждого места) до 5 ^ 10 ≅ 10 ^ 6 разных результатов (пространство решения).
Например, следующая матрица даст вам наихудший случай для 3 столбцов:
| 1 10 100 |
| 2 20 200 |
| 3 30 300 |
| 4 40 400 |
| 5 50 500 |
, что приведет к 5 ^ 3 = 125 различным результатам. Каждый результат имеет вид {a 1 a 2 a 3 } с i ∈ {1,5}
Довольно легко показать, что такая матрица всегда будет существовать для любого числа n столбцов.
Теперь, чтобы получить каждый числовой результат, вы будетенужно сделать n-1 сумм, в сумме получим размер задачи O (n 5 ^ n).Итак, это наихудший случай, и я думаю, что с этим ничего не поделаешь, потому что, чтобы узнать возможные результаты, вам НУЖНО эффективно выполнять суммы.
Больше доброкачественных воплощений:
Сложность проблемы можно обрезать двумя способами:
- Меньше чисел (т. Е. Не все столбцыfull)
- Повторные результаты (т. е. несколько частичных сумм дают одинаковый результат, и вы можете объединить их в одном потоке).Многое в этом позже.
Давайте рассмотрим упрощенный пример последующего с двумя строками:
| 7 6 100 |
| 3 4 200 |
| 1 2 200 |
на первый взгляд вам нужно будет сделать 2 3 ^ 3 суммы.Но это не настоящий случай.При сложении первого столбца вы не получите ожидаемых 9 различных результатов, а только 6 ({13,11,9,7,5,3}).
Так что вам не нужно нести свои девятьрезультаты до третьего столбца, но только 6.
Конечно, это происходит за счет удаления повторяющихся чисел из списка.«Удаление повторяющихся целочисленных элементов» было опубликовано ранее в SO , и я не буду повторять здесь обсуждение, а просто приведу ссылку на то, что выполнение слияния O (m log m) в размере списка (m) будетудалить дубликаты.Если вы хотите что-то проще, подойдет двойной цикл O (m ^ 2).
В любом случае, я не буду пытаться вычислить размер (средней) проблемы таким образом по нескольким причинам.Одним из них является то, что «m» в сортировке слияния - это не размер проблемы, а размер вектора результатов после сложения любых двух столбцов, и эта операция повторяется (n-1) раз ...и я действительно не хочу делать математику :(. Другая причина в том, что, когда я реализовал алгоритм, мы сможем использовать некоторые экспериментальные результаты и избавить нас от моих, безусловно, утраченных теоретических соображений.
Алгоритм
Из того, что мы сказали ранее, становится ясно, что мы должны оптимизировать для доброкачественных случаев, поскольку наихудший случай - потерянный.
Для этого нам нужно использовать списки (или переменныеdim векторы или что-то еще, что может эмулировать их) для столбцов и выполнять слияние после добавления каждого столбца.
Слияние может быть заменено несколькими другими алгоритмами (такими как вставка в BTree) без изменения результатов.
Таким образом, алгоритм (процедурный псевдокод) выглядит примерно так:
Set result_vector to Column 1
For column i in (2 to n-1)
Remove repeated integers in the result_vector
Add every element of result_vector to every element of column i+1
giving a new result vector
Next column
Remove repeated integers in the result_vector
Или, как вы просили, рекурсивная версия может работать следующим образом:
function genResVector(a:list, b:list): returns list
local c:list
{
Set c = CartesianProduct (a x b)
Set c = Sum up each element {a[i],b[j]} of c </code>
Drop repeated elements of c
Return(c)
}
function ResursiveAdd(a:matrix, i integer): returns list
{
genResVector[Column i from a, RecursiveAdd[a, i-1]];
}
function ResursiveAdd(a:matrix, i==0 integer): returns list={0}
Реализация алгоритма (рекурсивная)
Я выбираю функциональный язык, я думаю, нет ничего сложного в переводе на любой процедурный.
В нашей программе есть двафункции:
- genResVector, который суммирует два списка, дающих все возможные результаты с удаленными повторяющимися элементами, и
- recursiveAdd, который рекурсивно обрабатывает столбцы матрицы, складывая их все.
recursiveAdd, который рекурсивно складывает все столбцы матрицы.
Код:
genResVector[x__, y__] := (* Header: A function that takes two lists as input *)
Union[ (* remove duplicates from resulting list *)
Apply (* distribute the following function on the lists *)
[Plus, (* "Add" is the function to be distributed *)
Tuples[{x, y}],2] (*generate all combinations of the two lists *)];
recursiveAdd[t_, i_] := genResVector[t[[i]], recursiveAdd[t, i - 1]];
(* Recursive add function *)
recursiveAdd[t_, 0] := {0}; (* With its stop pit *)
Тест
Если мы возьмем ваш пример списка
| 1 1 7 9 1 1 |
| 2 2 5 2 2 |
| 3 3 |
| 4 |
| 5 |
и запустим программу, результат будет:
{11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27}
Максимум и минимум очень легко проверить, так как они соответствуют минимальномуили Макс из каждого столбца.
Некоторые интересные результаты
Давайте рассмотрим, что происходит, когда числа в каждой позиции матрицы ограничены.Для этого мы возьмем полную (10 x 5) матрицу и заполним ее Random Integers .
В крайнем случае, когда целые числа являются только нулями или единицами, мы можем ожидать две вещи:
- Очень маленький набор результатов
- Быстрое выполнение, так какбудет много повторяющихся промежуточных результатов
Если мы увеличим Range наших случайных целых чисел, мы можем ожидать увеличения наборов результатов и времени выполнения.
Эксперимент 1: матрица 5x10, заполненная случайными целыми числами различного диапазона
Достаточно ясно, что для набора результатов, близкого к максимальному размеру набора результатов (5 ^ 10 × 10 ^ 6), время вычисления и «Количество! = Результатов» имеют асимптоту.Тот факт, что мы видим увеличение функций, просто означает, что мы все еще далеки от этой точки.
Мораль: чем меньше ваши элементы, тем больше у вас шансов получить его быстро.Это потому, что вы, вероятно, будете иметь много повторений!
Обратите внимание, что наше МАКСИМАЛЬНОЕ время вычисления близко к 20 с для наихудшего протестированного случая
Эксперимент 2: Оптимизации, которые не
Имея много доступной памяти, мы можем вычислить методом грубой силы, не удаляя повторяющиеся результаты.
Результат интересный ... 10,6 сек! ... Подожди!Что случилось ?Наш маленький трюк «удалить повторяющиеся целые числа» съедает много времени, и когда не так много результатов для удаления, нет выгоды, но он теряет попытки избавиться от повторений.
Номы можем получить много преимуществ от оптимизации, когда числа Max в матрице значительно меньше 5 10 ^ 5.Помните, что я выполняю эти тесты с полностью загруженной матрицей 5x10.
Мораль этого эксперимента такова: алгоритм повторного целочисленного удаления является критическим.
HTH!
PS: У меня есть еще несколько экспериментов, если у меня будет время их редактировать.