用于 A* 搜索的启发式以收集 2D 网格中的最大硬币数？
Heuristic for A* search to collect the maximum number of coins in a 2D grid?
给定 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 , 0 , 0 , 0 , 0 , D
最佳路径单元格是粗体。
请注意，我对解决方案的实际实施不感兴趣，我只想帮助找到合适的启发式函数来正确建模此问题。
tldr； A* 和最大化个数：可能但不好
第一个问题是定义适当的距离。
让状态为网格中的位置+被选中的数量。
邻居很简单，相邻的方块不是X
我们可以摆出远距离的姿势
d(a,b) = -(b.ones - a.ones)
- 所以对于邻居b，如果我们选择一个1，距离是-1
- 如果没有选择则 0
最小化 d 将产生最大数 1。
关于启发式，为了确保最佳解决方案，我们需要 h 可接受的，我们可以定义 h
h(s) = -56（您的网格是 7x8）、h(s) = 56 - s.ones 甚至 h(s) = numberOfOnesInTheGrid - s.ones
（虽然后者意味着我们事先知道有多少1s）
然而 这不适合 A* 因为：
- 我们想探索 所有 paths/states 当 A* 的目标是避免...
- 我们将自己暴露在循环中（我们会贪婪地吃到……很久）。这是有症状的，不会发生在最短路径问题（具有正加权边）中，因为 循环 总是导致更长的路径被丢弃
- 我们想要的本质上是最长路径问题而不是最短路径问题（例如到 D 的欧氏距离与最大化 1 的数量（或条件为 1 的访问状态的数量））。
恐怕A*不会有满意的结果。
显示问题的更简单的网格（从您的示例中提取）：
0 , 1 , 0
0 , X , 0
S , X , 1
0 , 0 , D
上面的路径较长（就访问的方块而言）但是是最佳路径
您始终可以通过将访问过的 path/states 存储到每个状态（以避免循环）来强制执行 A*，但您也可以只使用具有启发式的 dfs，首先使用 1
给定 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 , 0 , 0 , 0 , 0 , D
最佳路径单元格是粗体。
请注意，我对解决方案的实际实施不感兴趣，我只想帮助找到合适的启发式函数来正确建模此问题。
tldr； A* 和最大化个数：可能但不好
第一个问题是定义适当的距离。
让状态为网格中的位置+被选中的数量。
邻居很简单，相邻的方块不是X
我们可以摆出远距离的姿势
d(a,b) = -(b.ones - a.ones)
- 所以对于邻居b，如果我们选择一个1，距离是-1
- 如果没有选择则 0
最小化 d 将产生最大数 1。
关于启发式，为了确保最佳解决方案，我们需要 h 可接受的，我们可以定义 h
h(s) = -56（您的网格是 7x8）、h(s) = 56 - s.ones 甚至 h(s) = numberOfOnesInTheGrid - s.ones
（虽然后者意味着我们事先知道有多少1s）
然而 这不适合 A* 因为：
- 我们想探索 所有 paths/states 当 A* 的目标是避免...
- 我们将自己暴露在循环中（我们会贪婪地吃到……很久）。这是有症状的，不会发生在最短路径问题（具有正加权边）中，因为 循环 总是导致更长的路径被丢弃
- 我们想要的本质上是最长路径问题而不是最短路径问题（例如到 D 的欧氏距离与最大化 1 的数量（或条件为 1 的访问状态的数量））。
恐怕A*不会有满意的结果。 显示问题的更简单的网格（从您的示例中提取）：
0 , 1 , 0
0 , X , 0
S , X , 1
0 , 0 , D
上面的路径较长（就访问的方块而言）但是是最佳路径
您始终可以通过将访问过的 path/states 存储到每个状态（以避免循环）来强制执行 A*，但您也可以只使用具有启发式的 dfs，首先使用 1