尋找多維優化算法

Question

問題描述

• 有不同categories含有的elements任意量。
• 有三種不同的attributes A，B和C.每個元素確實有這些attributes的其他分佈。該分佈通過正整數值表示。例如，元素1具有屬性A: 42 B: 1337 C: 18。這些屬性的總和在元素上不一致。有些元素比其他元素更多。

現在的問題：

我們希望一個元素，從每個類別中選擇，這樣

• 我們打的屬性A和B一定的閾值（去在它也是可能但不是必需的）
• 儘管獲得最大量的C.

例如：我們希望在所有選擇的元素上至少擊中80 A和150 B，並希望獲得儘可能多的C。

---

我想過這個問題，無法想象一個有效的解決方案。樣本大小約爲15個類別，每個樣本包含多達30個元素，因此bruteforce並不是非常有效，因爲可能存在30^15個可能性。

我的模型是我認爲它是一棵深度爲的樹數。每個深度級別代表一個類別，並給了我們從這個類別中選擇一個元素的選擇。在傳遞節點時，我們將表示元素的屬性添加到我們想要優化的總和中。

如果我們在同一級別上多次訪問同一個屬性組合，我們將它們合併，這樣我們就可以將已計算值的多個計算分離出來。如果我們達到一個道路在所有三個屬性中價值較低的水平，那麼我們就不會從這裏繼續遵循它。

但是，在最壞的情況下，這棵樹仍然有30〜15個節點。

有沒有人可以想到一個算法，可以幫助我解決這個問題？或者你能解釋爲什麼你認爲這不存在算法嗎？

Answer 1

此問題與knapsack problem的變體非常相似。我將首先看看這個問題的解決方案，並看看你可以如何將它應用於你陳述的問題。

Answer 2

我的第一個傾向是嘗試分支定界。你可以先做廣度優先或深度優先，並且我更喜歡深度優先，因爲我認爲它更乾淨。

簡單來說，你有一個樹形漫步程序walk，它可以枚舉所有的可能性（也許它只有一個5級嵌套循環）。它增加有兩件事情：

• 在的每一步，它跟蹤的cost在該點，那裏的成本只會增加。 （如果成本也可以降低，則它變得更像是一個極大極小的遊戲樹搜索。）

• 該過程的參數爲budget，它不搜索任何成本可能超過預算的分支。

然後你有一個外循環：

for (budget = 0; budget < ... ; budget++){ 
    walk(budget); 
    // if walk finds a solution within the budget, halt 
} 

的花費在預算指數時間量，從而更容易將案件花費更少的時間。您重新進行搜索的事實並不重要，因爲每個級別的預算比以前的所有級別的組合都要多或多。

將此與某種有關您考慮分支的順序的啓發式算法結合起來，它可以爲您提供一個可行的解決方案，以解決您給出的典型問題。

如果不起作用，您可以回退基本啓發式編程。也就是說，親自做一些事情，並注意你是如何做到的。然後以相同的方式編程。

我希望有幫助。