algorithm - A* Admissible Heuristic for die rolling on grid 网格上的模具滚动

Question

我需要一些帮助来为以下问题找到一个好的启发式方法:

You are given an R-by-C grid and a six-sided die. Let start and end be two distinct cells on this grid. Find a path from start to end such that the sum of the faces of the die looking up, as the die is turning along the path, is minimal.

The starting orientation of the die is the following (the "2" is facing south):

我对这个问题建模的方法是将骰子面的值视为图中边的成本。图的顶点的形式为 (row, col, die)(即，网格中的位置和骰子的当前状态/方向)。顶点不是简单的 (row, col) 的原因是因为您可以在同一个单元格上使用多个配置/方向的模具。

我用A*找到了问题的解决方案；给出的答案是正确的，但效率不够。我确定问题出在我正在使用的启发式方法上。目前我正在使用曼哈顿距离，这显然是可以接受的。如果我将启发式乘以一个常数，它就不再是可接受的:它运行得更快，但并不总能找到正确的答案。

我需要一些帮助来找到比曼哈顿距离更好的启发式算法。

Answer 1

好吧，我会在这里添加我的评论，因为它比@larsmans 当前投票最高的答案更优化 - 但是，我相信一定有更好的东西(因此有赏金)。

---

If I multiply the heuristic with a constant, it's no longer admissible

我能想到的最好的是 (manhattenDistance/3)*6 + (manhattenDistance%3)，其中 / 是整数除法，% 是模组。这是可行的，因为在没有回溯的任何 3 次移动中，所有三个数字都是唯一的，所以我们可以拥有的最低总和是 1+2+3 = 6 (%3 只是添加任何额外的非倍数三步法)。

---

[编辑] 正如@GrantS 在上面的评论中指出的那样，当 manhattenDistance%3 = = 2。如果没有条件，这很容易做到:(manhattenDistance/3)*6 + (manhattenDistance%3)*3/2