求解线性系统通过与numpy的整数(Solving linear system over integ

我试图解决numpy的方程的超定线性系统。目前，我做这样的事情（如一个简单的例子）：

a = np.array([[1,0], [0,1], [-1,1]])
b = np.array([1,1,0])

print np.linalg.lstsq(a,b)[0]

[ 1.  1.]

这工作，但使用浮动。有什么办法解决系统上唯一的整数？我试着沿东西线

print map(int, np.linalg.lstsq(a,b)[0])

[0, 1]

为了解决方案转换成int数组，希望[1, 1]但显然我失去了一些东西。任何人都可以点我在正确的方向？

Answer 1:

You are looking at a system of linear diophantine equations. A quick Google search comes up with Systems of Linear Diophantine Equations by Felix Lazebnik. In that paper, the author considers the following question:

Given a system of linear equations Ax = b, where A = a(i,j) is an m × n matrix with integer entries, and b is an m × 1 column vector with integer components, does the system have an integer solution, i.e. an n × 1 solution vector x with integer components?

Answer 2:

您应该使用专门的整数解决问题的能手（注意整数问题都没有解决，甚至简单）。 openopt是一个包，例如应为整数二次优化良好的包装，如你在做什么。尝试使用线性代数根本不会给你正确的解决方案，直接。

你的问题可以写成一个二次规划，但它是一个整数之一，所以使用openopt或一些其它的模块。由于这是一个非常简单的，不受约束的一个，也许有一些其他的办法。但对于初学者它不是简单的问题，它看起来像在第一，并且有在openopt程序等准备有效地解决这种事情。

Answer 3:

当您转换为int ，元素的小数部分被截断，因此它被舍去。

a = np.array([[1,0], [0,1], [-1,1]])
b = np.array([1,1,0])

x = np.linalg.lstsq(a,b)[0]

结果：

>>> x
array([ 1.,  1.])
>>> x[0]
0.99999999999999967
>>> x[1]
1.0000000000000002
>>> x.astype(int)
array([0, 1])
>>> map(int, x)
[0, 1]
>>> np.array([1.,1.]).astype(int) # works fine here
array([1, 1])

Answer 4:

我可能会误解你的问题，但我认为你只需要组合round ，然后astype(int)

如

a = np.array([[1,0], [0,1], [-1,1]])
b = np.array([1,1,0])

x = np.linalg.lstsq(a,b)[0]
print x.round().astype(int)

Answer 5:

+1 seberg，这里是一个反例来说明你不应该映射轮：
（对不起，这是MATLAB的风格，但你会很容易pythonize）

a =
     3     0
     0     3
     1     1
b = 
    2.71
   11.7
    0.5
x = a\b =
    0.5121
    3.5088
round(x) =
    1
    4
norm(a*round(x)-b) = 4.5193
norm(a*[0;4]-b) = 4.4367
norm(a*[1;3]-b) = 4.4299