5.5.2 Algoritmos recursivos de prueba y error
Ejemplo 15. Método de Newton-Rapshon de manera recursiva
A continuación se va a rehacer el método de Newton-Raphson de manera recursiva. La manera en la que se plantea es haciendo llamadas sucesivas a la subrutina en la que se realizan las aproximaciones sucesivas pasando el nuevo valor de X que se quiere chequear.
Este valor irá estando cada vez más cerca de la solución f(x)=0 por lo que se añade una bifurcación al comiendo de la subrutina para chequear si se está suficientemente cerca de la solución. Esta bifurcación establece si debe realizarse una nueva llamada a la propia subrutina o bien si debe finalizar el programa.
Resulta imposible describir todos los algoritmos recursivos de prueba y error. De hecho, tampoco es la intención de este libro, sino que es más bien la de familiarizarse con la computación. Sin embargo un par de algoritmos van a ser descritos para desarrollar el conocimiento en esta disciplina. Un tipo de algoritmos dentro de los algoritmos recursivos de prueba y error son los algoritmos recursivos de búsqueda "hacia delante y hacia atrás". A continuación veremos el ejemplo del "viaje del caballo" y el "problema de las 8 reinas". Son dos jemplos situados en el entorno del juego del ajedrez.
Este juego ha sido objeto de estudio para buscar maneras de programar siguiendo el razonamiento que sigue la inteligencia humana ya que, la manera de pensar que se sigue en este juego es abordable siguiendo métodos mecanicistas.
Ejemplo 16. El viaje del caballo
En ciertos casos se puede plantear un esquema recursivo de prueba y error donde las pruebas que realiza el ordenador construyen una serie caminos de búsqueda de soluciones. Estos caminos de búsqueda dan como resultado un árbol de subtareas, donde algunos caminos no llegan a la solución mientras que otros sí. En muchos problemas, este árbol crece muy rápidamente, normalmente de manera exponencial, con la subsiguiente carga computacional.
Vamos a introducirnos en la técnica descrita mediante el conocido ejemplo del "viaje del caballo". Dado un tablero de ajedrez de NxN casillas, un caballo situado en una determinada casilla debe recorrer todo el tablero -de acuerdo a los movimientos permitidos según el juego del ajedrez- visitando todas las casillas sin situarse dos veces en ninguna de ellas. De forma que el problema consiste en encontrar un camino, si es que existe alguno, que recorra todo el tablero siguiendo la ruta mas corta, y por lo tanto realizando N2-1 movimientos, siguiendo los movimientos del caballo de ajedrez.
Considerando que el caballo puede realizar 8 movimientos posibles, la manera lógica para resolver este problema es la de construir el camino mediante una sucesión de búsquedas parciales, siendo ésta la búsqueda parcial de una nueva casilla que puede ser visitada. En el caso de encontrarse una nueva casilla, se procede a buscar la siguiente (se avanza hacia delante) y, en caso de no encontrase, se vuelve a la casilla de la que se había partido (se avanza hacia atrás), para probar una nueva casilla que pueda ser visitada distinta a la que se acababa de probar.
De manera que el procedimiento consistirá en inicializar las variables necesarias y proceder a dar el primer paso. La resolución del problema la realizaremos para un tablero con un número cualquiera de casillas y comenzando en una fila (f) y columna (c) cualquiera.
Siendo Casillas, el número de casillas del tablero, las variables que se inicializan son:
Tablero: es una matriz llena de ceros con un número de celdas igual a CasillasxCasillas. Según vaya el caballo pasando por cada celda se llenará la celda en cuestión con el número que indica en qué paso ha accedido el caballo a ella.
a: es un vector de ocho elementos con los desplazamientos permitidos en las filas del tablero para un caballo de ajedrez.
b: es un vector de ocho elementos con los desplazamientos permitidos en las columnas del tablero para un caballo de ajedrez. Los vectores a y b están coordinados entre sí, de manera que a(1) y b(1) representan el desplazamiento en la fila y la columna para el primero de los movimientos y así sucesivamente.
N: se corresponde con el número de movimientos realizados por el caballo. Será una variable auxiliar para determinar si con el movimiento que se acaba de realizar se ha llegado a alguna solución, ya que cuando N adquiera el valor de CasillasxCasillas significará que el caballo a pasado por todas las casillas.
La inicialización se realizará en la función principal, a la que llamaremos El_viaje_del_Caballo(f,c,Casillas). Las variables que se pasan por ventanilla son la fila de la que parte el caballo, f, la columna, c, y el número de filas o columnas que tiene el tablero, Casillas. Después de la inicialización se procede a dar el primer paso. Para ello se utilizará la función nuevo_paso(Tablero,f,c,a,b,N).
La función nuevo_paso será una función recursiva en la que se irá probando cada uno de los 8 movimientos que puede dar el caballo. Para determinar cuál de los ocho movimientos se está probando utilizaremos una variable auxiliar a la que llamaremos movimiento.
En primer lugar, la función nuevo_paso probará a dar el primero de los 8 movimientos. Si es correcto lo guarda y vuelve a llamarse a sí misma volviendo a repetir el proceso, con lo que se da un paso adelante. Si el movimiento probado no es correcto (esto es, se sale del tablero o accede a una casilla por donde ya ha pasado) pasa a probar el siguiente movimiento. Cuando ha probado los 8 movimientos, la función termina y con ella termina también ese camino de búsqueda, con lo que se da un paso hacia atrás.
El diagrama de flujo con el algoritmo descrito anteriormente es el siguiente:
La variable N es una variable que contabiliza el número de movimientos realizados.
No aparece en el diagrama de flujo, pero si en el código del programa. Gracias a esta variable, se soluciona la casuística que aparece cuando se ha cumplido el objetivo de recorrer todas las casillas del tablero y, en consecuencia, no es posible realizar ningún movimiento más. Se puede identificar que el programa ha llegado a este momento porque el valor de N coincide con size(Tablero,1)^2. Ahora lo que se hace es sacar por pantalla el tablero con los pasos realizados (Tablero(f1,c1)=N -observe que no se ha puesto ’;’ al final de la instrucción).
Es interesante el recurso empleado para poder utilizar los vectores con los movimientos a y b. Al ser dos vectores con los valores constantes, se ha definido como variables globales tanto en la función de inicialización (backtraking) como en la de búsqueda (nuevo_paso). Con esto se evita tener que pasar los valores de a y b por ventanilla en cada una de las llamadas, con lo que la velocidad del proceso mejora.
A continuación se presenta la primera de las múltiples soluciones que se obtienen cuando se le pide al programa que determine el camino a seguir para un tablero de 8x8 situando al caballo inicialmente en la casilla 1,1.
Puede observarse (con un poco de paciencia) como los movimientos realizados tienen una correspondencia con el orden en el que se han definido los 8 movimientos en los vecotres a y b.
Ejemplo 17. El problema de los emparejamientos estables
Imaginemos dos grupos de personas A y B con un mismo número de componentes N.
Se trata de encontrar el conjunto de N parejas a,b siendo a del grupo A y b del grupo B, que satisfagan ciertas restricciones. Se pueden utilizar muchos criterios para establecer estos emparejamientos. Uno de ellos es conocido como la "regla de los emparejamientos estables", el cual se explica a continuación:
Supongamos que A es un conjunto de motoristas y B un conjunto de cámaras de televisión. El objetivo es tratar de emparejar a los motoristas con los cámaras de televisión para cubrir la retrasmisión de una carrera ciclista. Cada motorista y cada cámara tienen distintas preferencias a la hora de elegir una pareja del otro grupo. Si las N parejas se establecen de forma que existe un motorista y un cámara de televisión que se prefieren mutuamente frente a la pareja que les ha tocado respectivamente, entonces el emparejamiento resulta inestable. Si, por el contrario, este tipo de sinergias no existen, se dice entonces que el emparejamiento es estable. Esta situación caracteriza muchos problemas que se presentan cuando hay que realizar emparejamientos de acuerdo a ciertas preferencias.
Supongamos que acaban de nombrar a un nuevo jefe para cubrir la actualidad deportiva en ese canal de televisión. Este jefe quiere que todas las personas que están a su cargo estén lo más contestas posible. Va a intentar que todas las órdenes que se den estén consensuadas por todos los afectados. Se va a cubrir la retransmisión de una maratón con 8 parejas de motoristas y de cámaras. Para establecer los emparejamientos se ha decidido que cada motorista pase el orden de preferencia que tiene sobre los cámaras y que cada cámara pase el orden de preferencia que tiene sobre los motoristas.
Con ello se ha elaborado la siguiente lista con la que hay que establecer los emparejamientos:
De forma que el motorista 1 prefiere estar en primer lugar con el cámara 7, en segundo lugar con el cámara 2 y así sucesivamente.
Un camino para dar con la solución es probar todos los pares de miembros de los dos grupos, uno detrás de otro, localizando las soluciones. Se establece, en este caso, una búsqueda de prueba y error hacia delante y hacia atrás sobre las distintas pruebas que se van haciendo. Este es el método seguido en el caso del problema de las 8 reinas, presentado en el libro "Aprenda a programar...". Llamando Prueba a la función para buscar la pareja al motorista M según el orden establecido mediante su ranking R, podemos escribir el siguiente diagrama de flujo que es completamente coincidente al del problema de las 8 reinas, salvando las pequeñas diferencias debidas a la casuística:
En el diagrama de flujo propuesto, se busca a un cámara que pueda ser pareja de un motorista. De manera que comenzamos buscando pareja al motorista 1, luego al motorista 2 y así sucesivamente; sin embargo observe que podría realizarse al revés, buscando primero pareja al cámara 1, luego al 2 etc.
Dentro de la Figura 5.9, la pregunta ¿Es válido? tiene dos partes. Para que la respuesta sea sí, hay que comprobar en primer lugar que el cámara no haya sido ya asignado. Y en segundo lugar hay que comprobar que el emparejamiento es estable.
Para ello hay que decidir cómo agrupar la información. En primer lugar vamos a guardar los datos iniciales que aparecen en la Tabla 5.1 en dos matrices:
MR: Matriz de 8x8 con el ranking establecido por los motoristas.
CR: Matriz de 8x8 con el ranking establecido por los cámaras.
Por ejemplo, MR(3,2) se corresponde con el cámara preferido en segundo lugar por el motorista 3, que es el cámara 2, según la Tabla 5.1.
Vamos a guardar el resultado de la búsqueda en un vector llamado X de 8 elementos en el que se indiquen ordenadamente el cámara elegido por el motorista de cada casilla. Así por ejemplo, X(3) se correspondería con el cámara asignado al motorista 3.
Además, va a ser conveniente establecer un segundo vector Y de otros 8 elementos donde guardaremos ordenadamente a los motoristas asignados a los distintos cámaras. Lógicamente, no es necesario crear Y, ya que es en realidad una información redundante. En realidad se puede crear Y a partir de X, y viceversa, según la relación:
Con esto, el diagrama de flujo de la Figura 5.9 puede ser reescrito de la siguiente manera:
Una parte fundamental en el diagrama de la Figura 5.10 es determinar si es estable la nueva pareja M-C establecida. Desgraciadamente no es posible establecer si es estable la pareja con una simple comprobación como en el caso del problema de las 8 reinas. Lo primero que tenemos que tener en cuenta es que la estabilidad o no de una pareja se determina según el ranking establecido en las matrices MR y CR. Sin embargo, éste ranking no está expresado de manera explícita en estas dos matrices. Lo interesante sería disponer de matrices en las que sí estuviera explicito de manera que se pudiera acceder directamente al ranking que tiene el motorista M sobre el cámara C y viceversa.
Para ello vamos a establecer dos matrices auxiliares que son función directa de MR y CR. Estas matrices son RMC y RCM. La primera matriz (RMC) contiene el ranking establecido por los motoristas sobre los cámaras. De manera que RMC(3,1) es el ranking que ocupa el cámara 1 según el orden de preferencia del motorista 3 (que es 4, según el ejemplo propuesto en la Tabla 5.1). Así mismo la segunda matriz, RCM, contiene el ranking establecido por los cámaras sobre los motoristas. Con estas dos matrices auxiliares se facilita muchísimo la determinación de la estabilidad o no de una nueva pareja.
El proceso para saber si es o no estable un emparejamiento se construye directamente aplicando la definición de la estabilidad. Un emparejamiento <M,C> no es estable por dos posibilidades:
1º Existe un cámara, distinto a C, que prefiere a M, frente al motorista que le han asignado y, a su vez, M le prefiere a él frente a C.
2º Existe un motorista distinto a M, que prefiere a C, frente al cámara que le han asignado y, a su vez, C le prefiere a él frente a M.
Lo que ahora toca es realizar una función cuyo encabezado sea:
function [XM,YM]=EmparejamientoEstable(MR,CR)
Donde MR y CR son las matrices anteriormente descritas que contienen el ranking, XM es una matriz cuyas filas se corresponden con cada una de las soluciones estables con los emparejamientos que se hacen a los motoristas e YM es el homólogo a XM pero con los cámaras.
Está función realizará la inicialización del proceso recursivo de prueba y error y lanzará la búsqueda de la pareja para el primer motorista. Según lo que se ha comentado, en la inicialización del proceso debe:
1º Inicializar los vectores X e Y
2º Crear las matrices RMC y RCM.
3º Lanzar la función Prueba para el motorista 1.
Por otra parte hay que, lógicamente, programar la función Prueba, cuyo encabezado será:
function Prueba(M,X,Y)
Siendo M el motorista al que se le busca pareja, X son los cámaras asignados a los motoristas e Y son los motoristas asignados a las cámaras.
Por último será necesario programar una tercera función que devuelva si un emparejamiento es o no estable. El encabezado será:
function E=Estable(M,C,X,Y)
Donde X, Y y M coinciden con los valores de entrada de la función Prueba. C es el cámara que se prueba a emparejar con el motorista M y E es 1 si el emparejamiento es estable y 0 si no lo es.
El resto de datos que necesitan las funciones (MR, CR, RMC o RCM), como no van a variar una vez definidos, deben guardarse como variables globales, tal y como se hace con los vectores que contienen los movimientos en el "viaje del caballo". Hay que observar que en el caso de la función de inicialización - EmparejamientoEstable(MR,CR)- no pueden definirse como variables globales MR y CR, ya que son los propios valores de entrada a la función, así que deberá utilizar otro nombre alternativo para estas dos matrices.
También se deben definir como variables globales las dos matrices de retorno XM e YM, para añadir una nueva fila cada vez que se encuentre alguna solución.
Espero haber ayudado en algo. Hasta la próxima oportunidad!
Twittear
No hay comentarios:
Publicar un comentario