置換爲方程求解

如果有一個方程3a + 6b +7d = 55並將溶液組是{1,4,6}但它是未知的，其在溶液中編號對應於變量，有一種方法，以確定哪個號碼對應與可變，而無需使用強力力？如果方程有1000個變量，這個方法可以縮放嗎？謝謝！置換爲方程求解

來源

2016-12-16 artificial_intelligence

如果所有係數與解是非負（或相反，非正），則比幼稚蠻力稍快的方法將是消除這些係數 - 導致期限大於預期總和的解決方案對... – Travis

好的謝謝。是否有任何啓發式算法或梯度下降方法嘗試？ –

您可能想在[計算機科學]（http://cs.stackexchange.com/）或[數學]（http://math.stackexchange.com/）的Stack Exchange網站上發佈該問題。它可能更適合那些社區，而不是Stack Overflow。 – Travis

這是具有修剪搜索功能的解決方案無法找到的蠻力解決方案。

讓我們來展示兩件事。首先，如果係數和解是非負數，並且如果它們被表示爲排序列表，則最大值方程可以具有「平行和」，並且最小值是「反轉和」。

max = sum(c*s for c, s in zip(coeffs, sols)) 
min = sum(c*s for c, s in zip(coeffs, reversed(sols)))

這足以看到，四個數字0 <= a1 <= a2和0 <= b1 <= b2認爲：

a1*b1 + a2*b2 = a1*b2 + a2*b1 + (a2-a1)*(b2-b1) >= a1*b2 + a2*b1.

二是，它始終是可能轉化問題的同類型非負係數的問題解決方案。爲了將解決方案「移動」到非負數，需要將所有解決方案的值增加到-min(solutions)並導致-min(solutions)*sum(coefficients)。相似的過程會將係數移動到非負數。

這裏是Python實現的解決方案：

def C(coeffs, res, sols): 
    _max = sum(i*j for i, j in zip(coeffs, sols)) 
    if _max < res: # No result 
     return None 
    if _max == res: # Result mapping coeffs <-> sols 
     return sols 
    _min = sum(i*j for i, j in zip(coeffs, reversed(sols))) 
    if _min > res: # No result 
     return None 
    if _min == res: # Result mapping coeffs <-> reversed sols 
     return sols[::-1] # reverse sols 
    # For next coefficient try all solutions 
    for i, s in enumerate(sols): 
     r = C(coeffs[1:], res - coeffs[0]*s, sols[:i] + sols[(i+1):]) 
     if r is not None: 
      return [s] + r 

print C([3, 6, 7], 55, [1, 4, 6])

來源

2016-12-19 21:01:48 Ante

置換爲方程求解

回答

相關問題