如何比較由兩個值組成的元素？ （pareto最佳）

Question

我對Python很新，我想執行某種帕累托最優。這有點難以解釋，所以我希望我的問題能夠清楚地理解。

我有以下模型，其中包含5個門（列表：'門'）的列表，每個門包含兩個成本（顯示在字典'cost'中）：[travel distance，delay]。我想比較每扇門的成本與另一扇門的成本。但是，沒有主導成本。這意味着我想要一個門的列表與最佳的解決方案（最小化成本）兩個成本。

doors = ['D1', 'D2', 'D3', 'D4', 'D5'] 

# cost: [travel distance, delay] 
cost = { 
'D1': [150, 0], 
'D2': [160, 0], 
'D3': [170, 1], 
'D4': [140, 2], 
'D5': [150, 0] 
} 

def test(doors): 
    for s in doors: 
     for d in doors: 
      if s != d: 
       if cost[s][0] < cost[d][0] and cost[s][1] < cost[d][1]: 
        doors.remove(d) 
    return doors 

print(test(doors)) 

例如：D1，D2，D5都具有0延遲的成本。如果我只會尋找在最短的時間成本這三個門會做門。然而，D2的行程距離爲160，大於150.因此，您不會選擇D2（與D1和D5相比），因爲它包含相同的延遲值和較差的行程距離值。所以我們希望將D2從列表中刪除。

對於旅行距離成本，您將選擇D4，因爲它具有最低的旅行距離：140.雖然它具有最高的延遲，但由於行駛距離較短，因此沒有超過D4的門。

因此，最終我想要一個門的列表，其中一個成本最低，其他成本的最佳值。 基於此，我想要有以下輸出：

best_doors = ['D1'，'D4'，'D5']。

在我的模型中，我嘗試比較兩個不同門的成本，並且如果兩個成本都高於另一個門的成本，則移除門，但它不會給我所需的輸出。

我知道我的功能可能太簡單了，不能解決這個問題，但我不知道如何解決這個問題。有人有任何想法如何解決這個問題嗎？我已經在網上查看了幾個網站，但似乎沒有什麼能真正解決我的問題。

您的幫助將非常感謝！

Answer 1

最簡單的是做一個Door類

門類

class Door(): 
    def __init__(self, name, distance, delay): 
     self.name = name 
     self.distance = distance 
     self.delay = delay 

    def __gt__(self, other): 
     return (self.distance > other.distance and self.delay >= other.delay) or \ 
    (self.distance >= other.distance and self.delay > other.delay) 

    def __repr__(self): 
     return 'Door(name=%s, distance=%i, delay=%i'% (self.name, self.distance, self.delay) 

注意雙對比（>，>=）和（>=，>）。由於只有（>，>）會有D1和D2

產生的樣本

這裏我使用了一組，一dict會略有調整

doors_orig = set() 
for d, c in cost.items(): 
    doors_orig.add(Door(d, *c)) 

工作太沒有區別doors_orig

{Door(name=D4, distance=140, delay=2, 
Door(name=D1, distance=150, delay=0, 
Door(name=D5, distance=150, delay=0, 
Door(name=D2, distance=160, delay=0, 
Door(name=D3, distance=170, delay=1} 

實際比較

然後您可以使用itertools.permutations來生成所有可能的組合。檢查該組合是否仍然是可能的最佳門的子集並進行比較。丟棄它是絕對更大的。

doors_perm = doors_orig.copy() 
comb = itertools.permutations(doors_perm, 2) 

for d1, d2 in comb: 
    if {d1, d2} <= doors_perm and (d1 > d2): 
     doors_perm.discard(d1) 

doors_perm

{Door(name=D4, distance=140, delay=2, 
Door(name=D1, distance=150, delay=0, 
Door(name=D5, distance=150, delay=0} 

無論{d1, d2} <= doors_perm是必要取決於所述子集檢查和比較的相對性能。

Answer 2

我知道這可能不會完全回答你的問題，但我希望它會引導你在正確的方向，因爲這不是一個（太）微不足道的問題（而且這太長而無法成爲評論）。

解決這個問題的一種方法是給每個成本一個「權重」，即它對決定是否選擇特定門有多大貢獻。

通常這是通過提出一個適當描述每個成本權重的公式來完成的。

在波紋管的例子，我使用的公式給出的距離爲1的重量和delay 5.

cost = { 
'D1': [150, 0], 
'D2': [160, 0], 
'D3': [170, 1], 
'D4': [140, 2], 
'D5': [150, 0] 
} 

def cost_function(x): 
    # x here is a tuple of the form (door_name, [travel distance, delay]) 
    return x[1][0] + x[1][1] * 5 

print(sorted(cost.items(), key=cost_function)) 
# [('D1', [150, 0]), ('D4', [140, 2]), ('D5', [150, 0]), 
# ('D2', [160, 0]), ('D3', [170, 1])] 

的重量此成本函數實現你想要的特定順序。