Проблема: n переменных (x) в сумме составляют константу. x1+x2+..+xn = const, где каждый x может принимать только p (скажем, 5) положительных целых чисел. Мы хотим найти решение, в котором разница между x минимальна, т. е. они распределены наиболее равномерно. Это проблема целочисленного программирования?
длм
Да, это проблема целочисленного программирования. Вы можете написать это как:
minimize |x1 - x2| + |x2 - x3| + ... + |xn-1 - xn|
subject to x1 + x2 + x3 + ... + xn == c,
xi == Ai1*yi1 + Ai2*yi2 + ... + Aip*yip, i=1,...,n,
yi1 + yi2 + ... + yip == 1, i=1,...,n,
yij binary for i=1,...,n j=1,...,p,
xi integer for i=1,...,n,
здесь Aij — известные входные данные, описывающие, какие целые числа может принимать конкретное значение xi. Ниже приведен конкретный пример с 3 переменными (n=3), где каждое xi может принимать одно из двух целых значений (p=2). То есть x1 может быть 1 или 3, x2 может быть 3 или 4, x3 может быть 2 или 3.
minimize |x1 - x2| + |x2 - x3|
subject to x1 + x2 + x3 == 8,
x1 == 1*y11 + 3*y12,
x2 == 3*y21 + 4*y22,
x3 == 2*y31 + 3*y32,
y11 + y12 == 1,
y21 + y22 == 1,
y31 + y32 == 1,
yij binary i=1,2,3 j=1,2
xi integer i=1,2,3
Вы можете переформулировать приведенную выше задачу как MIP (программа смешанных целых чисел), создав новый набор переменных u для представления целевой функции.
minimize u1 + u2 + ... + un
subject to ui >= xi - xi+1, i=1,...,n-1,
ui >= xi+1 - xi, i=1,...,n-1,
x1 + x2 + x3 + ... + xn == c,
xi == Ai1*yi1 + Ai2*yi2 + ... + Aip*yip, i=1,...,n,
yi1 + yi2 + ... + yip == 1, i=1,...,n,
yij binary for i=1,...,n j=1,...,p,
xi integer for i=1,...,n,
ui real for i=1,...,n-1,
Вы можете использовать любой стандартный решатель MIP для решения вышеуказанной проблемы.
Кажется, что это np-полная проблема, на самом деле вам нужно искать все решения, чтобы получить правильное распределение. Может быть, попробовать это
И. Жадный алгоритм
foreach x in xses
if current_sum < desired_sum:
take maximal p for x
else take_minimal p for x
Как вы видите, это не приведет вас к правильному решению, возможно, у вас будет SUM больше, чем DESIRED_SUM.
но после этого вы можете начать оптимизировать свой дистрибутив: теперь у нас есть набор жадно выбранных xses
foreach x:
if current_sum > desired_sum
change taken P to minimal P for x
else
break
это приведет вас к близкому решению
II. Эволюционный алгоритм
Строгое определение вашей проблемы приводит вас к генетическим алгоритмам. Популяции будут векторами фитнес-функции X=[x1,x2,x3,x4...xn], это очевидно (разница между желаемой суммой и вычисленной суммой из X)
просто выполните правильные эволюционные операции над векторами, и это должно привести к оптимизированному решению за короткое время.
Есть ли у вас какие-либо ограничения (или дополнительная информация) на целые числа? Если они не слишком велики, можно реализовать алгоритм, который перебирает все возможные суммы (без выполнения всех комбинаций):
function adds_up_to(xs, N):
sums := {0}
for i from 1 to n:
new_sums := {}
for sum in sums:
for value in values:
new_sums := new_sums U {sum + value}
sums := new_sums
return (N in sums)
(Это просто поиск удовлетворительного решения. Алгоритм должен быть усилен, чтобы справляться с минимизацией различий, что бы это ни значило)
Что касается целевой функции, то это хитрость, когда вы хотите минимизировать разницу между наборами. Простая форма может быть Sum(ABS(Xi-Xj)), где i>j. который можно линеаризовать. Однако, если вы хотите использовать примерный вариант, это станет QIP и потребует немного больше времени для решения.
