A *在网格上滚动的容许启发式
我需要一些帮助为以下问题find一个好的启发式：
给你一个
Rby-C格子和一个六面骰子。 让start和end在这个网格上是两个不同的单元格。 从头到尾找出一条path，使得当死亡沿path转向时，抬头的面的总和最小。模具的起始方向如下（“2”朝南）：
我模拟这个问题的方式是将模具面部的价值作为graphics边缘的成本。 graphics的顶点的forms是(row, col, die) （即网格中的一个位置和die的当前状态/方向）。 顶点不是简单的(row, col)的原因是因为你可以结束在同一个单元与多个configuration/方向的骰子。
我用A *find解决问题的办法; 给出的答案是正确的，但效率不够高。 我确定问题是我正在使用的启发式。 目前我使用曼哈顿距离，显然是可以接受的。 如果我将启发式乘以一个常量，那么它就不再是可以接受的了：它的运行速度要快得多，但并不总能find正确的答案。
我需要一些帮助来find一个比曼哈顿距离更好的启发式。
这是我的algorithm，应用于Paul的300×300网格，从（23,25）开始到（282,199）结束。 它在0.52秒内find最小path和总和（1515，比保罗1517年的结果less2分）。 一个带查找表的版本，而不是计算小部分花了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 ab = b ++ [((0,["R"]),[])] ++ [minimumBy (comparing fst) $ paths (1,1) (4,4) (rollDie (snd . last $ b) "R")] mfs1 ab = 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"]
使用起始模具的path和“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”（从我们在(1,1,) ， (r,c)开始的列表(r,c)计算(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)
algorithm/解决scheme
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.
但是，我们如何findpath呢？
从我的testing看来，似乎也是这样：
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' eg, 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
那么，我会在这里加上我的评论，因为它比@larsmans现在最高的答案更为理想 – 但是我相信肯定有更好的东西（因此是赏金）。
如果我将启发式乘以一个常数，那么它就不再是可接受的了
我能想出最好的是(manhattenDistance/3)*6 + (manhattenDistance%3) ，其中/是整数除法， %是mod。 这是有效的，因为在任何3次移动中没有回溯，所有三个数字都是唯一的，所以我们可以得到的最低总和是1 + 2 + 3 = 6 （％3只是增加了任何额外的，三招） 。
正如@GrantS在上面的评论中指出的那样，当manhattenDistance%3 == 2时，我的启发式可以通过增加一个额外的1来改善。 这很容易做到没有条件： (manhattenDistance/3)*6 + (manhattenDistance%3)*3/2
主要编辑3：certificate最佳可接受启发式应该基于3.5m
从曼哈顿的距离来看，沿长途旅行的平均成本要达到3.5m m 。 因此最好的可接受的启发式应该是3.5m加上或减去一些小的常量。
原因是每当你朝一个方向移动时，例如从x1方向移动到下一个朝向x2方向的移动必须满足x1 + x2 = 7 。 这是因为在垂直方向上的任何移动都使得面x2的方向相同 。 想想从左到右旋转一个模子 – 无论你做了多less次旋转，前后面都保持不变。 相反，如果将模具正面向后旋转，则左侧和右侧的面保持不变。
用一些例子来看这个是最简单的（所有的问题都是从configuration开始的）
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 。 （此外，我们看到y方向上的4+3=7 ，x方向上的2+5=7配对，并且我们知道在这种情况下，x方向上的下一个移动必须是4 ，并且y方向的下一步必须是1 。
这一切都假设这是永远不值得回溯，但希望这可以被视为阅读。
下面的原始文章只是填补了一些细节，应该如何调整3.5m的估计，以考虑短期内被打败的能力。
作为一个侧面说明，正如我刚才评论的OP，A *search可能根本不需要。 简单地select由4长的水平片和4长的垂直片构成的path应该是有意义的，也就是说，这是最佳的。 然后根据方向和xy偏移量使用search或查找表来补足余数。 （但问题要求一个可接受的启发式，所以我要离开我的答案。）
主编辑2：总结原创实证工作，并考虑以下评论
从长远来看，如上所述，您的平均每次移动成本为3.5。 这在下面的数据的探索中也可以经验地看到。
这给出了一个天真的估计3.5m ，其中m是曼哈顿距离。 但这是一个高估，因为在短期内可能比平均水平做得更好。 一个好的假设是探索如何避免使用大于3的面。
- 如果我们从第一面开始，我们可以在前
3.5m使用第二面和第三面，比预测的3.5m更好。 - 如果我们从第二张脸开始，我们可以在前两次使用第一张和第三张脸，比
3.5m要好3.5m。 - 如果我们从第3张开始，我们可以在前两次使用面1和2，比预测的
3.5m好4次。 - 如果我们从第4,5或6张开始 ，我们可以在前3次移动中使用面1,2和3，移动速度比
3.5m快4.53.5m。
如BlueRaja – Danny Pflughoeft所build议的那样，这个假设可以通过简单地运行下面的脚本来证实。 所以一个简单的容许统计量是3.5m - k ，其中k = max(f+1, 4.5) ， f是起始面。 但是，这有点klunky，小数值为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在search空间中运行 |x|,|y| <= 100 ，这个函数低估了0到6之间的实际成本，取决于开始面的中间值为0.5或1.5。
主编辑1：原文
我的基本思想是，探索这些数据是一件好事。 所以我在Dijkstra的algorithm中去看看解决scheme的空间是什么样的。 我发现的是支持已经说过的话。 曼哈顿距离的某些因素乘以合适，但可能有一些理由认为更高的因子比1.5。 这很好地通过成本的等高线图的形状来表示，以避免偏离最初的xy位置。
这是一个线框图 – 说实话这只是眼睛的糖果。
有趣的是，如果在曼哈顿距离（man）的数据中添加另一列，并在R中对曼哈顿距离（v）进行回归，则可得到以下
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，或v接近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 *search必须适用于所有的configuration，包括在芯片不是原始configuration的开始之后，所以常数k一般不能低至2.5 。 或者需要提高，例如4 ，或者依赖于模具的configuration，正如另一个答案中所build议的那样。
我很可能犯了一个可怕的错误，所以我把代码放在下面。 就像我说的，我认为即使我的结果不是这样，生成数据和调查数据的方法也是合理的。
以下是结果文件的一些行。
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)
如果我将启发式乘以一个常数，那么它就不再是可接受的了
这可能是如果你摆脱了一些angular落案件。 假设d是曼哈顿距离，并且观察到死亡在path的两个后续步骤中永远不会有其面朝上。 因此，如果你还没有达到目标：
- 第一步至less花费1元;
- 如果1面朝上，那么至less有2个（并且持有6个）。
- 剩下的path至less和一系列1-2次交替一样昂贵，其成本是1.5×（ 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)
理念：
如果你必须直线移动，你所能做的最好的就是用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
