所以这是我一直在研究的问题： 你会得到一个随机的 nxn 网格，网格的每个框中都有权重，你还会得到一组钉子 p<=n。您的目标是将钉子放置在网格上，以便放置钉子的网格上的权重总和最大化。 限制是钉子位置也必须遵循非攻击女王的位置。
我最初的尝试是从最大分数网格框开始，然后遵循 n 个女王的位置。但是，这不起作用，因为它最终会错过最大值。
我一直试图用 A* 解决这个问题，但一直在努力寻找启发式方法。
通常 A* 搜索用于查找最短路径，而不是用于查找最大值，但您也可以将其用于最大化。 在通常的最小化版本中，您的启发式必须始终是长度的下限。 为了最大化，启发式需要是一个不太难计算的上限。 而且您需要一个最大堆，而不是最小堆来生成下一个最佳候选者。
另一个问题是，有许多不同的订单来选择最佳展示位置。 使用nxn板，将有n!这样的订单。 如果您执行诸如坚持从最大到最小引脚进行选择之类的操作，您将大大加快搜索速度。
因此，我建议作为启发式方法，将尚未受到攻击的最大引脚的总和，并且不大于您当前选择的最小引脚，而无需尝试测试是否具有非攻击性。 这是一个易于计算的上限，并且将导致您最初从明显的贪婪选择开始，试图抓住最大的可用引脚。