search - Pacman ai 项目 - 适合步骤成本和启发式的组合
问题描述
作为项目的一部分，我正在尝试在 pacman 游戏的上下文中实现 A*（请参阅 UC Berkley pacman ai 项目）。没有鬼或胶囊，只有迷宫和“水果”。但是，我在理解启发式函数和成本函数之间的关系时遇到了麻烦。
根据该项目，在定义搜索问题时，我们需要指定一个步骤成本，该成本源自：
score = -Nb Steps + 10*NbOfEatenDots + 200*NbOfEatenGhosts + (-500*isLoss) + (500*isWin)
该成本应该始终为正，因此，为简单起见，我决定采用：1.5 - (0.5*AteAFoodDot)。我忽略了幽灵和胶囊，因为它们不存在，并且我对最终吃掉一个点的动作给出了优先分数。我也忽略了导致失败的步骤（因为它们不存在）和导致胜利状态的步骤。
现在就 A* 算法本身而言，我们必须实现自己的成本函数和启发式函数：
作为我选择的成本函数：Cost = sum(step costs to current state)和作为启发式：h = Manhattan distance between pacman and the dot closest to him + manhattan distance of this dot and another dot that is furthest away from it, as long as it exists，这是一个可接受的启发式。我还使用真正的迷宫距离而不是曼哈顿距离实现了这种启发式方法，但这对于有很多食物点的迷宫来说似乎太耗时了。
现在，如果我正确理解g(n)了我的成本函数和h(n)启发式，我必须始终拥有：g(n to goal) >= h(n)这样 A* 总是返回最优路径，并且节点 n 的值g和值最接近h，将扩展更少的节点。
在这方面，忽略分数是如何计算的，忽略一个步骤是否会导致吃掉一个食物点这一事实，而只是采取step_cost = 1所有步骤，难道不符合我的利益吗？
这就是我在计算时间和扩展节点方面获得最佳结果的方式，但忽略游戏的成本函数似乎是错误的。
有人可以为我澄清一下吗？这是一个rpeference/选择的问题，还是有一个客观的正确答案/最佳方法？