我学习了A*、BFS和DFS算法,并且能够很好地实现它们。然而,在解决吃豆人寻路问题时,会遇到一些问题。假设迷宫只有两种类型:一种是所有空格都有元素,即没有空白方块,每个方块上要么是吃豆人,要么是要收集的物品,要么是墙;另一种只有少量物品(4个或更少)。
如果要收集多个物品,BFS和DFS应该如何实现?在这种情况下,它们是否仍然能够产生最优结果?
对于全有物品的地图来说,哪种算法/启发式函数最好呢?到目前为止,我想到的是一种贪心启发式函数,但由于地图上有太多要收集的物品,因此它非常随机,不是解决此类迷宫问题的好方法。
在使用A*算法处理只有几个物品的地图时,有没有一种好方法确定首先拿取哪个物品?我考虑过使用曼哈顿距离作为粗略估计,但在某些棘手的情况下,这似乎不正确。