如何找到两个对战团队的最佳解决方案？

Question

如何找到两个对战团队的最佳解决方案？

pythonalgorithmoptimizationdata-structures

3

我有一张关于A队和B队的表格，其中每对2名球员之间都有一个数字。行代表A队的球员，列代表B队的球员。如果一个数字为正数，意味着A队的球员比B队的球员好，如果是负数则相反。

例如：

-710 415 527 -641 175 48
-447 -799 253 626 304 895
509 -523 -758 -678 -689 92
24 -318 -61 -9 174 255
487 408 696 861 -394 -67

两支队伍都了解这张表格。现在，团队A报告了5名球员，团队B可以查看并选择最适合他们的5名球员。如果我们想比较球队，我们总结从表格中给定的位置上的数字，知道每个队都有一个被计算两次的队长（就像一个队有6个球员且队长出现两次），如果总和是正数，则团队A更好。

输入的数字为a（行/球员数A）和b（列/球员数B），表格如下：

6
6
-54 -927 428 -510 911 93
-710 415 527 -641 175 48
-447 -799 253 626 304 895
509 -523 -758 -678 -689 92
24 -318 -61 -9 174 255
487 408 696 861 -394 -67

输出应该是1282。

所以，我所做的是将数字放入一个矩阵中，就像这样:

a, b = int(input()), int(input())

matrix = [list(map(int,input().split())) for _ in range(a)]

我在这里使用了一个最小堆和一个最大堆。我将行放入最大堆中，因为A队想要最大的，然后我从中获取5个最好的A球员，如下所示：

for player, values in enumerate(matrix):
    maxheap.enqueue(sum(values), player)

playersA = []
overallA = 0

for i in range(5):
    ov, pl  = maxheap.remove_max()
    if i == 0: # it is a captain
        playersA.append(pl)
        overallA += ov
        
    playersA.append(pl)
    overallA += ov

B 队知道 A 球队的使用情况，他们使用 MinHeap 来找到自己最好的 5 名球员：

for i in range(b):
    player = []
    ov = 0
    for j in range(a): #take out a column of a matrix
        player.append(matrix[j][i])


    for rival in playersA: #counting only players already chosen by A
        ov += player[rival]

    minheap.enqueue(ov,i)

playersB = []
overallB = 0

for i in range(5):
    ov, pl = minheap.remove_min()
    if i == 0:
        playersB.append(pl)
        overallB += ov
        
    playersB.append(pl)
    overallB += ov

给定玩家后，我从矩阵中计算总和：

out = 0
for a in playersA:
    for b in playersB:
        out += matrix[a][b]
print(out)

然而，这种解决方案并不能总是给出正确的结果。例如，对于以下输入，它并不能返回正确的结果：

10
10
-802 -781 826 997 -403 243 -533 -694 195 182
103 182 -14 130 953 -900 43 334 -724 716
-350 506 184 691 -785 742 -303 -682 186 -520
25 -815 475 -407 -78 509 -512 714 898 243
758 -743 -504 -160 855 -792 -177 747 188 -190
333 -439 529 795 -500 112 625 -2 -994 282
824 498 -899 158 453 644 117 598 432 310
-799 594 933 -15 47 -687 68 480 -933 -631
741 400 979 -52 -78 -744 -573 -170 882 -610
-376 -928 -324 658 -538 811 -724 848 344 -308

但它并不适用于

11
11
279 475 -894 -641 -716 687 253 -451 580 -727 -509
880 -778 -867 -527 816 -458 -136 -517 217 58 740
360 -841 492 -3 940 754 -584 715 -389 438 -887
-739 664 972 838 -974 -802 799 258 628 3 815
952 -404 -273 -323 -948 674 687 233 62 -339 352
285 -535 -812 -452 -335 -452 -799 -902 691 195 -837
-78 56 459 -178 631 -348 481 608 -131 -575 732
-212 -826 -547 440 -399 -994 486 -382 -509 483 -786
-94 -983 785 -8 445 -462 -138 804 749 890 -890
-184 872 -341 776 447 -573 405 462 -76 -69 906
-617 704 292 287 464 -711 354 428 444 -42 45

