曲棍球台球算法

Question

这是一个有趣的项目，我已经开始尝试最大程度地提高赢得办公室曲棍球池的机会。我正在尝试找到选择 20 名球员的最佳方法，这些球员将在最高工资帽内为我提供最多的分数。

例如，假设原始数据由

1. 球员姓名
2. 位置（前锋、防守队员、守门员）
3. 的预测得分
4. 、本赛季薪水

组成。现在我想要 20 名能够在 X 工资帽内给我最多分数的球员。稍后，作为第二阶段，我想做同样的事情，但在这种情况下，我只想要 12 名前锋、6 名后卫和 2 名守门员。

现在显而易见的方法是简单地采用所有可能的组合，然而，虽然这可行，但它不是一个有效的选择，因为对于 500 名玩家来说，这将有太多可能的组合。我可以添加一些智能过滤器，将 500 名球员减少到前 50 名前锋、前 30 名后卫和前 15 名守门员，但这仍然是一个非常缓慢的过程。

我想知道是否还有其他算法可以实现这一点。这只是为了好玩，并不是重要的业务请求。但如果您对如何继续有一些想法，请告诉我。

我的第一次尝试是在其他来源的帮助下使用背包算法。它似乎只使用薪水作为参数。我正在努力弄清楚如何添加 20 名玩家的团队参数。它在 .Net 中，但应该很容易转换为 Java。

我正在考虑做一个单独的循环来找出拥有 20 名球员的最佳球队，无论薪水如何，然后比较两个列表，直到找到两个列表中最高的球队。没有把握。

namespace HockeyPoolCalculator
{
public class ZeroOneKnapsack
{

protected List<Item> itemList = new List<Item>();
protected int maxSalary = 0;
protected int teamSize = 0;
protected int teamSalary = 0;
protected int points = 0;
protected bool calculated = false;

public ZeroOneKnapsack() { }

public ZeroOneKnapsack(int _maxSalary)
{
setMaxSalary(_maxSalary);
}

public ZeroOneKnapsack(List<Item> _itemList)
{
setItemList(_itemList);
}

public ZeroOneKnapsack(List<Item> _itemList, int _maxSalary)
{
setItemList(_itemList);
setMaxSalary(_maxSalary);
}

// calculte the solution of 0-1 knapsack problem with dynamic method:
public virtual List<Item> calcSolution()
{
int n = itemList.Count;

setInitialStateForCalculation();
if (n > 0 && maxSalary > 0)
{
List<List<int>> playerList = new List<List<int>>();
List<int> salaryList = new List<int>();

//initialise list
playerList.Add(salaryList);
for (int j = 0; j <= maxSalary; j++)
salaryList.Add(0);
// Loop through players
for (int i = 1; i <= n; i++)
{
List<int> prev = salaryList;
playerList.Add(salaryList = new List<int>());
for (int j = 0; j <= maxSalary; j++)
{
if (j > 0)
{
int wH = itemList.ElementAt(i - 1).getSalary();
// Is the players salary more than the current calculated salary? If yes, then keep current max points, else get the highest amount between previous max points at that salary and new max points.
salaryList.Add((wH > j)?prev.ElementAt(j): Math.Max(prev.ElementAt(j),itemList.ElementAt(i - 1).getPoints() + prev.ElementAt(j - wH)));
}
else
{
salaryList.Add(0);
}
} // for (j...)
} // for (i...)
points = salaryList.ElementAt(maxSalary);

for (int i = n, j = maxSalary; i > 0 && j >= 0; i--)
{
int tempI = playerList.ElementAt(i).ElementAt(j);
int tempI_1 = playerList.ElementAt(i - 1).ElementAt(j);
if ((i == 0 && tempI > 0)||(i > 0 && tempI != tempI_1))
{
Item iH = itemList.ElementAt(i - 1);
int wH = iH.getSalary();
iH.setInKnapsack(1);
j -= wH;
teamSalary += wH;
}
} // for()
calculated = true;
} // if()
return itemList;
}

// add an item to the item list
public void add(String name, int Salary, int value)
{
if (name.Equals(""))
name = "" + (itemList.Count() + 1);
itemList.Add(new Item(name, Salary, value));
setInitialStateForCalculation();
}

// add an item to the item list
public void add(int Salary, int value)
{
add("", Salary, value); // the name will be "itemList.size() + 1"!
}

// remove an item from the item list
public void remove(String name)
{
for (int pointer = 0; pointer <= itemList.Count-1; pointer++)

{
itemList[pointer].getName().Equals("");

if (itemList.ElementAt(pointer).getName().Equals(itemList.ElementAt(pointer).getName()))
{
itemList.Remove(itemList.ElementAt(pointer));
}
}
setInitialStateForCalculation();
}

// remove all items from the item list
public void removeAllItems()
{
itemList.Clear();
setInitialStateForCalculation();
}

public int getPoints()
{
if (!calculated)
calcSolution();
return points;
}

public int getSolutionSalary() { return teamSalary; }
public bool isCalculated() { return calculated; }
public int getMaxSalary() { return maxSalary; }

public void setTeamSize(int _teamSize)
{
teamSize = _teamSize;
}

public int getTeamSize()
{
return teamSize;
}

public void setMaxSalary(int _maxSalary)
{
maxSalary = Math.Max(_maxSalary, 0);
}

public void setItemList(List<Item> _itemList) {
if (_itemList != null) {
itemList = _itemList;
foreach (Item item in _itemList) {
item.checkMembers();
}
}
}

// set the member with name "inKnapsack" by all items:
private void setInKnapsackByAll(int inKnapsack) {
foreach (Item item in itemList)
if (inKnapsack > 0)
item.setInKnapsack(1);
else
item.setInKnapsack(0);
}

// set the data members of class in the state of starting the calculation:
protected void setInitialStateForCalculation()
{
setInKnapsackByAll(0);
calculated = false;
points = 0;
teamSalary = 0;
teamSize = 0;
}

} 
}

