加权图中的寻路游戏

Question

我想知道一个与图的探索相关的优化问题:假设我们有一个连通的加权图，每个顶点与其他顶点之间有1到4个连接。现在假设一些顶点包含巧克力，我们将两个学生放在两个不同的顶点上，他们都由两个人工智能控制，这两个人工智能可以访问巧克力的位置，另一个学生的位置和图形，在每个转弯，他们都可以移动到一个连接的顶点(如果边的权重是K，则需要K个移动)。最后，如果一个学生在一个含有巧克力的顶点上，他就会吃巧克力。我的问题是:对于人工智能来说，最好的算法是什么，这样受控的学生会比另一个人吃更多的巧克力？

谢谢你。

Answer 1

最好的方法可能是使用成本分析和启发式方法。你的机器人有1-4个选择，所以你应该考虑每一个选择。往上走有什么好处？费用是多少？如果你将值作为benefit - cost，那么你应该选择最有价值的选项。

所以..。无论如何，你如何计算收益和成本呢？您已经概述了一些条件。K值是一种成本。有没有巧克力是有好处的。或者分析与给定顶点相邻的巧克力的数量？

但是等等！你知道敌人的位置，你的敌人也知道你的位置！如果你在一个给定的方向上移动，它会影响他们的移动(如果他们很聪明的话)。因此，你必须向前看，分析你的敌人可能会对你做出什么反应。国际象棋解算器使用广度优先的先行计划，通过这个确切的系统规划出可能的最佳走法。不幸的是，你的问题是无界的--没有真正的成功条件。因此，您的机器人将无限期地向前看(或者，无论如何，直到它耗尽内存为止)。这是一个问题，因为计算需要时间。国际象棋解算器通过施加时间限制来绕过这一点。当时间耗尽时，他们会采取他们发现的最好的行动。

现在，我已经给出了一个可以在其中工作的通用框架。您仍然需要对其进行组装。制定启发式的一部分是权衡你的成本和收益。也许与获得巧克力的好处相比，K的成本微不足道？也许不是呢？使用恒定系数来权衡成本和收益。

至于在网格中寻找方法，我会看看Dijkstra's algorithm或A* to move。

哦，在我忘记之前，这里有一篇关于graph traversal的维基百科文章。你可能会发现它很有用。