如何以編程方式求解y =（a1 * x1）+（a2 * x2）+ .... +（a28 * x28）其中y和a1，a2 .... a28是已知的？

我試圖解決這個方程28個變量：如何以編程方式求解y =（a1 * x1）+（a2 * x2）+ .... +（a28 * x28）其中y和a1，a2 .... a28是已知的？

Y =（A1 * X1）+（A2 *×2）+ ... +（A28 * X28）

1）y是已知，所以a1，a2都是通過a28。 2）x1，x2 ..... x28是未知變量，它們的範圍是[-4,4]，增量爲0.1。

有人可以在我困惑的大腦上找到一些關於哪種算法最有效的方法嗎？

來源

2012-12-14 Jason Ye

x1 ... x28是否有所有不同的值？因爲在那種情況下，如果我沒有弄錯，會有非常多的有效解決方案。 –

你用'0.1增量'表示的範圍是多少？ – irrelephant

@irrelephant即時猜測他們是-4或-3.9或.... 3。9或4 –

這相當於整數線性規劃，儘管由於只有一個具有28個簡單約束（邊界，而不是方程系統）的方程，您可能會做得更好。一般來說，這將是NP難的（見https://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns），但有幾種實現方式可以使用（例如參見How to choose an integer linear programming solver?）

來源

2012-12-14 03:44:55 dfb

這不是一個線性規劃問題，它是一個方程而不是關係或最大化。答案肯定是y。 –

您可以將其視爲最大化右側總和，但受限於總和不得超過y。結合乘以10來擺脫分數，可能會使其成爲現有實際解算器的問題。 –

首先將所有東西都乘以10，這樣可以保留整數數學。此外，將總和（40 * a_u）添加到雙方將會將x_i的範圍更改爲[0,80]

其次，可能存在指數數量的答案，因此您的算法必須採用指數時間。

考慮到有80^28（約2^177）個可能的答案 - 這是不可能的。

現在，如果x_i的範圍是[0,1]（而不是[0,80]），並且我們添加一個等於y（並將y更改爲0）的額外項，則問題將變爲找到總和爲零的一組整數的子集。這是一個衆所周知的NP完整問題，它似乎比你更容易（儘管我沒有明確的減少）。

有可能是一個動態規劃的解決方案，但它可能是太慢：

set<float> X; 

X.insert(0) 

for i = 1 to 28 
    for f = -4.0 to 4.0 step 0.1 
     for x in X 
      X.insert(x + a_i * f) 

for x in X 
    if (x == y) 
     return true; 

return false;

你可以通過回傳可行的範圍比這更好的含量（[Y + A_I *（ - 4.0）， y + a_i * 4.0]）並在這些邊界之外修剪不可行的部分解。

來源

2012-12-14 03:51:12

你不能真正揹包這樣的問題。你上面做的是添加-4.0 * X1，-3.9 * X1等違反約束條件（更不用說你會用完內存:)） – dfb

@dfb：我同意取決於a_i它是指數空間，但它是如何違反約束條件的？ –

您可以在prolog中編程（SICStus prolog引擎和Eclipse上的SPIDER IDE）。這個問題是狀態空間搜索問題。並使用clpfd庫（有限域上的約束邏輯編程）。那麼你只需做一個約束，X1到X28就是域變量，給定約束y＃= a1 * X1 + ... + a28 * X28。還有很少的方法來優化狀態空間的搜索。

/編輯：或者你可以嘗試使用任何命令式語言。還可以使用一些啓發式方法 - 例如，選擇一些執行點，您可以在其中檢查當前結果（例如，您有一些tmp。sum，並且您已經從28個值中計算出15個值）。如果y減去溫和值小於MIN_VARIABLE_VALUE * i，其中i是索引，x_i屬於其餘變量，您可以放心地決定，您不會繼續，bcs。您不能平等）。這種啓發式首先讓我想起。使用也可以在這裏使用一些替代。但是應該對一些測試數據進行「研究」，它的效率有多高。

來源

2012-12-14 07:29:28 Equo

如何以編程方式求解y =（a1 * x1）+（a2 * x2）+ .... +（a28 * x28）其中y和a1，a2 .... a28是已知的？

回答

相關問題