搜索子集，算法（最佳或啓發式）

我在尋找有關問題的搜索算法的幫助。問題可以簡化爲以下內容。搜索子集，算法（最佳或啓發式）

我們有一個對象可以具有某些屬性 - X1，X2 ... XN。 N是5000的數量級。然而，一個特定的對象需要這些屬性的一個子集，如Xi .. Xj（約50）。

配置是屬性的特定子集。有一些配置，編號爲Z（數量爲10萬），是最優的。

輸入：

Configuration 1: X1, X2, X3.. Xf 
Configuration 2: X4, X6, X7, .. Xz 
: 
: 
Configuration Z: X10, X200… XN

問題：給定一個特定的對象，ALPHA與屬性的子集{曦...... XJ}的目標是找到最接近該對象的配置。該配置可以是對象ALPHA配置的超集。也可能是沒有配置具有ALPHA的所有屬性。最近的被定義爲具有ALPHA的最多號碼屬性的配置。

天真的解決方案，我已經基本上做以下

1. Take each configuration 
2. Loop through each attribute of ALPHA 
3. Keep track of the configuration with maximum number of matches to ALPHA 
4. Pop out the configuration maximum matches.

我覺得天真的解決方案是正確的，但實在是太慢了。是否有一種有效的方法可以在整個配置中進行搜索？如果速度非常快，即使近似的啓發式算法也很好。

添加C++，Java標籤以查看是否有軟件執行此操作。

謝謝。

來源

2013-10-18 healthdev

這裏有一個更好的非啓發式方法。反向存儲您的最佳配置。即映射每個屬性出現在配置。如（無關於你的例子）

X1 : C1 C4 C5 C99999 
X2 : C1 C2 
X3 : C1 
X4 : C1 C2 
... 
XN : C100 C200 C300

現在，你讓長Z的陣列來存儲你有多少匹配項。您通過ALPHA進行迭代，並對每個屬性進行相關配置。對於每個配置，您將一個添加到陣列中的相應位置。

最後，運行數組並選擇計數最大的配置。如果你願意，你可以保持一個運行的最大值，但是如果你希望總共做少於Z比較（ALPHA中的元素數量乘以相關配置的平均數量），那將只會更有效。

這將找到最佳匹配，並且應該比您的天真解決方案快大約50倍。

來源

2013-10-18 02:31:58 paddy

感謝稻田。您的解決方案直觀有意義。我將不得不在早上考慮:-)。在較小的測試案例中，它的運行速度要快10-20倍。明天將運行更大的測試並接受你的答案。 – healthdev

不用擔心。祝你好運。假設配置在這個空間中均勻分佈，我建議根據您提到的典型數字加快50倍。情況可能不是這樣，但它仍然要快得多。 – paddy

好消息！程序大約快25倍。非常感謝稻田。 – healthdev

搜索子集，算法（最佳或啓發式）

回答

相關問題