如何比较由两个值组成的元素？ （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])] 

的重量此成本函数实现你想要的特定顺序。