使用哪種Multiple-Criteria排序算法？

讓我們說我們有物品清單，每個物品都有（未知）數量的屬性。通過單一屬性排序是一種簡單的排序算法。現在的問題是：如何對所有屬性排序相同的列表？每個屬性都有一個權重，所以我們可以先用最不重要的屬性進行排序，然後再用更重要的屬性用穩定的排序算法等等，但這顯然效率不高。使用哪種Multiple-Criteria排序算法？

謝謝。

來源

2011-09-15 Dima

創建函數f：A1xA2x ..-> R [即根據優先級和屬性賦予每個元素一個值]。該函數非常依賴於屬性[例如，如果屬性值在範圍（0,9）中，則給出值很簡單：Sigma[val(i)*10^prio(i)] for each attribute i。

迭代列表，計算函數值，並緩存該函數結果，並根據它進行排序。複雜度將爲O（nk + nlogn），其中k是屬性的數量，n是元素的數量。

來源

2011-09-15 13:34:44 amit

什麼是'prio（i）'？ – Dima

'prio（i）'是第i個屬性的優先級，其中i = 0在這個例子中是最不重要的。 – amit

嘿！我剛剛看到你的答案（在2年後..），我試圖理解它近兩天..你可以嘗試解釋算法或鏈接到一些參考？ –

大多數排序算法可以將一個比較函數作爲輸入，它可以結合幾個排序條件。最後，爲了能夠進行排序，所有元素之間必須存在單一的排序關係（例如，A肯定在元素B之前，反之亦然，或者兩者是等價的;關係必須滿足傳遞/對稱/自反屬性），所以這意味着必須有一個排序算法的一次排序，給定一個有效的比較函數。

來源

2011-09-15 13:34:47

這也是O（k * n * logn）最壞的情況，[k是屬性的數量，n是元素的數量]，因爲您需要在每次比較中檢查k個元素。與用穩定算法排序k次相同的界限。 – amit

是的，但你不需要使用穩定的排序。 –

是真實的，並且性能可能會更好，然後排序k次，因爲你不需要對所有元素進行全部k次比較，只是指出它將漸進地相同[至少對於最差情況下的分析] – amit

SORT BY A,B,C

你的那種裏面比較會： A，B，C是最高到最低prioerity

比較單元1與元件2之上的是一個
- 如果大於或小於返回結果
- 否則比較B
- - 如果大於或小於返回結果
- - 否則比較C返回結果

這可以被外推到A..n標準與一個簡單的循環。

對於標準的列表中的每個標準
- 比較部件1的標準與元素2的
- - 如果大於或小於返回結果
- - 否則繼續//爲清楚起見
返回等於

以上兩個假設你比較功能比較（元素1，元素2）

來源

2011-09-15 13:42:02

這也是O（k * n * logn），其中k是屬性的數量，n是元素的數量，與簡單排序k次相同。 – amit

與此相關的問題是，一個標準A的重量遠遠超過其他一切。說學生擅長數學，我希望有人加入我的機器人團隊。但是，那些學生吸取道德，專業，編碼，有毒品問題等等，但是因爲數學是開始重要的因素，算法會建議最好的學生是這個，至少他會成爲頂尖學生 –

@MuhammadUmer - 你想要一個*得分*算法不是*排序*算法。所以，你想要根據你認爲令人欽佩的分數爲每個學生創造一個分數，然後你會按照那個分數排序。 –

使用哪種Multiple-Criteria排序算法？

回答

相關問題