请教一个算法模型问题，实在不知道去哪找资料了，这里试试吧

[yml.Matthew]

请教一个算法问题，应用场景是这样的：

有50（n）个数字，[200,600,3902,1221,...2183], 要分成11(x)组，使各组的和与常数4216（必大于50个数字中的任一个）的总差是最小的。

这个的算法模型应该怎么组建……

[Dong HAN]

算法模型：

整数线性规划来建模。

分析：

假设有50个数字，分别是A1, A2, A3, ..., A49, A50

分成11组，因为每个数字只可能属于11组中的其中一组，对于每个数字，我们可以设一个未知数来确定这个数字属于哪一组。

比如对于第一个数字A1，我们可以设如下11个未知数

x1_1, x1_2, x1_3, x1_4, x1_5,x1_6,x1_7,x1_8,x1_9,x1_10,x1_11

这些未知数，只能取值为0或者1。取值为1的时候，代表数字A1属于某一组，取值为0，代表不属于这一组。

因为一个数字只可能属于11个组里面的某一组，那么对应的未知数就为1，剩余的未知数就为0，我们就可以得到一个如下的方程：

x1_1 + x1_2 + x1_3+ x1_4 + x1_5 + x1_6 + x1_7 + x1_8 + x1_9 + x1_10 + x1_11 = 1

因为每个未知数只可能取值0或者1，而且上面只有一个未知数为1，其他都为0，所以最后结果等于1.

照此办理，第二个数字A2，我们设11个未知数x2_1, x2_2, ..., x2_11我们也可以得出如下的方程：

x2_1 + x2_2 + x2_3+ x2_4 + x2_5 + x2_6 + x2_7 + x2_8 + x2_9 + x2_10 + x2_11 = 1

这样，我们能得到50个方程。

然后我们的目标是各组之和与常数4216的总差最小。

因为有11个组，第一组之和的表达式是

S1 = x1_1*A1 + x2_1*A2 + x3_1*A3 + ... + x49_1*A49 + x50_1*A50

第二组之和的表达式是

S2 = x1_2*A1 + x2_2*A2 + x3_2*A3 + ... + x49_2*A49 + x50_2*A50

以此类推，我们可以得到S3, S4, ..., S11

那么每组与4216的差加在一起可以得到总差的表达式为:

F(X) = (S1-4216) + (S2-4216) + (S3-4216) + ... +(S11-4216)

于是我们只要求目标函数最小，也就是：

minimize F(X)

这里的X代表所有的x1_1, x1_2, ...., x50_11的集合,这个集合里面有11*50个变量。

把上面的描述形式化成整数线性优化就是：

1. 目标函数: minimize F(X)

2. 目标函数的限定条件，具体分为如下4大部分:

(第一部分是F(X)的定义)

F(X) = (S1-4216) + (S2-4216) + (S3-4216) + ... +(S11-4216)

(第二部分是S1到S11的11个组的定义,有11个等式)

S1 = x1_1*A1 + x2_1*A2 + x3_1*A3 + ... + x49_1*A49 + x50_1*A50

S2 = x1_2*A1 + x2_2*A2 + x3_2*A3 + ... + x49_2*A49 + x50_2*A50

S3 = x1_3*A1 + .....+x50_3*A50

...

S11 = x1_11*A1 + ... +x50_11*A50

(第三部分是限制每个数字只能属于一个组，有50个等式)

x1_1 + x1_2 + x1_3+ x1_4 + x1_5 + x1_6 + x1_7 + x1_8 + x1_9 + x1_10 + x1_11 = 1

x2_1 + x2_2 + x2_3+ x2_4 + x2_5 + x2_6 + x2_7 + x2_8 + x2_9 + x2_10 + x2_11 = 1

x3_1 + ...... + x2_11 = 1

...

x50_1 + ...... + x50_11 = 1

(第四部分是限制所有未知数x只能取值0或者1,这个是限制未知数只能取整数)

x1_1 = {0,1}

x1_2 = {0,1}

.....

x50_11 = {0,1}

到此，算法建模完毕，你可以用各种线性规划的解析器能解出上述的方程。

具体实现

具体到解出上述目标函数的算法，可以是simplex算法，或者更高级的算法。

