启发式A *搜索以收集2D网格中的最大硬币数量？

Question

给出NxM网格的描述（起始单元，目标单元，不可达单元，具有硬币的单元），使用A *路径查找算法从起始单元到目标单元遍历网格，而收集关于以下限制：

1- Use only horizontal and vertical movement, diagonal movement is not allowed.
2- Each cell can be visited at most once.
3- Each cell can have at most 1 coin. 
这里是一个例子（0表示一个空单元格，1表示一个有硬币的单元格，X表示一个不可达的单元格，S是起始单元格，D是目标单元格：]]]
S

，X，X，X，X，X，X，X

1，X，X，X，X，X，X，X

0，X，X，X，X，X，X，X

1，1

，1，X，X，0，1，0

0，X，0，X，X，0

，X，0

0，X，0，1

，1，1，X，1

0，1，0，X，X，X，X，D

最佳路径单元格为粗体。

[请注意，我对解决方案的实际实现不感兴趣，我只需要帮助找到合适的启发式函数来正确建模此问题。

给出NxM网格的描述（起始单元，目标单元，不可达单元，具有硬币的单元），使用A *路径查找算法从起始单元到... ...遍历网格。]] >

主要问题是定义适当的距离。

让状态成为网格中的位置+拾取的数量。

邻居很简单，相邻的正方形不是X

我们可能会冒充距离

d(a,b) = -(b.ones - a.ones)
[b.ones-a.ones是0或1（因为我们以曼哈顿的方式移动）]

• 因此，如果我们不选择1，则距离为0
• 但是如果我们选择1（同等的b，则距离为负有利于最小化：我们选择的越多，越好

  关于启发式方法，为了确保最佳解，我们需要允许h，并且可以通过以下方式定义h：h(s) = -56（您的网格为7x8），即：我们不能比选择所有1s更好（这确保了最低的成本）

  我们可能会更精确地采取

h(s) = 56 - s.ones
甚至
h(s) = numberOfOnesInTheGrid - s.ones
但是后面暗示我们事先知道有多少1s

Answer 1

主要问题是定义适当的距离。

让状态成为网格中的位置+拾取的数量。