所以问题是：是否可以这样做，或者是否存在另一个快速算法（O(n ** 2) / O(n ** 3)等），或者我只能使用O(n!)的暴力方法尝试所有可能的组合？

- romhud

每个团队是否总是选择 4 名球员和 1 名队长，或者这取决于每个团队的总人数？ - Anne Aunyme

任何球员都可以被指定为队长吗？ - itprorh66

@AnneAunyme 是的，他们总是选择5名球员-4 + 1。 - romhud

你明白为什么你的算法没有产生最优结果吗？还是需要我给你解释一下？ - Anne Aunyme

@AnneAunyme 不，我没有。我想做一些比尝试所有组合更有效的事情。 - romhud

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anne Aunyme · Accepted Answer

有一种方法可以用多项式复杂度来解决这个问题。

为了说明为什么你的解决方案不可行，让我们考虑一个更简单的问题。假设每个团队只选两名球员，没有队长。

我们还可以使用一个简单的得分矩阵：

1 1 1 2 1 1 1 1 1 1 0 3 0 2 0 0 0 0 0 4 0 0 0 0 4

在这里，您可以看到A队没有赢的机会（因为没有负数），但他们仍然会尽力而为。他们应该选择谁？

使用您的算法，A队应该选择他们最好的球员，他们的排名将是： pa0 < pa1 = pa2 < pa3 = pa4

如果他们选择pa3和pa4，他们的分数都是4（这很糟糕，但不像pa0的6分那么糟糕），B队将以8分获胜（他们将选择pb4和另一位不重要的球员）。

另一方面，如果A队选择pa0和pa1（根据您的指标比pa3和pa4差），最好的B队可以获得的就是以5分赢得比赛（如果他们选择pb3和任何其他球员）。

基本上，您的近似算法未能考虑到B队只能选择两名球员，因此无法利用pa0+pa1的弱点，而可以轻松利用pa3+pa4的弱点。

更好的解决方案是让A队仅评估每个球员的得分，只考虑他们最差的2个得分（或选择5名球员时为5个得分）：这将使排名如下： pa2 < pa3 = pa4 < pa0 < pa1

仍然是一个近似值：一些组合，如pa2+pa3，实际上并不像听起来那么糟糕，因为再次，弱点足够分散，以至于B队无法利用它们所有的弱点（尽管对于这个例子，近似值产生了最佳结果）。

我们真正需要选择的不是两个最好的球员，而是最好的两个球员组合，遗憾的是我不知道其他方法，除了尝试在s（团队大小）中选择k个球员的所有$s!/(k!(s-k)!)$组合。不过，这并不算太糟糕，因为对于k=2，这只有$s*(s-1)/2$，对于k=5，这是$s*(s-1)(s-2)(s-3)*(s-4)/5!$，尽管复杂度为O(s^5)，但仍然是多项式复杂度。将队长加入到混合物中只会将组合数乘以k。它还需要一种计算分数的方法，但您应该能够找到它。

现在A队已经选定了他们的球员，B队则有一个简单的任务来选择球员。这很简单，因为每个球员都可以单独选择。

以下是如何使用最后一个算法与起始得分矩阵的示例。

A队有10种可能的组合：pa0 + pa1，pa0 + pa2，pa0 + pa3，pa0 + pa4，pa1 + pa2，pa1 + pa3，pa1 + pa4，pa2 + pa3，pa2 + pa4，pa3 + pa4。它们的得分分别是：5,8,7,7,7,6,6,7,7,8。

最佳组合是pa0 + pa1，所以它们将其发送给B队。

B队对其每个球员的得分与pa0 + pa1进行计算：pb0:2，pb1:2，pb2:2，pb3:3，pb4:2。pb3是最好的，其他所有的都相等，因此B队发送pb3 + pb4（例如），并且“答案”是5。