artificial-intelligence - 什么是狗定位问题的良好状态空间？

Question

假设我们有一个 M*N 迷宫，并且在这个迷宫的不同单元格中有 K 只狗在寻找它们的房子（它们独特的房子也位于迷宫中的某个单元格中）。在每一步中，所有的狗都可以留在他们的位置或移动到迷宫中的相邻单元（符合条件的移动是：如果可能的话，向上、向下、向右、向左）。什么是解决这个问题的好状态空间？

• 独特的房子意味着每只狗在迷宫的某个地方都有自己的房子。

• 两只狗也可以站在同一个牢房里。

我个人认为每只狗到它家的曼哈顿距离之和可能是一个很好的启发式方法，但我自己无法定义一个好的状态空间。

以下是 k=2 和 5*5 迷宫示例图片的链接： 示例

标签： artificial-intelligencestate-space

Answer 1

因为所有的动物都是独立的（它们不会互相阻挡，并且它们有独特的个人目标），所以您不应该对所有代理之间的联合行动进行建模。您实际上是在解决 K 个独立的寻路问题，其中每个人都可以单独使用曼哈顿距离启发式，给定 4 个连接的运动。如果您共同解决它们，那么您会在不必要的情况下使问题成倍增加。

有很多方法可以构建更好的启发式或重用搜索信息，但这是一个不同的问题。