感谢您的帮助！

Answer 1

不幸的是，你不应该期望找到一个好的解决方案来解决这个问题，因为它是NP-hard。除非P = NP，否则不存在任何多项式时间算法，并且穷举搜索是可能是最好的算法之一（尽管您可以使用一些启发式方法来加快速度）。

为了看出这个问题是 NP 困难的，我们将展示如何减少背包问题 在多项式时间内完成。给定由集合 S = {(weight₁, value₁), (weight₂, value< sub>2), ... , (weight_n, value_n)} 和重量限制 k，我们可以通过以下方式构建曲棍球问题的实例创建一组球员，他们的薪水是权重，他们的期望得分是价值。然后，我们尝试找到工资不超过 k 的球员的最大体重组合，该组合与您在原始背包问题中可以赚到的不超过目标体重的最大总和相同。

不过，正如您发布的代码所示，有一个伪多项式时间算法可以解决背包问题。假设工资很低（或者您可以将其标准化为较小的数字），您也许可以利用它取得良好的效果。

虽然是否存在多项式时间算法来获得准确答案值得怀疑，但如果您可以接受近似最优解，则可以使用多项式时间算法来近似解决背包问题。有关详细信息，请查看这些注释 ，其中详细介绍了两种算法。有趣的是，它们依赖于您似乎正在使用的伪多项式时间算法，所以也许它们很容易实现？

抱歉，让你对数学一个好的解决方案的希望破灭了……NP 难题往往会这样做。 :-(

Answer 2

将球员绘制在图表上，X 轴是分数，Y 轴是薪水，零位于起源。右下方的玩家将是理想的廉价高得分手，左上方的玩家将是不受欢迎的昂贵的低得分手，对角线上的玩家将是相同的（每点成本相同）。将原点锚定半径从 X 水平逆时针扫到 Y 垂直，形成不断增长的饼图切片，直到切片内有 20 名玩家或切片内的总工资达到上限。如果达到 $ 上限但未达到 20 名玩家，请删除切片内的“最左上方”玩家并继续。如果您达到 20 名玩家但未达到上限，您可以从切片中删除低得分玩家，为即将进入切片的高得分玩家腾出空间，从而使您的每点总成本不必要地上升，但因为这是有趣的钱而且你不是真正的主人，那就去吧。

Answer 3

解决此类问题的一个有趣方法是使用遗传算法。事实上，我就是为我自己的曲棍球池这么做的！

如果你好奇的话，你可以在这里看到整个 Scala 代码，但它的核心是：

def GA(nbIter: Int, popSize: Int, tournamentSize: Int) = {
  def loop(iter: Int, pop: Seq[LineUp]): LineUp = {
    val best = pop.maxBy(_.fitness)
    println("\nBest of generation " + iter + best)
    if (iter == nbIter)
      best
    else {
      val newPop = for {
        _ ← Stream.continually()
        x = tournament(pop, tournamentSize).head
        y = (x.mutants take 5) maxBy (_.fitness)
      } yield y
      loop(iter + 1, best +: newPop.take(popSize - 1))
    }
  }
  val initialPop = LineUp.randomStream.take(popSize)
  loop(0, initialPop)
} 

它开始于生成有效阵容的随机集合（尊重工资上限和职位限制）。对于每次迭代，它都会使用锦标赛选择和爬山。 “体能”简单地定义为以最低工资的阵容作为决胜局的预期得分。

当然，这只是一种启发式方法，但如果您的玩家列表不是太大，并且您有能力让算法运行一段时间，那么您很有可能找到一个相当最优的解决方案。

Answer 4

这个问题可能很难，但你可以利用你的守门员不会进攻的事实（更正式的是：你选择的实体属于不同类别）来提高你的运行时间。

此外，您可能想找到问题的近似解决方案。使用该值来限制最佳解决方案并对其进行搜索。

Answer 5

您可以轻松地将其表示为 ILP。解决它们也是NP-Hard，但是问题实例似乎不是那么大，所以它可能是可以完美解决的（一个求解器是例如lpsolve）。即使由于问题规模而无法完美解决，ILP 也存在良好的启发式方法。