这些算法有现成的工具包，比如Matlab的Linear Programming and Mixed-Integer Linear Programming工具包

或者用python，java，各种语言均有实现类似算法的类库，搜一搜integer linear programming就有了。

时间复杂度分析

线性规划是多项式时间复杂度，但是整数线性规划会稍微复杂一点，理论上有一些整数线性规划是NP复杂度，但是可以在多项式复杂度里面给出近似最优解，因为在实际解方程找最优解的时候，未知数x的取值可能在区间[0,1]里面，而不是严格的0或者1，然后最后再近似到0或者1。总体来讲，时间复杂度应该是和未知数的数量呈正比的关系，所以时间复杂度应该是O(n*x),这个n是指n个数字，x指的是分组的数。

总结

几乎所有类似的算法问题都可以用线性规划来解，而且时间复杂度给出的都是最优的：(1)对于本质上是多项式复杂度的问题，总能在多项式时间复杂度内解出来；(2)对于本质上是NP的问题，也能在多项式时间复杂度内给出相当不错的近似解。当然对于有些算法问题，不排除有类似于脑筋急转弯解法。但是线性规划是一种万金油解法，类似于套路，能套几乎所有算法问题。

--

---
您收到此邮件是因为您订阅了Google网上论坛上的“TopLanguage”群组。
要退订此群组并停止接收此群组的电子邮件，请发送电子邮件到pongba+unsubscribe@googlegroups.com。
要查看更多选项，请访问https://groups.google.com/d/optout。

[rain shawn]

好的，谢谢，我先补一补integer linear programming的知识，像x1_1+x2_2+x3_4...这样的情况是不是在建模运算的时候就包括在里面的？

[Tian Guo]

总差是绝对值还是平方差？

[rain shawn]

总差是正数差， sum(4216-group(x))

[Tian Guo]

分组是互斥的？ 

这样的话 总差是恒定的吧，都是线性求和， 没有可优化的地方。

[Dong HAN]

1.总差确实是恒定的值，如果不是绝对值。如果计算绝对值，那目标函数就是
F(X) = |S1-4216| + |S2-4216| + |S3-4216| + ... +|S11-4216|

2. x1_1+x2_2+x3_4...这样的情况在建模运算的时候就已经包含了。

[rain shawn]

分组是互斥的,问题描述有准确的地方，常数4216应该是50个数的总和除以分组数形成的平均数……

[rain shawn]

分组是互斥的,不好意思，问题描述有不准确的地方，常数4216应该是50个数的总和除以分组数形成的50个数字的平均数，总差计算的是绝对值。

在 2017年3月17日 下午10:05，Dong HAN <min...@gmail.com>写道：

[rain shawn]

我在调用python 的 pulp 和 scipy尝试进行计算

[Tian Guo]

还是不清楚你的问题描述。。 听上去是个clustering问题， loss function 不太一样。 很多种算法可以处理。

[rain shawn]

在用scipy进行处理的过程过，scipy的开发人员指出了这类问题在使用abs函数时已经不属于线性问题了，更像是分组优化问题，并且推荐了R语言的一些参考，现在用R语言实现的算法如下：

t <- c(22,8,15,1,2.2,2.3,0.8)

n <- 3

ngroup<- vector("list",n)

arp = function(rt,rn,ngroup){

if(rn==1){

ngroup[[rn]]<-rt

#print(rn)

return(ngroup)

}

ngroup[[rn]]<-sample(rt,sample(seq(length(rt)-rn)),FALSE)

print(ngroup[[rn]])

arp(setdiff(rt,ngroup[[rn]]),rn-1,ngroup)

}

gfun = function(){

tavg <- mean(t)

ngroup <-arp(t,n,ngroup)

gs <- 0

for( g in ngroup){

gs <- gs +(sum(g)-tavg)

}

thisvar <- var(gs)

return(list(group=ngroup,sums=gs,var=thisvar))

}

r<-(length(t)-1)^2

sorts <- replicate(r, gfun(), simplify=FALSE)

wh <- which.min(sapply(sorts, function(x) x$sums))

sorts[[wh]]

只是还有一个问题，就是不知道最大分组可能性该是 r<-(length(t)-1)^2 还是 r<-(length(t)-n)^(length(t)-n)