Ejemplos

N-reinas

El problema consiste en encontrar una forma de colocar N reinas en un tablero de ajedrez sin que se den jaque (dos reinas se dan jaque si comparten fila, columna o diagonal).

Una primera idea sería construir sistemáticamente todas las formas posibles de colocar N reinas en un tablero y verificar si alguna de ellas es una solución factible. Esta estrategia es impracticable ya que en el caso de 8 reinas, dicha estrategia generaría el siguiente número de posibilidades a ensayar: 4.426.165.368.

La primera mejora que podemos hacer es no poner nunca más de una reina en una fila. Esto reduce la representación del tablero a un vector de 8 elementos, cada uno de los cuales da la posición de la reina dentro de la fila correspondiente. Podemos replantear el problema del siguiente modo: “colocar una reina en cada fila del tablero de ajedrez de forma que no se den jaque”.

En este caso el número de posibilidades es 8^8 = 16.777.216.

§La solución será una N-tupla

< x1, x2, …, xN >

donde xi representa la columna en la que se coloca la i-ésima reina.

Buscaremos UNA solución factible.

Restricciones explícitas:

$(\forall i)(x_i \in {1,2...,N}:1 \le i \le N)$

Reina 1 -> ( 1, x1 ) Reina 2 -> (2, x2) …

(x1, x2, x3, x4) = (2, 4, 1, 3)

Restricciones implícitas

Es posible determinar si una secuencia completa es factible y es posible determinar si una secuencia parcial puede conducir o no a una solución factible a través de las siguientes restricciones implícitas:

Dos reinas NO pueden estar en la misma columna.

Dos reinas i y j están en una misma columna si xi = xj

Por lo que una solución (x1, x2, …, xN) es factible si cumple lo siguiente

(\forall i)((\forall j)(i\neq j ->x_i \neq x_j: 1 \le j \le N):1 \le i \le N)

Dos reinas NO pueden estar en la misma diagonal.
- del tipo “/” si tienen el mismo valor de “fila + columna”, esto es, i + xi = j + xj y
- del tipo “\” si tienen el mismo valor de “fila - columna”, esto es, i - xi = j - xj

Reina1 (1,6) y Reina5 (5,2) están en la misma diagonal del tipo “/”, por tanto tienen el mismo

valor de fila+columna, 1 + 6 = 5 + 2 = 7

Reina3 (3,2) y Reina5 (5,4) están en la misma diagonal del tipo “/”, por tanto tienen el mismo

valor de fila-columna, 3 - 2 = 5 - 4 = 1

N-reinas: Una solución factible

Procedimiento N-reinas (N:entero, k:entero, e/s x[1..N]:vector de enteros, e/s flag:booleano)
   # Llamada inicial: N-reinas( N, 1, x, verdadero)
   x[ k ] = 0
   mientras (x[k] < N and flag ) hacer
	x[ k ] = x[k] + 1
	opción
		k = N and BUEN_SITIO(x,k): 
                           tratar(x)
                           flag=falso
		k < N and BUEN_SITIO(x,k): 
                           N-reinas(N, k+1, x, flag)
	fopción
   fmientras
fprocedimiento

donde la función BUEN_SITIO devuelve cierto si la k-ésima reina se puede colocar en la posición x[k], es decir, si está en distinta columna y distinta diagonal que las k-1 reinas anteriores; falso, en caso contrario.

Funcion BUEN_SITIO (x[1..N]:vector de enteros, k:entero) retorna (b:booleano)
   var  i:entero; ok:booleano; fvar
   i = 0
   ok = verdadero
   mientras (i < k-1 and ok) hacer
	i = i + 1
	si ( x[ i ] = x[ k ] ) or ( |x[ i ] – x[ k ] | = | i – k |) entonces
		ok=falso
	fsi
   fmientras
   retorna ok
ffunción

Existen dos soluciones factibles < 2, 4, 1, 3 > y < 3, 1, 4, 2 >

Número de nodos explorados hasta alcanzar la 1ª solución factible: 26

Número de nodos explorados en todas las soluciones factibles: 60

Número de nodos explorados en todas las soluciones factibles (sin poda): 340

Laberinto

Dado un laberinto representado por una matriz cuadrada L de n x n elementos:

Cada L[i][j], con 1 <= i, j <= n, tiene dos posibles valores:

