我需要一些帮助来为以下问题找到一个好的启发式方法：
您将获得一个
R网格C和一个六面骰子。让start和end成为这个网格上的两个不同的单元格。找到一条从start到的路径，end使得当骰子沿着路径转动时，向上看的骰子面的总和是最小的。模具的起始方向如下（“2”朝南）：
我对这个问题建模的方法是将模具面的价值视为图中边的成本。图形的顶点具有以下形式(row, col, die)（即网格中的位置和骰子的当前状态/方向）。顶点的原因不仅仅是(row, col)因为您最终可能会在具有多个模具配置/方向的同一单元格上结束。
我使用 A* 来找到问题的解决方案；给出的答案是正确的，但效率不够。我已经确定问题出在我正在使用的启发式方法上。目前我正在使用曼哈顿距离，这显然是可以接受的。如果我将启发式乘以一个常数，它就不再可接受：它运行得更快，但并不总能找到正确的答案。
我需要一些帮助来找到比曼哈顿距离更好的启发式方法。
好吧，我将在这里添加我的评论，因为它比@larsmans 当前投票率最高的答案更优化 - 但是，我相信一定有更好的东西（因此是赏金）。
如果我将启发式乘以常数，则不再可接受
我能想到的最好的方法是(manhattenDistance/3)*6 + (manhattenDistance%3)，其中/是整数除法，%是 mod。这是有效的，因为在没有回溯的任何 3 次移动中，所有三个数字都是唯一的，所以我们可以得到的最小总和是 1+2+3 = 6 （%3 只是添加任何额外的非倍数三个动作）。
[编辑] 正如@GrantS 在上面的评论中指出的那样，我的启发式方法可以通过添加一个额外的1when来略微改进manhattenDistance%3 == 2。这很容易在没有条件的情况下完成： (manhattenDistance/3)*6 + (manhattenDistance%3)*3/2
主要编辑 3：证明最佳可接受启发式应该基于3.5m
3.5m从长远来看，沿着董事会旅行的平均成本必须接近m曼哈顿距离。因此，最好的可接受启发式应该3.5m加上或减去一些小常数。
这样做的原因是，每当你在一个方向移动时，x，比如说，从 face x1，下一次在同一方向移动，到 facex2必须满足x1 + x2 = 7。这是因为在垂直方向上的任何移动都会使面 x2 的方向保持不变。考虑从左到右旋转模具——无论你旋转多少次，正面和背面都保持不变。相反，如果您从前向后旋转模具，左右面保持不变。
通过一些示例最容易看到这一点（所有示例都从问题中的配置开始）
6
2453
1
在这里你可以看到我们从 开始y1=1，然后无论我们在 x 方向上移动多少次，下一个在 y 方向上的移动必须是y2=6，所以y1+y2=7. （同样在 x 方向，有 和 的简单配对2+5 = 7）4+3 = 7。
另一个例子是
35
26
14
在这个例子中，我们从 开始x1=1，然后无论我们在 y 方向上移动多少次，下一次在 x 方向上的移动都必须是x2=6。4+3=7（此外，我们在 y 方向和 x 方向上看到了 的配对2+5=7。我们知道在这种情况下，x 方向上的下一步移动必须是4，而 y 方向上的下一步移动必须是1。 )
这一切都假设它永远不值得回溯，但希望这可以被视为已读。
下面的原始帖子只是填写了一些关于3.5m应该如何调整估计值以考虑到它在短期内被击败的能力的细节。
作为旁注，正如我刚刚评论的 OP，A* 搜索可能根本不需要。简单地选择一条由 4 长水平部分和 4 长垂直部分组成的路径应该是有意义的，例如，这是最佳的。然后通过基于方向和 xy 偏移的搜索或查找表来弥补剩余部分。（但这个问题要求一个可接受的启发式，所以我要留下我的答案。）
主要编辑 2：总结原始实证工作，考虑以下评论
从长远来看，如上所述，您的平均每次移动成本为 3.5。这也可以在对以下数据的探索中凭经验看出。
这给出了一个天真的估计曼哈顿距离3.5m在哪里。m然而，这是一个高估，因为在短期内有可能做得比平均水平更好。一个很好的假设是探索我们如何避免使用任何大于 3 的面。
3.5m预测的要好。3.5m3.5m3.5m正如 BlueRaja - Danny Pflughoeft 所建议的，这个假设可以通过简单地运行下面的脚本来验证每个骰子的起始可能性。所以一个简单的可接受的统计量是3.5m - k, where k = max(f+1, 4.5), 和f是起始面。但这有点笨拙，为 的小值给出负数m。编写一个程序化版本很容易，它考虑到你是否只有 1 步或 2 步或 3 步要走，见下文
static double Adm(int x, int y, int face /* start face */, out int m)
{
double adm = 0;
m = Math.Abs(x) + Math.Abs(y);
if (m >= 1) {
if (face == 1)
adm += 2;
else
adm += 1;
m--;
}
if (m >= 1) {
if (face <= 2)
adm += 3;
else
adm += 2;
m--;
}
if (m >= 1 && face >=4) {
// 4,5,6: we can still use a 3 without backtracking
adm += 3;
m--;
}
adm += 3.5 * m;
return adm;
}
在搜索空间中运行|x|,|y| <= 100此函数，此函数将实际成本低估了 0 到 6 之间，中位数为 0.5 或 1.5，具体取决于起始面。
主要编辑1：原始帖子
我的基本想法是探索数据会很好。所以我尝试了Dijkstra 的算法，看看解决方案的空间是什么样的。我发现支持已经说过的话。曼哈顿距离的某些倍数是合适的，但对于高于 1.5 的因子可能有一些理由。成本与初始 xy 位置偏差的等值线图形状很好地表明了这一点。
这是一个线框图——老实说，这只是为了吸引眼球。
有趣的是，如果您在数据中添加另一列曼哈顿距离 (man) 并将成本 (v) 与 R 中的曼哈顿距离进行回归，您会得到以下结果
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) -0.6408087 0.0113650 -56.38 <2e-16
df$man 3.4991861 0.0001047 33421.66 <2e-16
也就是说，它告诉您，对于您在水平或垂直方向上的每一步，您的成本是 3.4991861，或接近 3.5。这恰好是 1 到 6 的平均值，所以我的直觉是数据告诉我们，平均而言，在长距离内平均使用模具的所有面是最有效的。在短距离内，您可以更优化。
我试过3.5man - k作为估计，用k = 2.5. 这似乎工作正常。当我从中减去实际成本时，我得到 -0.5 作为最高值。
> summary(df$est - df$v)
Min. 1st Qu. Median Mean 3rd Qu. Max.
-6.500 -2.500 -2.000 -1.777 -1.000 -0.500
然而，A* 搜索必须适用于所有配置，包括那些在开始后芯片不在原始配置中的配置，因此常数k不能像2.5一般情况下那么低。如另一个答案中所建议的，它要么需要提高，例如4，要么取决于模具的配置。
我很可能在这一切中犯了一些可怕的错误，所以我把代码放在下面。就像我说的，我认为生成数据并对其进行调查的方法是合理的，即使我的结果不是。
这是结果文件的一些行。
17,-100,410
17,-99,406
17,-98,403
17,-97,399
17,-96,396
C# 代码
class Die
{
int top;
int bottom;
int front;
int back;
int left;
int right;
public int Top { get { return top; } }
public int Bottom { get { return bottom; } }
public int Front { get { return front; } }
public int Back { get { return back; } }
public int Left { get { return left; } }
public int Right { get { return right; } }
public Die(int top, int bot, int fro, int bac, int lef, int rig)
{
this.top = top;
bottom = bot;
front = fro;
back = bac;
left = lef;
right = rig;
}
public Die RotateLeft()
{
return new Die(
top: right,
rig: bottom,
bot: left,
lef: top,
fro: front,
bac: back
);
}
public Die RotateRight()
{
return new Die(
rig: top,
top: left,
lef: bottom,
bot: right,
fro: front,
bac: back
);
}
public Die RotateUp()
{
return new Die(
top: front,
fro: bottom,
bot: back,
bac: top,
lef: left,
rig: right
);
}
public Die RotateDown()
{
return new Die(
fro: top,
top: back,
bac: bottom,
bot: front,
lef: left,
rig: right
);
}
}
class DieXY
{
public Die Die { get; set; }
public int X { get; set; }
public int Y { get; set; }
public DieXY(Die die, int x, int y) { Die = die; X = x; Y = y; }
public override int GetHashCode() { return Die.Top + Die.Bottom*6 + Die.Front*6^2 + Die.Back*6^3 + Die.Left*6^4 + Die.Right*6^5 + X*6^6 + Y*6^8; }
public override bool Equals(object obj)
{
DieXY die = (DieXY)obj;
return die != null
&& die.Die.Top == Die.Top && die.Die.Bottom == Die.Bottom
&& die.Die.Front == Die.Front && die.Die.Back == Die.Back
&& die.Die.Left == Die.Left && die.Die.Right == Die.Right
&& die.X == X && die.Y == Y;
}
}
class Program
{
static void Main(string[] args)
{
Dictionary<DieXY, int> dict = new Dictionary<DieXY, int>();
int n = 100;
int sofar = -1;
DieXY root = new DieXY(new Die(1, 6, 2, 5, 4, 3), 0, 0);
Queue<Tuple<DieXY, int>> queue = new Queue<Tuple<DieXY, int>>();
queue.Enqueue(new Tuple<DieXY,int>(root,0));
while (queue.Count > 0)
{
Tuple<DieXY, int> curr = queue.Dequeue();
DieXY dieXY = curr.Item1;
Die die = dieXY.Die;
int x = dieXY.X;
int y = dieXY.Y;
if (Math.Max(x,y) > sofar)
{
sofar = Math.Max(x, y);
Console.WriteLine("{0}", sofar);
}
int score = curr.Item2;
if (Math.Abs(x) <= n && Math.Abs(y) <= n)
{
int existingScore = 0;
if (!dict.TryGetValue(dieXY, out existingScore)
|| score < existingScore)
{
dict[dieXY] = score;
Die newDie = null;
newDie = die.RotateLeft();
queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x - 1, y), score + newDie.Top));
newDie = die.RotateRight();
queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x + 1, y), score + newDie.Top));
newDie = die.RotateUp();
queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x, y + 1), score + newDie.Top));
newDie = die.RotateDown();
queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x, y - 1), score + newDie.Top));
}
}
}
int[,] scores = new int[2*n+1,2*n+1];
for (int aX = 0; aX < 2 * n + 1; aX++)
for (int aY = 0; aY < 2 * n + 1; aY++)
scores[aX, aY] = int.MaxValue;
foreach (KeyValuePair<DieXY, int> curr in dict)
{
int aX = curr.Key.X + n;
int aY = curr.Key.Y + n;
if (curr.Value < scores[aX, aY])
{
scores[aX, aY] = curr.Value;
}
}
using (System.IO.StreamWriter file = new System.IO.StreamWriter("out.csv"))
{
file.WriteLine("x,y,v");
for (int aX = 0; aX < 2*n+1; aX++)
{
int x = aX - n;
for (int aY = 0; aY < 2 * n + 1; aY++)
{
int y = aY - n;
file.WriteLine("{0},{1},{2}", x, y, scores[aX, aY]);
}
}
}
Console.WriteLine("Written file");
Console.ReadKey();
}
}
下面的R代码
library(lattice)
df = read.csv("out.csv")
df=transform(df, man=abs(x)+abs(y))
v50=df[abs(df$x)<=50 & abs(df$y)<=50,]
with(v50, wireframe(v ~ x*y))
with(v50, contourplot(v ~ x*y))
summary(lm(df$v ~ df$man))
df$est = df$man * 3.5 - 2.5
summary(df$est - df$v)
如果我将启发式乘以常数，则不再可接受
如果您摆脱了一些极端情况，则可能是这样。设d为曼哈顿距离，并观察骰子在路径的两个后续步骤中永远不会使其 1 面朝上。因此，如果您还没有达到目标：
所以一个可接受的启发式是
if d == 0 then
h := 0
else if die == 1 or die == 6 then
h := 2 + 1.5 × (d - 1)
else
h := 1 + 1.5 × (d - 1)
这是我的算法应用于 Paul 的 300x300 网格示例，从 (23,25) 开始，到 (282, 199) 结束。它在 0.52 秒内找到最小路径和总和（1515，比 Paul 的结果 1517 少 2 个点）。使用查找表而不是计算小部分的版本需要 0.13 秒。
哈斯克尔代码：
import Data.List (minimumBy)
import Data.Ord (comparing)
import Control.Monad (guard)
rollDie die@[left,right,top,bottom,front,back] move
| move == "U" = [left,right,front,back,bottom,top]
| move == "D" = [left,right,back,front,top,bottom]
| move == "L" = [top,bottom,right,left,front,back]
| move == "R" = [bottom,top,left,right,front,back]
dieTop die = die!!2
--dieStartingOrientation = [4,3,1,6,2,5] --left,right,top,bottom,front,back
rows = 300
columns = 300
paths (startRow,startColumn) (endRow,endColumn) dieStartingOrientation =
solve (dieTop dieStartingOrientation,[]) [(startRow,startColumn)] dieStartingOrientation where
leftBorder = max 0 (min startColumn endColumn)
rightBorder = min columns (max startColumn endColumn)
topBorder = endRow
bottomBorder = startRow
solve result@(cost,moves) ((i,j):pathTail) die =
if (i,j) == (endRow,endColumn)
then [(result,die)]
else do
((i',j'),move) <- ((i+1,j),"U"):next
guard (i' <= topBorder && i' >= bottomBorder && j' <= rightBorder && j' >= leftBorder)
solve (cost + dieTop (rollDie die move),move:moves) ((i',j'):(i,j):pathTail) (rollDie die move)
where next | null pathTail = [((i,j+1),"R"),((i,j-1),"L")]
| head pathTail == (i,j-1) = [((i,j+1),"R")]
| head pathTail == (i,j+1) = [((i,j-1),"L")]
| otherwise = [((i,j+1),"R"),((i,j-1),"L")]
--300x300 grid starting at (23, 25) and ending at (282,199)
applicationNum =
let (r,c) = (282-22, 199-24)
numRowReductions = floor (r/4) - 1
numColumnReductions = floor (c/4) - 1
minimalR = r - 4 * fromInteger numRowReductions
minimalC = c - 4 * fromInteger numColumnReductions
in (fst . fst . minimumBy (comparing fst) $ paths (1,1) (minimalR,minimalC) [4,3,1,6,2,5])
+ 14*numRowReductions + 14*numColumnReductions
applicationPath = [firstLeg] ++ secondLeg ++ thirdLeg
++ [((0,["R"]),[])] ++ [minimumBy (comparing fst) $ paths (1,1) (2,4) die2]
where
(r,c) = (282-22, 199-24) --(260,175)
numRowReductions = floor (r/4) - 1
numColumnReductions = floor (c/4) - 1
minimalR = r - 4 * fromInteger numRowReductions
minimalC = c - 4 * fromInteger numColumnReductions
firstLeg = minimumBy (comparing fst) $ paths (1,1) (minimalR,minimalC) [4,3,1,6,2,5]
die0 = snd firstLeg
secondLeg = tail . foldr mfs0 [((0,["R"]),die0)] $ [1..numColumnReductions - 1]
die1 = snd . last $ secondLeg
thirdLeg = tail . foldr mfs1 [((0,[]),die1)] $ [1..numRowReductions - 3 * div (numColumnReductions - 1) 4 - 1]
die2 = rollDie (snd . last $ thirdLeg) "R"
mfs0 a b = b ++ [((0,["R"]),[])] ++ [minimumBy (comparing fst) $ paths (1,1) (4,4) (rollDie (snd . last $ b) "R")]
mfs1 a b = b ++ [((0,["U"]),[])] ++ [minimumBy (comparing fst) $ paths (1,1) (4,1) (rollDie (snd . last $ b) "U")]
输出：
*Main> applicationNum
1515
*Main> applicationPath
[((31,["R","R","R","R","U","U","R","U","R"]),[5,2,1,6,4,3])
,((0,["R"]),[]),((25,["R","R","R","U","U","U"]),[3,4,1,6,5,2])
,((0,["R"]),[]),((24,["R","U","R","R","U","U"]),[5,2,1,6,4,3])
................((17,["R","R","R","U"]),[5,2,1,6,4,3])]
(0.52 secs, 32093988 bytes)
“R”和“U”列表：
*Main> let listRL = concatMap (\((a,b),c) -> b) applicationPath
*Main> listRL
["R","R","R","R","U","U","R","U","R","R","R","R","R","U","U","U","R","R","U","R"
..."U","R","R","R","R","U"]
使用起始骰子和“R”和“U”列表的路径总和：
*Main> let sumPath path = foldr (\move (cost,die) -> (cost + dieTop (rollDie die move), rollDie die move)) (1,[4,3,1,6,2,5]) path
*Main> sumPath listRL
(1515,[5,2,1,6,4,3])
使用“R”和“U”列表计算（因为我们(r,c)从(1,1)开始(1,1,)，(r,c)调整为(282-22, 199-24)：
*Main> let rc path = foldr (\move (r,c) -> if move == "R" then (r,c+1) else (r+1,c)) (1,1) path
*Main> rc listRL
(260,175)
算法/解决方案
Continuing the research below, it seems that the minimal face-sum path (MFS)
can be reduced, mod 4, by either rows or columns like so:
MFS (1,1) (r,c) == MFS (1,1) (r-4,c) + 14, for r > 7
== MFS (1,1) (r,c-4) + 14, for c > 7
This makes finding the number for the minimal path straightforward:
MFS (1,1) (r,c) =
let numRowReductions = floor (r/4) - 1
numColumnReductions = floor (c/4) - 1
minimalR = r - 4 * numRowReductions
minimalC = c - 4 * numColumnReductions
in MFS (1,1) (minimalR,minimalC) + 14*numRowReductions + 14*numColumnReductions
minimalR and minimalC are always less than eight, which means we can easily
pre-calculate the minimal-face-sums for these and use that table to quickly
output the overall solution.
但是我们如何找到路径呢？
根据我的测试，结果似乎类似：
MFS (1,1) (1,anything) = trivial
MFS (1,1) (anything,1) = trivial
MFS (1,1) (r,c), for r,c < 5 = calculate solution in your favorite way
MFS (1,1) (r,c), for either or both r,c > 4 =
MFS (1,1) (minimalR,minimalC) -> roll ->
MFS (1,1) (min 4 r-1, min 4 c-1) -> roll ->
...sections must be arranged so the last one includes
four rotations for one axis and at least one for the other.
keeping one row or column the same till the end seems to work.
(For Paul's example above, after the initial MFS box, I moved in
fours along the x-axis, rolling 4x4 boxes to the right, which
means the y-axis advanced in threes and then a section in fours
going up, until the last box of 2x4. I suspect, but haven't checked,
that the sections must divide at least one axis only in fours for
this to work)...
MFS (1,1) (either (if r > 4 then 4 else min 2 r, 4)
or (4, if c > 4 then 4 else min 2 c))
=> (r,c) is now reached
例如，
MFS (1,1) (5,13) = MFS (1,1) (1,5) -> roll right ->
MFS (1,1) (1,4) -> roll right -> MFS (1,1) (5,4)
MFS (1,1) (2,13) = MFS (1,1) (1,5) -> roll right ->
MFS (1,1) (1,4) -> roll right -> MFS (1,1) (2,4)
经验测试中观察到的骰子属性
For target points farther than (1,1) to (2,3), for example (1,1) to (3,4)
or (1,1) to (4,6), the minimum path top-face-sum (MFS) is equal if you
reverse the target (r,c). In other words:
1. MFS (1,1) (r,c) == MFS (1,1) (c,r), for r,c > 2
不仅。
2. MFS (1,1) (r,c) == MFS (1,1) (r',c'), for r,c,r',c' > 2 and r + c == r' + c'
e.g., MFS (1,1) (4,5) == MFS (1,1) (5,4) == MFS (1,1) (3,6) == MFS (1,1) (6,3)
但有趣的是：
The MFS for any target box (meaning from startPoint to endPoint) that
can be reduced to a symmetrical combination of (r,c) (r,c) or (r,c) (c,r), for
r,c > 2, can be expressed as the sum of the MFS of the two smaller symmetrical
parts, if the die-roll (the change in orientation) between the two parts is
accounted for. In other words, if this is true, we can breakdown the calculation
into smaller parts, which is much much faster.
For example:
Target-box (1,1) to (7,6) can be expressed as:
(1,1) (4,3) -> roll right -> (1,1) (4,3) with a different starting orientation
Check it, baby:
MFS (1,1) (7,6) = MFS (1,1) (4,3) + MFS (1,1) (4,3)
(when accounting for the change in starting orientation, rolling right in
between)
Eq. 2., implies that MFS (1,1) to (7,6) == MFS (1,1) (5,8)
and MFS (1,1) (5,8) can be expressed as (1,1) (3,4) -> roll right -> (1,1) (3,4)
Check it again:
MFS (1,1) (7,6) = MFS (1,1) (5,8) = MFS (1,1) (3,4) + MFS (1,1) (3,4)
(when accounting for the change in starting orientation, rolling right in
between)
不仅。
The symmetrical parts can apparently be combined in any way:
3. MFS (1,1) (r,c) -> roll-right -> MFS (1,1) (r,c) equals
MFS (1,1) (r,c) -> roll-right -> MFS (1,1) (c,r) equals
MFS (1,1) (r,c) -> roll-up -> MFS (1,1) (r,c) equals
MFS (1,1) (r,c) -> roll-up -> MFS (1,1) (c,r) equals
MFS (1,1) (2*r-1, 2*c) equals
MFS (1,1) (2*r, 2*c-1), for r,c > 2
主意：
如果你必须直线移动，你能做的最好的就是以 1 和 2 结束你的移动，对于所有其他移动，你不能做得比 更好3.5*distance。
启发式：
可以使用ManhattanDistance = x + y以下启发式方法：
Heuristic = xH + yH;
在哪里
xH = calculateStraightLineHeuristic(x)
yH = calculateStraightLineHeuristic(y)
函数calculateStraightLineHeuristic(z)定义如下：
calculateStraightLineHeuristic(z)
if (z = 1)
return zH = 1
elseif (z = 2)
return zH = 2+1
else
return zH = (z-2)*3.5+2+1
end