algorithm - manhattan - primero el mejor inteligencia artificial
A*HeurÃstica admisible para matrices rodando en cuadrÃcula (5)
Necesito ayuda para encontrar una buena heurística para el siguiente problema:
Te dan una cuadrícula
Rby-Cy un dado de seis caras. Deje que elstarty elendsean dos celdas distintas en esta cuadrícula. Encuentre un camino destartaend, de manera que la suma de las caras de la matriz mirando hacia arriba, a medida que la matriz esté girando a lo largo del camino, sea mínima.La orientación inicial del dado es la siguiente (el "2" está orientado al sur):
La forma en que modelé este problema es considerando el valor de la cara del dado como el costo de un borde en un gráfico. Los vértices del gráfico son de la forma (row, col, die) (es decir, una posición en la cuadrícula y el estado / orientación actual del dado). La razón por la que un vértice no es simple (row, col) es porque puede terminar en la misma celda con múltiples configuraciones / orientaciones del dado.
Usé A * para encontrar la solución al problema; Las respuestas dadas son correctas, pero no es lo suficientemente eficiente. He determinado que el problema es la heurística que estoy usando. Actualmente estoy usando la distancia de Manhattan, que obviamente es admisible. Si multiplico la heurística por una constante, ya no es admisible: corre mucho más rápido, pero no siempre encuentra la respuesta correcta.
Necesito ayuda para encontrar una mejor heurística que la distancia de Manhattan.
Si multiplico la heurística por una constante, ya no es admisible.
Puede ser si te deshaces de algunos casos de esquina. Sea d la distancia de Manhattan y observe que el dado nunca puede tener su 1 cara arriba en dos pasos subsiguientes del camino. De ello se deduce que, si aún no estás en la meta:
- El primer paso ha costado al menos 1;
- si 1 es boca arriba, es al menos 2 (y lo mismo ocurre con 6);
- el resto del recorrido es al menos tan costoso como una serie de 1-2 alternaciones, que ha costado 1.5 × ( d - 1).
Así que una heurística admisible es
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)
Aquí está mi algoritmo aplicado al ejemplo de Paul de una cuadrícula de 300x300, comenzando desde (23,25) y terminando en (282, 199). Encuentra la ruta y la suma mínimas (1515, que es 2 puntos menos que el resultado de Paul de 1517) en 0.52 segundos. Una versión con tablas de consulta en lugar de calcular las secciones pequeñas tomó 0.13 segundos.
Código 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")]
Salida:
*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)
Lista de "R" y "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"]
Suma de la ruta usando el dado inicial y la lista de "R" y "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])
El cálculo de (r,c) partir de (1,1) utilizando la lista de "R" y "U" (ya que comenzamos en (1,1,) , (r,c) se ajusta a (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)
Algoritmo / Solución
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.
¿Pero cómo encontramos el camino?
De mis pruebas, parece funcionar de manera similar:
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
Por ejemplo,
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)
Propiedades de los dados observados en las pruebas empíricas
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
No solo eso.
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)
Pero aquí es donde se pone interesante:
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)
No solo eso.
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
Bueno, agregaré mi comentario aquí, ya que es más óptimo que la respuesta más votada actual por @larsmans, pero estoy convencido de que debe haber algo mejor (de ahí la recompensa).
Si multiplico la heurística por una constante, ya no es admisible.
Lo mejor que se me ocurre es (manhattenDistance/3)*6 + (manhattenDistance%3) , donde / es la división entera y % es mod. Esto funciona porque en 3 movimientos sin retroceso, los tres dígitos serán únicos, por lo que la suma más baja que podríamos tener es 1 + 2 + 3 = 6 (el% 3 simplemente agrega cualquier extra, no múltiple de tres movimientos) .
[Editar] Como @GrantS señaló en los comentarios anteriores, mi heurística puede mejorarse muy ligeramente al agregar un 1 adicional cuando manhattenDistance%3 == 2 . Esto es fácil de hacer sin un condicional: (manhattenDistance/3)*6 + (manhattenDistance%3)*3/2
Edición principal 3: Prueba de que la heurística admisible óptima debe basarse en 3.5m
El costo promedio de viajar a lo largo del tablero tiene que acercarse a 3.5m m en el largo plazo, donde m es la distancia de Manhattan. Por lo tanto, la mejor heurística admisible debe ser de 3.5m más o menos una pequeña constante.
La razón de esto es que cada vez que te mueves en una dirección, x, digamos, desde la cara x1 , el próximo movimiento en la misma dirección, hacia la cara x2 tiene que satisfacer x1 + x2 = 7 . Esto se debe a que cualquier movimiento en la dirección perpendicular deja la orientación de la cara x2 igual . Piensa en rotar un dado de izquierda a derecha: las caras frontal y posterior permanecen iguales sin importar cuántas rotaciones realices. Por el contrario, si gira un troquel de adelante hacia atrás, las caras izquierda y derecha permanecen igual.
Es más fácil de ver esto con algunos ejemplos (todo comienza en la configuración que se muestra en la pregunta)
6
2453
1
Aquí puede ver que comenzamos con y1=1 , y como muchas veces nos movemos en la dirección x después, el siguiente movimiento en la dirección y debe ser y2=6 , entonces y1+y2=7 . (También en la dirección x, hay un par simple de 2+5 = 7 y 4+3 = 7 ).
Otro ejemplo es
35
26
14
En este ejemplo, comenzamos con x1=1 , y como muchas veces nos movemos en la dirección y después, el siguiente movimiento en la dirección x tiene que ser x2=6 . (Además, vemos pares de 4+3=7 en la dirección y, 2+5=7 en la dirección x. Y sabemos que en este caso el siguiente movimiento en la dirección x tiene que ser 4 , y el el siguiente movimiento en la dirección y tiene que ser 1 )
Todo esto asume que nunca vale la pena retroceder, pero espero que esto pueda tomarse como leído.
La publicación original a continuación solo completa algunos detalles de cómo se debe ajustar la estimación de 3.5m para tener en cuenta la capacidad de superación en el corto plazo.
Como nota al margen, como acabo de comentar sobre el OP, es posible que no se requiera una búsqueda *. Debería tener sentido simplemente elegir un camino hecho de 4 piezas horizontales largas y 4 verticales, por ejemplo, que sean óptimas. Y luego invente el resto con una búsqueda o una tabla de búsqueda basada en la orientación y el desplazamiento xy. (Pero la pregunta pide una heurística admisible, así que voy a dejar mi respuesta).
Main Edit 2: resume el trabajo empírico original, teniendo en cuenta los comentarios a continuación
A largo plazo, como se explicó anteriormente, su costo promedio por movimiento es de 3.5. Esto también se puede ver empíricamente en la exploración de los datos a continuación.
Esto da una estimación ingenua de 3.5m m donde m es la distancia de Manhattan. Sin embargo, esto es una sobreestimación, porque a corto plazo es posible hacerlo mejor que el promedio. Una buena hipótesis para esto es explorar cómo podemos evitar usar cualquier cara mayor a 3.
- Si comenzamos con la cara 1 , podemos usar las caras 2 y 3 en nuestros primeros 2 movimientos, yendo 2 movimientos mejor que los
3.5mpredice. - Si comenzamos con la cara 2 , podemos usar las caras 1 y 3 en nuestros primeros 2 movimientos, yendo 3 movimientos mejor que los
3.5mpredice. - Si comenzamos con la cara 3 , podemos usar las caras 1 y 2 en nuestros primeros 2 movimientos, yendo 4 movimientos mejor de lo que predice
3.5m. - Si comenzamos con la cara 4,5 o 6 , podemos usar las caras 1, 2 y 3 en nuestros primeros 3 movimientos, yendo 4.5 movimientos mejor que los
3.5mpredice.
Esta hipótesis se puede confirmar empíricamente simplemente ejecutando el siguiente script para cada posibilidad de inicio del dado, como lo sugiere BlueRaja - Danny Pflughoeft. Por lo tanto, una estadística admisible simple es 3.5m - k , donde k = max(f+1, 4.5) , y f es la cara inicial. Pero esto es un poco torpe, dando números negativos para valores pequeños de m . Es fácil escribir una versión programática que tenga en cuenta si solo te quedan 1 o 2 o 3 movimientos, ver más abajo.
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;
}
Ejecutar esto en un espacio de búsqueda con |x|,|y| <= 100 |x|,|y| <= 100 , esta función subestima el costo real entre 0 y 6, con una mediana de 0.5 o 1.5 dependiendo de la cara inicial.
Edición principal 1: publicación original
Mi pensamiento básico era que sería bueno explorar los datos. Así que probé el algoritmo de Dijkstra para ver cómo se ve el espacio de soluciones. Lo que encontré es un apoyo a lo que ya se ha dicho. Algún factor multiplicado por la distancia de Manhattan es apropiado, pero puede haber alguna justificación para un factor mayor que 1.5. Esto está muy bien indicado por la forma de un gráfico de contorno del costo contra la desviación de la posición inicial xy.
Aquí hay un diagrama de marco de alambre: para ser honesto, esto es sólo para los ojos dulces.
Lo que es interesante es que si agrega otra columna a sus datos para la distancia de manhattan (hombre) y regresa el costo (v) contra la distancia de manhattan en R, obtiene lo siguiente
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
Es decir, le está diciendo que por cada movimiento que realice en forma horizontal o vertical, su costo es de 3.4991861, o muy cerca de 3.5. Sucede que el promedio es de 1 a 6, por lo que mi intuición es que los datos nos dicen que, en promedio, es más eficiente usar todas las caras del dado por igual en una larga distancia. En distancias cortas puedes ser más óptimo.
Intenté 3.5man - k como una estimación, con k = 2.5 . Esto parecía funcionar bien. Cuando resté el costo real de esto, obtuve -0.5 como el valor más alto.
> 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
Sin embargo, la búsqueda A * tiene que funcionar para todas las configuraciones, incluidas las posteriores al inicio donde el dado no está en la configuración original, por lo que la constante k no puede ser tan baja como 2.5 en general. Se debe elevar, por ejemplo, a 4 , o depender de la configuración del dado, como se sugiere en otra respuesta.
Es muy posible que haya cometido un error horrible en todo esto, así que puse el código a continuación. Como dije, creo que el enfoque de generar los datos e investigarlos es correcto incluso si mis resultados no lo son.
Aquí hay algunas líneas del archivo de resultados primero.
17, -100,410
17, -99,406
17, -98,403
17, -97,399
17, -96,396
Código 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();
}
}
Código R a continuación
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)
Idea:
Si tienes que moverte en línea recta, lo mejor que puedes hacer es terminar tus movimientos con 1 y 2, para todos los demás movimientos no puedes hacer más que 3.5*distance .
Heurístico:
Con ManhattanDistance = x + y se puede utilizar la siguiente heurística:
Heuristic = xH + yH;
dónde
xH = calculateStraightLineHeuristic(x)
yH = calculateStraightLineHeuristic(y)
y la función calculateStraightLineHeuristic(z) se define de la siguiente manera:
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