A*允许的启发式在网格上滚动

Question

我需要一些帮助找到一个良好的启发式解决以下问题:

您将得到一个R-by- C网格和六面的骰子.设start和 end是在这个网格两种截然不同的细胞.找到一条路径start,end使得当模具沿路径转动时,模具面朝上的总和是最小的.

模具的起始方向如下("2"朝南):

我模拟这个问题的方法是将模具的面值视为图形中边缘的成本.图形的顶点具有形式(row, col, die)(即,网格中的位置和模具的当前状态/方向).顶点不是简单的原因(row, col)是因为你可以使用骰子的多个配置/方向结束相同的单元格.

我用A*来找到问题的解决方案; 给出的答案是正确的,但效率不高.我已经确定问题是我正在使用的启发式问题.目前我正在使用曼哈顿距离,这显然是可以接受的.如果我将启发式乘以常量,则不再允许:它运行得更快,但并不总能找到正确的答案.

我需要一些帮助才能找到比曼哈顿距离更好的启发式方法.

Answer 1

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

如果我将启发式乘以常数,则不再允许

我能想到的最好的是(manhattenDistance/3)*6 + (manhattenDistance%3),/整数除法在哪里,%是mod.这是有效的,因为在没有反向跟踪的任何3个动作中,所有三个数字都是唯一的,所以我们可以得到的最低总和是1 + 2 + 3 = 6 (%3简单地添加任何额外的,非多个 -三招).

[编辑] 正如@GrantS在上面的评论中指出的那样,通过添加额外的1时间可以略微改善我的启发式manhattenDistance%3 == 2.没有条件,这很容易做到: (manhattenDistance/3)*6 + (manhattenDistance%3)*3/2

Answer 2

主编辑3:证明最佳可接受启发式应该基于 3.5m

3.5m从长远来看,沿着董事会旅行的平均成本必须接近m曼哈顿距离.因此,最佳允许启发式应该是3.5m正或负一些小常数.

这样做的原因是,无论何时你向一个方向移动,比如说,从脸部x1移动,下一步向相同方向移动,面对x2必须满足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方向上,2+5=7在x方向上的配对.我们知道在这种情况下,x方向上4的下一个移动必须是,并且y方向上的下一个移动必须是1. )

这一切都假设它永远不值得回溯,但希望这可以作为阅读.

下面的原始帖子只是填写了一些细节,说明3.5m应该如何调整估计值,以考虑到它在短期内被击败的能力.

作为旁注,正如我刚刚对OP进行评论,可能根本不需要A*搜索.简单地选择由4长水平件和4长垂直件组成的路径应该是有意义的,比如说,这是最佳的.然后使用基于方向和xy偏移的搜索或查找表来构成余数.(但问题是要求允许的启发式,所以我要留下我的答案.)

主要编辑2:总结原始的实证工作,考虑下面的评论

从长远来看,如上所述,您的平均每次移动费用为3.5.在探索下面的数据时,这也可以凭经验看出.

这给出了曼哈顿距离3.5m在哪里的天真估计m.然而,这是一个过高估计,因为在短期内是可以做到比一般的要好.一个很好的假设是探索如何避免使用任何大于3的面.

• 如果我们从面部1开始,我们可以在前2个动作中使用面部2和3,比预测更好地进行2次移动3.5m.
• 如果我们从面部2开始,我们可以在前两个动作中使用面部1和3,比预测更好地进行3次移动3.5m.
• 如果我们从第3面开始 ,我们可以在前2个动作中使用面1和2,比预测更好地进行4次动作3.5m.
• 如果我们从面部 4,5或6开始,我们可以在前3个移动中使用面1,2和3,比预测更好地移动4.5个移动3.5m.

正如BlueRaja - Danny Pflughoeft所建议的那样,这个假设可以通过简单地运行下面的脚本来确认死亡的每个起始可能性,从而凭经验证实.因此,一个简单的可接受的统计数据是3.5m - k,在哪里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)

Answer 3

如果我将启发式乘以常数,则不再允许

如果你摆脱一些角落案件就可以了.设d是曼哈顿距离,并观察到骰子在路径的两个后续步骤中永远不会让它面朝上.因此,如果你还没有达到目标:

• 第一步成本至少为1;
• 如果1面朝上,则至少为2(同样适用于6);
• 路径的其余部分至少与一系列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)

Answer 4

这是我的算法应用于Paul的300x300网格示例,从(23,25)开始到(282,199)结束.它在0.52秒内找到最小路径和总和(1515,比保罗1517的结果小2点).具有查找表而不是计算小部分的版本花费0.13秒.

Haskell代码:

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)from (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