´·´ representa una posición abierta y

´x´ representa una posición bloqueada.

Se trata de generar todos los caminos que comenzando en L[1][1] terminen en la posición L[n][n].

Para ello se considerarán únicamente dos tipos de movimientos: movimiento hacia la casilla inferior, que representaremos por el valor 1, y movimiento hacia la casilla derecha, que representaremos por el valor 2.

No se puede atravesar una posición bloqueada ni salir del laberinto.

La solución se puede expresar como una secuencia de decisiones que son los distintos movimientos que nos permiten ir desde la casilla L[1][1] a la L[n][n].

Una secuencia completa será del tipo <x1,x2, ..., x2(n-1) > ya que serán necesarios 2(n-1) movimientos para conseguir el objetivo, xi será 1 o 2 dependiendo del movimiento a realizar.

TODAS las soluciones factibles.

Restricciones explícitas.-

(\forall i)(x_i \in {1,2}:1 \le i \le 2(n-1))

Es posible determinar si una secuencia de decisiones completa es factible y es posible determinar si una secuencia de decisiones parcial puede conducir o no a una solución factible a través de las siguientes restricciones implícitas :

No salirse del tablero
No atravesar una posición bloqueada

Todas las soluciones factibles

procedimiento LABERINTO (L[1..n][1..n]:matriz de caracteres, n, k:entero, e/s x[1..2(n-1)]:vector de enteros)
    # Llamada inicial: LABERINTO (L, n, 1, x)
    x[ k ] = 0 
    mientras x[ k ] < 2 hacer
	x[ k ] = x[ k ] + 1
	opción
		k = 2(n-1) and MOVIMIENTO_CORRECTO(L, k, x): 
                                                                                                                       tratar(x,k)
		k < 2(n-1) and MOVIMIENTO_CORRECTO(L, k, x): 
                                                                                                                       LABERINTO(L, n, k+1, x)
	fopción
     fmientras
 fprocedimiento

donde la función MOVIMIENTO_CORRECTO devuelve cierto si el k-ésimo movimiento nos conduce a una posición libre y nos deja dentro del laberinto; falso, en caso contrario.

funcion MOVIMIENTO_CORRECTO (L[1..n][1..n]:matriz de caracteres, k:entero, x[1..2(n-1)]:vector de enteros) retorna (b:booleano)
     var i, fila, columna: entero  fvar
     i = 0, fila = 1, columna = 1
     mientras i < k hacer
	i = i + 1
	si x[ i ] = 1 entonces     
                fila = fila + 1
	si no 
                columna = columna + 1
	fsi
     fmientras
     si (fila <= n) and (columna <= n) and (L[fila][columna]= ´.´) entonces 
                   retorna cierto 
         si no 
                   retorna falso
     fsi
ffunción

Coloreado de un grafo

Dado un grafo no orientado G = ( V, E ) con V = { 1, 2, …, n }, determinar todas las formas posibles en las que pueden colorearse los nodos del grafo, de modo que no haya dos nodos adyacentes del mismo color y no se usen más de M colores (color 1, color 2, …, color M).

Se representará el grafo mediante una matriz de adyacencias L con valores tales que:

L[ i ][ j ] = 1 indicará que los nodos i y j son adyacentes y
L[ i ][ j ] = 0 indicará que los nodos i y j no son adyacentes

La solución se puede expresar como una secuencia de decisiones,

<x1, x2, …, xn>

siendo n el número de nodos de G, y siendo xi el color con el que se va a pintar el nodo i.

TODAS las soluciones factibles.

Restricciones explícitas

(\forall i)(x_i \in {1,2,...,M}:1 \le i \le n)

Es posible determinar si una solución completa es factible y es posible determinar si una solución parcial puede conducir o no a una solución factible a través de la siguiente restricción implícita:

No debe haber nodos adyacentes con el mismo color, es decir,

(\forall i) ((\forall j) ( L[ i ][ j ]=1 -> x_i \neq x_j : 1 \le j \le n): 1 \le i \le n)

