algorithm - 加权图中的寻路游戏

Question

我想知道与图形探索相关的优化问题:假设我们有一个连接的加权图，每个顶点与其他顶点之间有 1 到 4 个连接。现在假设一些顶点包含巧克力，我们在两个不同的顶点上放置两个学生，他们都由两个 AI 控制，这两个 AI 可以访问巧克力的位置、另一个学生的位置和图表，并且在每个反过来，它们都可以移动到连接的顶点(如果边的权重为 K，则需要 K 移动)。最后，如果一个学生在一个包含巧克力的顶点上，他就会吃掉它。我的问题:AI 的最佳算法是什么，以便受控制的学生比其他学生吃更多的巧克力？

谢谢。

Answer 1

最好的方法可能是使用成本分析和启发式方法。您的机器人可以做出 1-4 种选择，因此您应该考虑每一种选择。上去有什么好处？费用是多少？如果您将值(value)视为 benefit - cost，那么您应该选择最有值(value)的选项。

所以...您甚至如何计算 yield 和成本？您已经概述了一些条件。 K 值是一个成本。有没有巧克力就有好处。也许分析与给定顶点相邻的巧克力数量？

但是等等!你知道你的敌人的位置，你的敌人也知道你的!如果您朝特定方向移动，它会影响他们的移动(如果他们聪明的话。)因此您必须向前看并分析您的敌人可能会对您做出什么 react 。国际象棋求解器使用广度优先前瞻来通过这个精确的系统计划出最佳可能的移动。不幸的是，你的问题是无限的——没有真正的胜利条件。所以你的机器人会无限期地向前看(或者，直到它用完内存，反正。)这是一个问题，因为计算需要时间。国际象棋解算器通过施加时间限制来解决这个问题。他们在时间用完时采取了他们找到的最佳着法。

现在，我已经为您提供了一个通用的工作框架。您仍然需要组装它。进行试探法的一部分是权衡您的成本和 yield 。也许 K 的成本与获得巧克力的好处相比微不足道？也许不是？使用常数系数来权衡成本和 yield 。

至于在网格中寻找出路，我会看一下 Dijkstra's algorithm或 A*移动。

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