在python中求解一个有限制的矩阵

Question

这是个问题：我有两个向量A(1Xn(和B(1Xm(，其中n>m。 我正在寻找一个矩阵 T (nXm(，使得 AT=B。 T 具有以下属性：T 的所有元素都是 1 或 0。 T 中每行中的元素总和为 1。理想情况下，如果没有完美的解决方案，我希望程序返回最佳解决方案，其中 AT-B=0 的元素数量相同。

下面是一个示例：

import numpy as np
A = np.array([-1.051, 1.069, 0.132, -0.003, -0.001, 0.066, -0.28,
              -0.121, 0.075, 0.006, 0.229, -0.018, -0.213, -0.11])
B = np.array([-1.051, 1.201, -0.003, -0.001, 0.066, -0.121, 0.075,
              -0.045,-0.231, -0.11])
T = np.array([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
              [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]])
# This should equal a vector of 0's
print A.dot(T)-B  

Answer 1

我想

出了一些东西，但我认为它并不完全令人满意。 我宁愿不必走这条路，因为它很笨重。 我首先尝试 1 对 1 映射，因为这是许多映射的常见解决方案。 剩下的任何东西我都会迭代所有的可能性。 这很快就会变得有点混乱。 你也会注意到我对 numpy 相当陌生。我将不胜感激有关如何改进这一点的任何反馈。 谢谢。

def solver(B,A):
    m=B.size
    n=A.size
    start=np.ones((1,n))
    start=np.concatenate((start,np.zeros((m-1,n))),axis=0).astype(np.int)
    for i in xrange(0,m):
        T=np.roll(start,i,axis=0)
        test=B.dot(T)-A
        if i==0:
            matches=np.absolute(test)<.0001
        else:
            matches=np.vstack((matches,np.absolute(test)<.0001))
    rA=(A-B.dot(matches))[np.absolute(A-B.dot(matches))>.0001]
    Amissing=A-B.dot(matches)
    rB=(B-B*np.sum(matches,axis=1))[np.absolute(B-B*np.sum(matches,axis=1))>.0001]
    Bmissing=B-B*np.sum(matches,axis=1)
    rm=rB.size
    rn=rA.size
    rmxrn = np.arange(rm*rn).reshape(rm,rn)
    dif=np.absolute(rA)
    best=np.zeros(shape=(rm,rn))
    for i in xrange(0, 2**(rm*rn)):
        arr = (i >> rmxrn) % 2
        if np.amax(np.sum(arr,axis=1))>1 or np.sum(arr)>rm:
            continue
        else:
            diftemp=rB.dot(arr)-rA
            besttemp=arr
            if np.sum(np.absolute(diftemp))<np.sum(np.absolute(dif)):            
                dif=diftemp
                best=besttemp
            if np.sum(np.absolute(dif)<.0001)==rn:
                break
    best=best.astype(np.bool)
    matchesT=matches.T
    bestT=best.T
    newbestT=np.zeros(shape=(m,rn)).astype(np.bool).T
    for x in xrange(0,rn):
        counter=0
        for i, value in enumerate(Bmissing):
            if abs(Bmissing[i])>.0001:
                newbestT[x,i]=bestT[x,counter]
                counter=counter+1
    for x in xrange(0,rn):
        counter=0
        for i, value in enumerate(Amissing):
            if abs(Amissing[i])>.0001:
                matchesT[i]=newbestT[counter]
                counter=counter+1
    return(matchesT.T)
A=np.array([-1.051,1.201,-0.003,-0.001,0.066,-0.121,0.075,-0.045,-0.231,-0.11])             
B=np.array([-1.051,1.069,0.132,-0.003,-0.001,0.066,-0.28,-0.121,0.075,0.006,0.229,-0.018,-0.213,-0.11])
print solver(B,A)