我想知道一个与graph探索相关的优化问题：
假设我们有一个连通的加权图，每个顶点与其他顶点有1到4个连通。现在假设一些顶点包含巧克力，我们把这个图放在两个不同的顶点上，两个学生，都由两个ais控制，这两个ais可以访问巧克力的位置，另一个学生的位置和这个图，在每个回合，它们都可以移动到连接的顶点（如果边的权重为k，则需要k移动）。最后，如果学生在含有巧克力的顶点上，他会吃巧克力。
我的问题是：对于人工智能来说，什么样的算法才是最好的，这样受控制的学生会比其他人吃更多的巧克力？
谢谢您。
最佳答案
最好的方法可能是使用成本分析和启发式方法。
你的机器人有1-4个选择，所以你应该考虑每一个上去有什么好处费用是多少如果您将值设为benefit - cost，则应选择最有价值的选项。
所以你怎么计算收益和成本呢你已经概述了一些条件K值是一种成本有没有巧克力是有好处的。也许可以分析一个顶点附近的巧克力数量？
但是等等你知道敌人的位置，你的敌人也知道你的位置如果你朝一个特定的方向移动，它会影响他们的移动（如果他们聪明的话），所以你必须向前看，分析你的敌人可能会对你做出什么反应国际象棋解算者使用广度优先的展望，通过这个精确的系统规划出可能的最佳移动不幸的是，你的问题是无限的-没有真正的获胜条件所以你的机器人会无限期地向前看（或者，直到内存耗尽为止），这是个问题，因为计算需要时间。国际象棋解决者通过设定一个时间限制来解决这个问题。他们在时间不多的时候会采取最好的行动。
现在，我给了你一个总体框架。你还需要组装它启发法的一部分是衡量你的成本和收益。也许比起吃巧克力的好处来说，K的成本是微不足道的也许不是？使用常数系数来衡量成本和收益。
至于在网格中找到你的路，我会看一看Dijkstra's algorithm或A*来移动。
哦，在我忘记之前，这里有一篇关于graph traversal的维基百科文章你可能会发现它很有用。
关于algorithm - 加权图中的寻路游戏，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47538042/