procedimiento COLOREAR (L[1..n][1..n]:matriz de enteros, n, M:entero, k:entero, e/s x[1..n]:vector de enteros)
    # Llamada inicial: COLOREAR (L, n, M, 1, x)
     x[ k ] = 0
     mientras x[ k ] < M hacer
	x[ k ] = x[ k ] + 1
	opción
		k = n and COLOR_CORRECTO(L, k, x): 
	           tratar(x,k)
                k < n and COLOR_CORRECTO(L, k, x): 
                   COLOREAR (L, n, M, k+1, x)
	fopción
    fmientras
fprocedimiento

donde la función COLOR_CORRECTO devuelve cierto si el color asignado al nodo k-ésimo no coincide con el color asignado a ninguno de sus nodos adyacentes; falso, en caso contrario.

funcion COLOR_CORRECTO (L[1..n][1..n]:matriz de enteros, k:entero, x[1..n]:vector de enteros) retorna (b:booleano)
     var  i:entero; ok:booleano fvar
     i = 0
     ok = cierto
     mientras ( i < k-1 and ok ) hacer
	i = i + 1
	si ( x[ i ] = x[ k ] and  L[ i ][ k ] = 1)  entonces 
            ok = falso
        fsi
     fmientras
     retorna ok
ffunción

Embarcaderos

En un río hay n embarcaderos (numerados del 1 al n) y en cada uno de ellos se puede alquilar un bote que permite ir a cualquier embarcadero río abajo. Por tanto, existe una matriz C con las tarifas, donde en C[ i ][ j ] se recoge el coste del viaje entre el punto de embarque i y el j, para cualquier embarcadero de partida i y cualquier embarcadero de llegada j más abajo en el río.

Puede que un viaje de i a j sea más caro que una sucesión de viajes más cortos, por ello se trata de determinar cuál es el coste mínimo para ir desde el embarcadero 1 al embarcadero n y cuál es el trayecto que proporciona ese coste.

Se asume que el coste de ir de un embarcadero a él mismo es cero, o sea,

C[ i ][ i ] = 0 $\forall$ i: 1..n

La única limitación que existe en este problema es que desde un embarcadero no se puede volver a ninguno de los anteriores.

Secuencia de decisiones:

<x1, x2, …, xs> con 1 <= s <= n-1

en cada una de las decisiones optamos por uno de los embarcaderos situados más adelante en el río con respecto al embarcadero actual.

Restricciones explícitas: ( $\forall$ i)( {xi-1+1, xi-1+2, …, n } : 1 <= i <= s ), para ello, consideraremos que x0=1 que es el embarcadero del que partimos.

Restricciones implícitas: 1 < x1 < x2 < … < xs

Nota.- No es necesario comprobar el cumplimiento de las restricciones implícitas ya que por la propia definición de las restricciones explícitas siempre ocurre que las alternativas para la siguiente decisión (xi) son mayores que el embarcadero en el que hemos parado previamente (xi-1).

Función objetivo:

Se trata de minimizar por tanto el coste C[1][x1]+C[x1][x2]+…+C[xs-1][xs]

o lo que es lo mismo C[1][x1]+C[x1][x2]+…+C[xs-1][n]

Procedimiento Embarcaderos (C[1..n][1..n]:matriz de enteros; n, k:entero; e/s x[0..n-1], x_mejor[0..n-1]:vector de enteros; e/s v_mejor:entero)
      # Llamada inicial: Embarcaderos( C, n, 1, x, x_mejor,v_mejor) y la posición 0 de x tiene valor 1, que es el embarcadero en el que comenzamos el viaje
      var aux: entero fvar
      x[ k ] = x[ k-1 ]
      mientras ( x[k] < n ) hacer
               x[ k ] = x[ k ] + 1
               opción
                       x[ k ] = n:
                          aux = COSTE_VIAJE(C, x, k) 
                          si aux < v_mejor entonces
		               x_mejor = x
                	       v_mejor = aux
	                fsi
                       
                       x[ k ] < n:  
                           Embarcaderos(C, n, k+1, x, x_mejor, v_mejor)
                fopción
      fmientras
fprocedimiento


Funcion COSTE_VIAJE (C[1..n][1..n]:matriz de enteros; x[0..n-1]:vector de enteros, k:entero) retorna (s:entero)
     var  i, coste: entero fvar
     coste = 0
     para i=1 hasta k hacer
          coste = coste + C[x[i-1]][x[i]] 
     fpara
   retorna coste
ffuncion

Last updated 1 year ago