問題描述尋找多維優化算法
- 有不同
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個節點。
有沒有人可以想到一個算法,可以幫助我解決這個問題?或者你能解釋爲什麼你認爲這不存在算法嗎?
如果你能創建一個場景,這將有助於我看到你在說什麼。我認爲這是一個優化問題,但如果您有一個非最佳解決方案來滿足要求,那麼這會是足夠的嗎? –
我正在尋找最佳解決方案。但是,也接受近乎最佳的解決方案。滿足要求是必須的。 – Etan