A * Heuristique admissible pour rouler sur une grille

Question

J'ai besoin d'aide pour trouver une bonne heuristique pour le problème suivant:

Vous êtes donné un R-par-C de la grille et de un à six côtés de mourir. Laissez - start et end de deux cellules distinctes sur cette grille. Trouver un chemin de start de end tels que la somme des faces de la filière, de la recherche, que le dé est en train de tourner sur le chemin, est minimes.

Le départ de l'orientation de la matrice est la suivante (le "2" est face au sud):

La façon dont je l'ai modélisé ce problème est d'étudier la valeur de la matrice du visage, comme le coût d'une arête du graphe. Le graphe de sommets sont de la forme (row, col, die) (j'.e, une position dans la grille et de l'état actuel et de l'orientation de la matrice). La raison d'un sommet n'est pas simplement (row, col) est parce que vous pouvez retrouver sur la même cellule avec plusieurs configurations/orientations de la filière.

J'ai utilisé Un* pour trouver la solution au problème; les réponses données sont correctes, mais il n'est pas assez efficace. J'ai déterminé que le problème est l'heuristique que j'utilise. Actuellement, je suis en utilisant une distance Manhattan, ce qui est évidemment recevable. Si je multiplie l'heuristique avec une constante, il n'est plus recevable: elle s'exécute beaucoup plus rapidement mais il n'est pas toujours à trouver la bonne réponse.

J'ai besoin d'aide dans la recherche d'une meilleure heuristique de distance Manhattan.

Answer 1

Eh bien, je vais ajouter mon commentaire ici, car il est plus optimal que le courant plus-voté réponse par @larsmans - mais, j'en suis convaincu, il doit y avoir quelque chose de mieux (d'où le bounty).

---

Si je multiplie l'heuristique avec une constante, il n'est plus recevable

