1votos

Laberinto en C#

por josejuan hace 6 años

Es un problema típico de optimización de rutas, usando un A* la solución es casi directa.

Hay un raton en un laberinto en el cual existen tanto una salida como puede haber quesos por todo el laberinto.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// datos del problema, una cadena MOD(n) 
var P = "#########" + 
        "#R   ##Q#" + 
        "#Q   ## #" + 
        "#       S" + 
        "#########"; 
// MOD(9), hay que indicarlo, porque podría ser cualquier divisor de P.Length 
var w = 9; 
 
 
 
 
 
var h = P.Length / 9; 
var r = P.IndexOf('R'); 
var s = P.IndexOf('S'); 
 
var v = new HashSet<int>(); 
v.Add(r); 
 
Func<int, double> cost = i => P [ i ] == ' ' ? 1.0 : ( P [ i ] == 'Q' ? 1.0 - ( 1.0 / P.Length ) : P.Length ); 
 
var p = AStarSolver( 
 
            new List<int> { r }, 
 
            l => 
 
                l.Select(cost).Sum() + 
 
                ( Math.Abs(( s - l.Last() ) % w) + Math.Abs(( s - l.Last() ) / w) ) * ( 1.0 + 1.0 / P.Length ), 
 
            l => new [] { -w, +w, -1, +1 } 
                    .Select(i => l.Last() + i) 
                    .Where(i => 0 <= i && i < P.Length && !v.Contains(i)) 
                    .Select(i => { 
                        v.Add(i); 
                        return l.Concat(new [] { i }).ToList(); 
                    }), 
 
            l => l.Last() == s 
 
    ); 
 
foreach( var i in p ) 
    Console.WriteLine("({0}, {1})\n", i % w, i / w); 
3 comentarios
0votos

Escrito por cruack hace 6 años

donde sacas AstarSolver ?
0votos

Escrito por josejuan hace 6 años

@cruack, es un A* de libro:
  • nodos iniciales de partida.
  • función de optimización (coste).
  • función de expansión.
  • condición de éxito.

Por ejemplo en A* search algorithm.

Creo recordar que implementé esa función adhoc, pero ya digo que es genérica y valdría cualquier otra implementación (genérica) del A*.
0votos

Escrito por cruack hace 6 años

donde sacas AstarSolver ?

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.