最优匹配

Question

让我们假设你是一名棒球经理。你的牛棚里有N个投手(N<=14)，他们必须面对M个击球手(M<=100)。另外，你也知道每个投手和每个击球手的实力。对于那些不熟悉棒球的人来说，一旦你引入了一名替补投手，他可以向k名连续击球手投球，但一旦他被淘汰出场，他就不能再回来了。

对于每个投手，他输掉比赛的概率是(他将面对的所有击球手的总和)/(他的实力)。尝试最小化这些概率，即尝试最大化您赢得游戏的机会。

例如，我们有3名投手，他们必须面对3名击球手。击球手的强度是：

10 40 30

而你投手的实力是：

40 30 3

最好的解决方案是让最强的投手面对前两名击球手，第二名面对第三名击球手。那么每个投手输掉比赛的概率将是：

50/40 = 1.25和30/30 =1

所以输掉比赛的概率是1.25 (这个数字可以大于100)。

怎样才能找到最优的数字？我在考虑采取一种贪婪的方法，但我怀疑它是否会一直存在。此外，投手可以面对无限数量的击球手(我的意思是它只受到M的限制)的事实给我带来了主要的问题。

Answer 1

概率必须在0.0，1.0的范围内，所以你所说的概率不能是概率。我只会称它为分数并最小化它。

我现在假设你知道投手应该按什么顺序打球。

根据顺序，剩下要决定的是每个投手打多长时间。我认为你可以使用动态编程来解决这个问题。考虑要面对的击球手的顺序。建立一个NxM表最好的投手，击球手，其中besti，j是考虑使用第一个i投手的前j个击球手所能获得的最好分数，如果没有意义，则是巨大的。

best1 1，1只是最好的投手对第一个击球手的得分，而best，j对于j值的任何其他值都没有意义。

对于较大的i值，你可以通过考虑最后一次更换投手的时间，考虑所有的可能性(所以1，2，3...i)来计算besti，j。如果投手的最后一次更改是在时间t，那么查找best，j-1以获得直到该更改之前的得分，然后计算a/b值以考虑时间t+1和时间i之间的击球手强度的总和。当您考虑到所有可能的时间时，取最好的分数并将其用作besti，j的值。记下足够的信息(例如最后证明是最佳的投手更改的时间)，以便一旦计算出bestN，M，您就可以回溯以找到最佳时间表。

你实际上并不知道顺序，因为最终得分是每个投手的a/b值的最大值，所以顺序确实很重要。但是，在给定球员分组的情况下，将投手分配到组的最佳方法是将最佳投手分配给总分最高的组，将次佳投手分配给总分第二好的组，依此类推。如上所述，你可以交替将击球手分组，然后将投手分配到组中，以确定投手真正应该进入的顺序-继续这样做，直到答案停止变化，并希望结果是全局最优的。不幸的是，不能保证这一点。

我不相信你的得分是一个好的棒球模型，特别是因为它一开始是一个概率，但不可能是。也许你应该想出几个例子(甚至可以用暴力解决一些小例子)，看看结果是否合理。

Answer 2

解决这个问题的另一种方法是通过http://en.wikipedia.org/wiki/Branch_and_bound。

使用分支和界限，你需要一些方法来描述部分答案，你需要一些方法来计算给定部分答案的值V，这样扩展部分答案的任何方法都不可能产生比V更好的答案。然后你运行树搜索，以每种可能的方式扩展部分答案，但丢弃不可能比到目前为止找到的最佳答案更好的部分答案。如果你能至少猜测一下最好的答案，这是很好的，因为这样你就可以从一开始就放弃糟糕的部分答案。我的另一个答案可能会提供一种方法来实现这一点。

这里的部分答案是选择投手，按照他们应该上场的顺序，以及他们应该投球的击球手的数量。第一个部分答案是0个投手，你可以选择每个可能的投手，投球给每个可能的击球手，给出一个部分答案的列表，每个部分答案只提到一个投手，其中大多数你可能会放弃。

给定部分答案，您可以计算选择的每个投手的(总击球强度)/(投手强度)。这里找到的最大值是计算V的一种可能的方法。还有另一种计算方法。将剩下的所有击球手的总实力相加，再除以剩下的所有投手的总实力。这将是你能为剩下的投手得到的最好的结果，因为如果你设法尽可能平均地将投手分配给击球手，你就会得到这样的结果。如果此值大于到目前为止计算的V，请使用此值而不是V，以获得不太乐观(但更准确)的度量，以衡量该部分答案的任何后代可能有多好。