Le mieux que je peux venir avec est - (manhattenDistance/3)*6 + (manhattenDistance%3)où / est la division entière et % mod. Cela fonctionne parce que dans tous les 3 se déplace avec pas de suivi, tous les trois chiffres sera unique, de sorte que le plus bas de la somme que nous pourrions avoir est 1+2+3 = 6 (L' %3 ajoute simplement supplémentaire, non multiple de trois mouvements).

---

[Edit] Comme @Subventions souligné dans les commentaires ci-dessus, mon heuristique peut être très légèrement amélioré par l'ajout d'un supplément de 1 lorsque manhattenDistance%3 == 2. C'est facile à faire sans une condition: (manhattenDistance/3)*6 + (manhattenDistance%3)*3/2

Answer 2

Principales Edit 3: Preuve que le meilleur recevable heuristique doit être fondée sur 3.5m

Le coût moyen d'un voyage le long de la conseil d'administration a pour approche 3.5m sur le long terme où l' m est la distance Manhattan. Par conséquent, la meilleure heuristique admissible devrait être 3.5m plus ou moins un petit constante.

La raison pour cela est que lorsque vous déplacez dans une direction, x, disons, de face - x1, le prochain déplacement dans la même direction, pour le visage x2 a pour satisfaire x1 + x2 = 7. C'est parce que tout se déplace dans la direction perpendiculaire quitter l'orientation de la face x2 le même. Penser à la rotation d'un die de gauche à droite-les faces avant et arrière restent les mêmes, peu importe le nombre de rotations que vous faites. Inversement, si vous faites une rotation de mourir avant à l'arrière, la gauche et la droite visages restent les mêmes.

Il est plus facile de voir cela avec quelques exemples (tous de départ dans la configuration illustrée à la question)

   6
2453
1

ici vous pouvez voir que nous commençons avec y1=1, et cependant de nombreuses fois de nous déplacer dans la direction x par la suite, le prochain déplacement dans la direction y a à être y2=6, alors y1+y2=7. (Également dans le sens des x, il existe un couplage simple d' 2+5 = 7 et 4+3 = 7).

Un autre exemple est

  35
 26
14

Dans cet exemple nous commençons x1=1, et cependant beaucoup de fois nous déplacer dans la direction y par la suite, le prochain déplacement dans la direction x doit être x2=6. (Aussi, nous voyons des paires d' 4+3=7 dans la direction y, 2+5=7 dans la direction x. Et nous savons dans ce cas, le prochain déplacement dans la direction x doit être 4, et le prochain déplacement dans la direction y a à être 1.)

Tout cela suppose qu'il n'est jamais la peine de recul, mais j'espère que cela peut être pris comme lu.

Le post original ci-dessous se remplit peu à certains détails de la façon dont l'estimation de l' 3.5m doit être ajusté pour tenir compte de la possibilité pour elle d'être battu sur le court terme.

Comme une note, comme je viens de le commenté l'OP,* la recherche peut ne pas être nécessaire à tous. Il doit faire sens de simplement choisir un parcours de 4-pièces horizontales et 4-pièces verticales, disons, qui sont optimales. Et puis le reste avec une recherche ou d'une table de recherche basé sur l'orientation et x-y offset. (Mais la question demande une heuristique admissible, donc je vais laisser ma réponse.)

Principales Edit 2: résumer l'origine de ce travail empirique, en tenant compte des commentaires ci-dessous

Dans le long terme, comme expliqué ci-dessus, votre coût moyen de se déplacer est de 3,5. Cela peut aussi peut être vu de façon empirique dans l'exploration des données ci-dessous.

Cela donne une estimation naïve de l' 3.5m où m est la distance Manhattan. Cependant, c'est une sur-estimation, parce que dans le court terme, il est possible de faire mieux que la moyenne. Une bonne hypothèse pour ce qui est d'explorer comment nous pouvons éviter d'utiliser toutes les faces supérieure à 3.

• Si nous commençons avec la face 1, nous pouvons utiliser des faces 2 et 3 sur nos 2 premiers se déplace, va 2 se déplace mieux que 3.5m prédit.
• Si nous commençons avec le visage 2, nous pouvons utiliser des faces 1 et 3 sur nos 2 premiers se déplace, passant de 3 coups de mieux que d' 3.5m prédit.
• Si nous commençons avec la face 3, nous pouvons utiliser des faces 1 et 2 sur nos 2 premiers se déplace, va 4 se déplace mieux que 3.5m prédit.
• Si nous commençons avec le visage 4,5, ou 6, nous pouvons utiliser des faces 1, 2 et 3 sur nos 3 premiers se déplace, passant de 4,5 déplace mieux que 3.5m prédit.

Cette hypothèse peut être confirmée empiriquement simplement en exécutant le script ci-dessous pour chaque éventualité de départ de la filière, comme l'a suggéré BlueRaja - Danny Pflughoeft. Ainsi, une simple recevable statistique est 3.5m - koù k = max(f+1, 4.5), et f est à partir de la face. Mais c'est un peu klunky, en donnant des nombres négatifs pour les petites valeurs de m. Il est facile d'écrire des programmes version qui prend en compte si vous avez seulement 1 ou 2 ou 3 se déplace pour aller, voir ci-dessous

    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;
    }

L'exécution de ce à travers un espace de recherche avec |x|,|y| <= 100, cette fonction sous-estime le coût réel compris entre 0 et 6, avec une médiane de 0,5 ou 1,5 selon la face à.

Principales Edit 1: post original

Ma pensée a été qu'il serait bon d'explorer les données. J'ai donc eu un aller à l'algorithme de Dijkstra pour voir ce qu'est l'espace des solutions ressemble. Ce que j'ai trouvé est symptomatique de ce qui a été dit déjà. Certains facteur de fois la distance Manhattan est approprié, mais il peut y avoir de justification pour un plus grand facteur de 1,5. C'est bien indiquée par la forme du contour de la parcelle de coût contre les déviations de la phase initiale de x / y de la position.

Voici une trame de fil de l'intrigue, pour être honnête, c'est juste pour le plaisir des yeux.

Ce qui est intéressant, c'est que si vous ajoutez une autre colonne à vos données pour la distance manhattan (l'homme) et de la régression du coût (v) à l'encontre de la distance manhattan dans R, vous obtenez le résultat suivant

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

I. e. c'est vous dire que, pour chaque mouvement que vous faites à l'horizontale ou à la verticale, votre coût est 3.4991861, ou v près de 3,5. Qui se trouve tout juste à la moyenne de 1 à 6, si mon intuition est que les données nous dit qu'en moyenne, il est plus efficace d'utiliser toutes les faces de la mourir de façon égale sur une longue distance. Sur de courtes distances que vous pouvez être plus optimale.

J'ai essayé d' 3.5man - k comme estimation, avec k = 2.5. Cela semblait fonctionner. Quand j'ai soustrait le coût réel de ce que je suis -0.5 comme la valeur la plus élevée.

> 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 

Cependant Un* recherche a travailler pour toutes les configurations, y compris ceux après le début où le dé n'est pas dans la configuration d'origine, de sorte que la constante k ne peut pas être aussi faible que 2.5 en général. Il doit être soulevée, par exemple, à l' 4, ou dépendent de la configuration de la matrice, comme il est suggéré dans une autre réponse.

C'est tout à fait possible que j'ai fait une horrible erreur dans tout cela, donc j'ai mis le code ci-dessous. Comme je l'ai dit, je pense que l'approche de la génération de données et d'enquêter sur elle est saine même si mes résultats ne sont pas.

Voici quelques lignes du fichier de résultat de la première.

17,-100,410

17,-99,406

17,-98,403

17,-97,399

17,-96,396

Le code 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 code ci-dessous

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

Si je multiplie l'heuristique avec une constante, il n'est plus recevable

Il peut être si vous vous débarrasser de certains cas particuliers. Permettez d être la distance Manhattan, et observer que le dé ne peut jamais avoir de ses 1 face en deux étapes ultérieures de la voie. Il en résulte que, si vous n'êtes pas déjà à l'objectif:

• la première étape a coûté au moins 1;
• si 1 est en face, c'est au moins 2 (et la même chose vaut pour 6);
• le reste du chemin est au moins aussi cher qu'une série de 1 à 2 alternances, qui a coûté la bagatelle de 1,5 × (d - 1).

Donc recevable heuristique est

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

Voici mon algorithme appliqué à l'exemple de Paul de 300x300 de la grille, à partir de (23,25) et se terminant à (282, 199). Il trouve le chemin d'accès minimal et de la somme (1515, qui est de 2 points de moins que celle de Paul résultat de 1517) dans 0.52 secondes. Une version avec des tables au lieu de calculer les petites sections ont pris 0.13 secondes.

Code 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")]

Sortie:

*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)

Liste de "R" et "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"]

Somme du chemin d'accès en utilisant le démarrage de mourir et de la liste des "R" et "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])

Calcul de (r,c) de (1,1) à l'aide de la liste de "R" et "U" (puisque nous partons en (1,1,), (r,c) se règle à l' (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)

Algorithme/Solution

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.

Mais comment pouvons-nous savoir le chemin?
De mes tests, il semble fonctionner de la même façon:

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

Par exemple,

  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)

Propriétés de Dés Observé dans les Tests Empiriques

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

Pas seulement.

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)

Mais ici l'été, il devient intéressant:

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)

Pas seulement.

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

Answer 5

Idée:

Si vous devez vous déplacer en ligne droite, le mieux que vous puissiez faire est de terminer vos mouvements par 1 et 2, pour tous les autres mouvements, vous ne pouvez pas faire mieux que 3.5*distance .

Heuristique:

Avec ManhattanDistance = x + y l'heuristique suivante pourrait être utilisée:

 Heuristic = xH + yH;
 

où

 xH = calculateStraightLineHeuristic(x)
yH = calculateStraightLineHeuristic(y)
 

et la fonction calculateStraightLineHeuristic(z) est définie comme suit:

 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