選擇集合的子集使得子集滿足全局約束條件

我們有一組項目I = {i_1，i_2，...，i_n}。這些項目中的每一項都具有我們所稱的p值，這是一些實數。我們想選擇I的一個子集，稱爲I'，其大小爲m（對於某些具有1 < = m的< = m），使得I'中的項的值的平均值落入某個指定的範圍內範圍，[p_l，p_u]。（例如，我們可能需要的平均值在0.70和0.74之間。）此外，我們希望有效地完成此操作。選擇集合的子集使得子集滿足全局約束條件

我們希望在O（n）時間內做到這一點，但任何多項式時間算法都足夠好。我們當然不想嘗試每個可能的大小爲m的I子集，然後檢查它是否滿足平均p值約束。

最後，我們將重複這樣做，我們希望選擇的子集在所有可能的子集上均勻隨機分佈。

有沒有辦法做到這一點？

來源

2010-08-24 Paul Reiners

對此，多項式時間算法似乎不太可能。這個問題可能相當於一般的*約束子集選擇問題*，這是NP。如果您的輸入值緊密聚集在某個數據透視點附近，並且具有正態分佈，則可以使用回溯算法來選擇符合要求的子集。但是，確保您對l的所有成員進行統一的隨機分配將是具有挑戰性的。你可能會有更好的運氣在[mathoverflow.com]（http://www.mathoverflow.com）上尋求幫助。 – LBushkin 2010-08-24 16:41:27

感謝您的評論。我傾向於認爲問題也是棘手的。我可能會問mathoverflow.com，但到目前爲止，我發現堆棧溢出是更有幫助，即使這樣的理論問題。 – 2010-08-24 17:15:12

如果您有一個子集及其總和，如果您將總和按| subset + 1 |/| subset |進行縮放，則您添加的每個新元素都會對總和做出線性貢獻。這似乎與子集和問題（NP-complete）非常相似，其目標是找到所有總和爲0的子集，儘管這裏我們希望總和接近0.例如，如果你有一個大的設置一個元素大致在可接受的p範圍內的位置，如果您粗略地假設該元素無關緊要，則突然實際上是相等的......假設您有大量的正負p值，並且問題不是由對手構建的。如果是這種情況，您可以使用http://en.wikipedia.org/wiki/Subset_sum_problem給出的兩個近似解決方案之一，使相等性爲「模糊」，然後僅在該「集合」上使用0.7「0.」0.74的「保留」元素。

當然，您可以從您的解決方案中剔除的效率是難以置信的，這取決於生成p值的方式（「分佈」）。

來源

2011-05-06 01:23:51 ninjagecko

選擇集合的子集使得子集滿足全局約束條件

回答

相關問題