algorithm - 以较低的成本将元素分配给多个目标的最佳方法是什么？

Question

我正在尝试找到以尽可能低的成本将元素分配给多个目标的最佳算法。

要激活目标(大写)，您需要使用 colour theory logic 的 1 或 2 个特定元素(小写) :

• 黄色需求:黄色
• 蓝色需求:蓝色
• RED 需求:红色
• 绿色需求:绿色或黄色+蓝色
• 橙色需求:橙色或黄色+红色
• VIOLET 需要:紫色或红色+蓝色

把这个问题想象成必须用一次性 key 打开的门。所有门都必须用 1 把相同颜色的 key 或 2 把原色 key 打开。 key 在迷宫中，成本是 key 到门的距离。

一旦您拥有包含所有可能组合的数组(非常简单的示例)并应用您拥有的算法:

//Doors: G (GREEN), B (BLUE), Y (YELLOW)
//Keys: b, (blue), y (yellow), g (green)
Input:
    [{Door: G,  Keys: [b,y], cost: 1},
     {Door: G,  Keys: [g],   cost: 10},
     {Door: B,  Keys: [b],   cost: 5},
     {Door: Y,  Keys: [y],   cost: 3}]

Output:
    [{Door: G,  Keys: [g],   cost: 10},
     {Door: B,  Keys: [b],   cost: 5},
     {Door: Y,  Keys: [y],   cost: 3}]
    Total cost: 18

(请注意，即使使用蓝色+黄色 key 打开绿色门的成本也较低(1)，它使用其他门所需的 2 把 key ，因此不能成为最终解决方案的一部分)

如果出现以下情况，这可能是找到成本更低的组合的最佳方法:

• 所有的门都需要 1 或 2 个成功的 key
• 没有必要使用所有的键
• 一个 key 只能使用一次

---

我在另一部分代码中使用了 A*，并且我已针对此建议对其进行了调整，但我认为它不够高效(我需要使用此算法数千次来解决迷宫问题)。我还探索了另一个 combinational optimization solutions ，但我不确定要使用哪个女巫。

任何帮助或方向将不胜感激。谢谢!

Answer 1

我第一次尝试提高速度是坚持使用您已有的分支定界解决方案(您的 A*)。

与国际象棋或围棋或类似的东西相比，这个问题可以用蛮力的方式解决。搜索树中的节点数量足够少，您可以将它们全部保存在内存中。

因此，我的第一个尝试是向您的 A* 添加一个转置表，它存储节点的已找到值。

我曾经写过一个程序来解决一个游戏(bunny bashing)。没有换位表，需要 10 秒才能解决。使用转置表，它在 35 毫秒内完成。

然后，可能会添加修剪技术(alpha beta，mayhaps)。

此外，它可能会加快用在树上运行的搜索算法替换 A*(在图上运行)的速度。