(void *) blog

Posted on by fortytwo_de


El enunciado del ejercicio de la OIE se puede descargar aquí.

Los problemas de "hallar la distancia más corta entre dos puntos" suelen resolverse con un breadth-first search. Es un algoritmo de búsqueda en un árbol que va iterando sobre los nodos horizontalmente, en vez de verticalmente como depth-first search.

La imagen representa el orden en el que se visitan los elementos del árbol, buscando la anchura antes que la profundidad.

En el caso concreto del ajedrez, se pueden interpretar todas los movimientos legales como un árbol (Game tree). El objetivo es alcanzar una casilla objetivo en el menor número posible de movimientos con un caballo. La ventaja de BFS es que una vez que se haya encontrado una ruta, está garantizado que esa es al ruta más corta. Con DFS, sin embargo, encontrar una ruta no es condición sine qua non de que será la más corta.

El procedimiento a seguir, entonces, es sencillo:

  • Leer el mapa
  • Interpretar los símbolos
  • Generar un vector de posiciones legales para un caballo
  • Comprobar cuáles de las posiciones legales son viables (la celda tiene que estar vacía, la celda no puede haber sido visitada anteriormente, la celda debe estar dentro de los límites del mapa...)
  • Comprobar si una de las posiciones legales es un objetivo. Si lo es, se termina el algoritmo. Si no lo es, se añade esa celda a la lista de distancias.
  • Añadir las posiciones permitidas a una lista
  • Mientras la lista no esté vacía, repetir el proceso desde el paso 3.

Implementación

Ahora que estoy programando los problemas en C++, puedo aprovecharme de ciertas ventajas, como que está permitido definir funciones dentro de clases.

Unas definiciones de preprocesador para definir internamente el mapa:

#define CELL_NOT_VISITED    -1
#define CELL_OBSTACLE       -2
#define CELL_TARGET         -3
#define CELL_HORSE          -4

#define FREE                    '.'
#define OBSTACLE                '#'
#define HORSE                   'C'
#define TARGET                  'X'

Todas las definiciones CELL_* son menores que cero a propósito. Al ser menores que cero, luego puedo comprobar si una celda ha sido visitada comprobando si su valor es mayor que cero.

Mis clases para resolver este problema:

struct point_t {
    unsigned int x;
    unsigned int y;

    point_t(unsigned int x_n, unsigned int y_n): x(x_n), y(y_n) {}
    std::vector<point_t> knight_locations() {
        std::vector<point_t> result;
        result.push_back(point_t(x+1, y+2));
        result.push_back(point_t(x+2, y+1));
        result.push_back(point_t(x-1, y+2));
        result.push_back(point_t(x-2, y+1));
        result.push_back(point_t(x-1, y-2));
        result.push_back(point_t(x-2, y-1));
        result.push_back(point_t(x+1, y-2));
        result.push_back(point_t(x+2, y-1));

        return result;
    }
};

Vamos, casi exactamente igual que un pair<unsigned int, unsigned int> pero con una función que genera automáticamente las posiciones posibles para un caballo a partir de un point_t.

struct board_t {
    unsigned int x;
    unsigned int y;
    std::vector< std::vector<int> > map;

    board_t(unsigned int x_n, unsigned int y_n): 
        x(x_n), y(y_n), map(x, std::vector<int>(y, CELL_NOT_VISITED)) {}


    bool valid_position(point_t point) {
        if(point.x >= x || point.y >= y) return false; // bounds check 
        return map[point.x][point.y] != CELL_OBSTACLE && map[point.x][point.y] < 0;
    }

    unsigned int distance(point_t point) {
        int cell = map[point.x][point.y];
        if(cell == CELL_HORSE) 
            return 1;
        else
            return cell+1;
    }

    void print_map() {
        for(size_t i = 0; i < x; i++) {
            for(size_t ii = 0; ii < y; ii++) {
                int cell = map[i][ii];
                if(cell == CELL_NOT_VISITED) {
                    std::cout << FREE;
                } else if(cell == CELL_OBSTACLE) {
                    std::cout << OBSTACLE;
                } else if(cell == CELL_HORSE) {
                    std::cout << HORSE;
                } else if(cell == CELL_TARGET) {
                    std::cout << TARGET;
                } else { 
                    std::cout << cell;
                }
            }
            std::cout << std::endl;
        }
   }    
};

Esta clase es mucho más interesante: la función valid_position comprueba si el punto está dentro de los límites del mapa, si es un obstáculo, y si ha sido visitado ya.

La función distance devuelve la distancia desde un punto. print_map es una función de debug, pero si se descomentan las líneas correspondientes de la solución se puede ver el proceso de búsqueda, es interesante.

El resto de la implementación no tiene mucho misterio. Se puede ver el código completo en paste.pm.

Conclusión

Breadth-first search es útil en un amplio espectro de situaciones, y la implementación es bastante fácil. Y es muy satisfactorio ver que el programa funciona :)

Posted on by fortytwo_de | Posted in Ajedrez, Algoritmos, C, Programación


4 Responses to El salto del caballo

  1. Manu Mateos says:


    Si te entiendo bien, “breadth-first search” es lo que los humanos de a pie llamamos recorrido en anchura de un árbol o grafo, ¿verdad? ;)


  2. Pingback: Bellman-Ford | (void *) blog

  3. Janell says:


    You must spent a lot of time writing posts on your page,
    you can save a lot of work, just type in gogle:
    treoughan’s rewriter


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>