Monografías
Publicar | Monografías por Categorías | Directorio de Sitios | Software Educativo | Juegos Educativos | Cursos On-Line Gratis

 

Algoritmos de retroceso parte 2 - Monografía



 
DESCARGA ESTA MONOGRAFÍA EN TU PC
Esta monografía en formato html para que puedas guardarla en tu pc e imprimirla.



Vínculo Patrocinado




Aquí te dejamos la descarga gratuita
Nota: para poder abrir archivos html solo necesitas tener instalado internet explorer u otro navegador web.




Como se puede ver en la Tabla 2.1, cuando a la variable x0 se le asigna el valor de 1 no existe ninguna tupla de soporte. Para que el problema sea consistente debe de existir al menos una tupla de soporte para cada combinación posible de (c, x, a) que se de en el problema. Debido a esto se debe de reducir el dominio de la variable x0 de { 0, 1 } a solamente { 0 } para que cumpla con las reglas de consistencia. Si se sigue esto entonces la tabla quedaría como en la Tabla 2.2.

A partir de todo lo que se ha estudiado, cualquier arco (xi, xj) que esté presente en un ejemplar CSP puede hacerse consistente con solo borrar aquellos valores de sus dominios que no permitan la consistencia de las restricciones que los vincula.

Es importante hacer notar que la inconsistencia del ejemplar no solo se puede presentar al momento de crear la instancia. También es posible que se dé durante el proceso de solución del mismo. Cuando se asigna a una variable un valor a es posible que esa asignación haga inconsistente valores de variables que se conservaban consistentes hasta antes de la asignación. Para resolver esto se sigue el mismo procedimiento, es decir, se borran esos valores inválidos de sus dominios. Con esto se advierte que es un proceso repetitivo y por tanto sería de gran utilidad emplearlo en los Algoritmos de Retroceso. En secciones posteriores se tratan algunas técnicas existentes para tratar la Consistencia de Arco durante el la búsqueda de solución trazada por el Paradigma BT.

2636.gif

Tabla 2.2. Ejemplar de un Problema CSP con consistencia de arco

2.3.2 Algoritmos de Retroceso


El tema de Algoritmos de Retroceso ya ha sido tratado en secciones anteriores. En esta sección se mostrarán algunos de los Algoritmos que existen para resolver el Problema  CSP, y como son las técnicas que implementan.

Existen diversas modalidades de algoritmos de retroceso que se emplean para resolver problemas CSP. Los que se utilizan para solucionar el problema de generación de crucigramas fueron tomados de [15], [20] y [24], y se analizan a continuación.

Dentro de los algoritmos que se pretenden analizar se encuentran:

1)    Algoritmo de Retroceso Cronológico (o simplemente BC);
2)    Algoritmo de Retroceso incorporando Chequeo Adelante
3)    Algoritmo de Retroceso incorporando Consistencia de Arco de nivel 3 (General Arc Consystency 3, Gac3);
4)    Algoritmo de Retroceso incorporando Consistencia de Arco de nivel 4 (Maintining Arc Consistency, Ac4); y
5)    Algoritmo de Retroceso incorporando Consistencia de Arco de nivel 7 (General Arc  Consistency, Gac7).

2.3.2.1 Algoritmo de Retroceso Cronológico



Este es el algoritmo de retroceso más común que existe. También es el más sencillo de explicar. La forma en que se desarrolla fue ya revisada al inició del tema de “Algoritmos para solucionar CSP” como Paradigma de Retroceso. Para comodidad del lector, esta técnica se revisará de nueva cuenta en esta sección.

El Algoritmo de Retroceso Cronológico va asignando valores a variables en forma secuencial, por cada asignación se va realizando un chequeo de restricciones. Si durante este chequeo se verifica que la consistencia del problema ha sido violada, entonces se efectúa un retroceso y se vuelve a la variable más recientemente asignada. Si no existió ninguna violación de restricciones durante la asignación del valor a la variable, se procede con el método de búsqueda, hasta llegar a encontrar una solución para el problema.

Este método implementa el árbol de búsqueda desarrollado  en el algoritmo de Generar-y-Examinar. Representa una mejora para el Paradigma GT puesto que ya no considera todas las posibles combinaciones que sean generadas por las variables y sus valores, sino que va realizando una verificación de restricciones en cada asignación de valor a variable y si alguna asignación hace inconsistente el problema entonces realiza un retroceso.

Una nota importante que se debe de tomar en cuenta para el Algoritmo de Retroceso Cronológico, es que hace uso de reglas heurísticas para determinar el orden en que se van a asignar las variables. Esto se hace con el objeto de mejorar el algoritmo. Si se escoge una regla heurística adecuada es posible mejorar el desempeño del algoritmo al hacer más rápida la localización de violaciones a restricciones.

El Algoritmo de Retroceso Cronológico se muestra en la Figura 2.11.

2637.gif

Figura 2.11. Algoritmo de Retroceso Cronológico

En este algoritmo también se advierten la presencia de algunas funciones,  procedimientos  y sentencias que cumplen con objetivos muy particulares para el algoritmo. Lo primero en hacer notar es la presencia de la función VerificarRestricciones( ), cuya labor es la misma que en el Paradigma GT, verificar la las asignaciones hechas hasta ese momento sean consistentes y no violen ninguna restricción. Por otro lado, aparece la función ElegirVariable( ), la cual se encarga de seleccionar cuál es la siguiente variable que se debe de asignar. Ésta función no retorna una variable que ha sido ordenada en forma ascendente de acuerdo a su índice junto con respecto a las demás, sino que regresa una variable que, mediante una heurística aplicada previamente, fue ordena de forma tal que asegura un mejor desempeño del algoritmo en cuanto a la asignación de valores, tratando de asegurar que las violaciones o inconsistencias serán encontradas más rápidamente. Ésta función sustituye a la de SiguienteVariable( ), en                  Generar-y-Examinar.  La heurística empleada para desarrollar esta función se muestra en más adelante. Otro procedimiento nuevo, en nombre, es el de  Restaurar( ). En este procedimiento se devuelven los valores que tenían las variables, las restricciones y sus dominios respectivos momentos antes de que la variable del nivel actual tomase su valor y siguiese con la búsqueda.

También debe de advertirse dos nuevas sentencias. La primera localizada en la línea 11 del algoritmo mostrado en la Figura 2.11, se asegura que el valor que se asigne a la variable sea válido, es decir, que exista al menos una tupla en cada restricción donde la variable interviene que permita tomar ese valor. De ser así, la sentencia se cumple y permite seguir con la búsqueda. De lo contrario, cancelará la búsqueda por ese lado.

La otra sentencia que se puede apreciar es la que se  encarga de Checar las Restricciones inmediatamente después de realizar la asignación de un valor. Se encuentra en la línea 13 del algoritmo, se representa por una llamada a la función VerificarRestricciones( ), y se asegura de que las demás variables puedan seguir tomando valores válidos de su dominio.

En esencia, este es el comportamiento del Algoritmo de Retroceso Cronológico. Su implementación es exactamente igual al de Generar-y-Examinar, la diferencia radica en la adición de chequeo adicionar en el Algoritmo de Retroceso.

Para ilustrar el Algoritmo de Retroceso Cronológico mostrar la diferencia que posee con respecto al de Generar-y-Examinar, en las Figuras 2.12 y 2.13 se muestran los árboles de búsqueda generados por cada uno de los algoritmos al resolver el Problema CSP señalado en la Figura 2.8..
2638.gif

Si se alcanza a apreciar, en la Figura 2.12 se muestra el árbol de búsqueda generado por el algoritmo Generar-y-Examinar. Como se ve, todo el árbol que se podía crear (es decir, todas las combinaciones) fue examinado, se alcanzaron todas las hojas. En cada hoja se realizó  un chequeo de restricciones, con el cual se podía determinar si las asignaciones hechas formaban una solución válida o no. En la Figura 2.13 se muestra el desarrollo  del árbol de búsqueda, pero hecho por el Algoritmo de Retroceso Cronológico.

2639.gif

Figura 2.13. Árbol de búsqueda generado por el Algoritmo de Retroceso Cronológico.

Con la Figura 2.13 se puede advertir que el comportamiento de ambas técnicas (Generar-y-Examinar, y Algoritmo de Retroceso Cronológico) son diferentes. Esto es debido a las implementaciones de los mismos. Su mecánica es diferente, y por consiguiente da diferentes resultados. En el árbol de búsqueda originado por el Algoritmo de Retroceso Cronológico se puede ver que no se alcanzaron todas las hojas, y solamente fueron examinadas unas cuantas. Esto se debió al chequeo parcial que se hace en los nodos del algoritmo cada vez que se asigna un valor a una variable.

2.3.2.2 Algoritmo de  Retroceso Cronológico con Chequeo hacia Adelante
Este algoritmo es el primero en tratar de resolver la Consistencia de Arco. Su forma de resolución es indirecta, a diferencia de los algoritmos que incorporan un método propiamente dicho, como los que se verán en las siguientes secciones.

El método general de esta técnica fue revisado en [5] y [20], y consiste en ir checando variables xi que representan la última variable de una restricción en ser asignadas. Dicho de otra manera, a medida que se avanza en la asignación de valores a variables y se llega al estado en que alguna de las restricciones necesita solamente instanciar una variable más (xi) para verificar la consistencia de la posible solución que se tiene, en lugar de seguir con la búsqueda normal volviendo a llamar de nueva cuenta al Algoritmo de  Retroceso, se asignan temporalmente a xi cada uno de los valores que tenga en su dominio. Si alguno valor a viola la restricción que se está checando, entonces ese a deberá ser removido, de lo contrario se deja intacto el valor y se sigue con las demás variables. Cuando el dominio de alguna variable que vacío, el problema se hace inconsistente por completo y se tiene que realizar forzosamente un retroceso. Si el D(xi) !=  , se desasigna cualquier valor que haya tomado y se sigue con el proceso de búsqueda.

En la Figura 2.14 se muestra la función que se incorporaría al Algoritmo de Retroceso Cronológico para que se convirtiese en Chequeo-Adelante( ). La diferencia radica en que la línea 13 del algoritmo mostrado en la Figura 2.11 cambia la función de  VerificarRestricciones( ) por la Chequeo-Adelante( ), para hacer un chequeo de consistencia.

2640.gif

2.3.2.3 Algoritmo de Retroceso incorporando Consistencia de Arco de nivel 3 (Gac3)


Este es el segundo algoritmo que se va a analizar.

Como se ha comentado previamente, el Algoritmo de Retroceso Cronológico al parecer no es una técnica muy eficiente, debido a que pasa por alto las inconsistencias de arco que van resultando al asignar valores de variables. Para resolver este problema se introduce el concepto de ¿qué es Consistencia de Arco?, y ¿Cómo puede ser resuelta? en la sección de Consistencia de Arco encontrada en el presente capítulo.

Ahora bien, solamente se ha visto la teoría, sin embargo, no se ha visualizado la técnica algorítmica que resolvería el problema de la inconsistencia de arco. Por esa razón se dedica esta sección y las 2 posteriores, al estudio de las técnicas que permiten manejar y controlar la consistencia de un Problema CSP.

El Gac3 es un Algoritmo de Retroceso. Su idea principal se basa en el desarrollo de un función que permita revisar las variables y sus dominios, de manera que se verifiquen si todos los valores siguen siendo válidos, es decir, siguen teniendo tuplas de soporte en los dominios actuales de las restricciones.
Como se dice en [24], su implementación reduce paulatinamente el espacio de posibles soluciones, y por tanto el tiempo de cómputo al eliminar periódicamente valores inválidos de una instancia CSP. En otras palabras, este algoritmo permite que el hecho de asignar un valor a una variable tenga repercusión en todos los conjuntos de valores asociados a ella (dominio de la variable, y restricciones que la incluyen), eliminando valores inconsistentes y dejando solo aquellos que permitan obtener una solución del problema.

La nueva función, que resolvería la Consistencia de Arco, quedaría como se muestra en la Figura 2.15. Fue tomada de [20], y forma el cimiento principal del Algoritmo Gac3.

2640.gif

La función Revisar( ) toma como parámetros una restricción c y una variable a perteneciente a dicha restricción. Examina el dominio de las restricción, buscando un soporte para cada valor a de la variable v analizada. Si durante la revisión existe algún valor que no posea algún soporte, ese valor deberá ser eliminado (asegurando así la consistencia del problema). Una vez que termina la revisión, se debe verificar si todavía existe algún valor que se pueda asignar a la variable v. Si no existe ninguno ( D(v) =   ) la función deberá regresar FALSO para indicar que ya no existe forma de hacer consistente al problema. De lo contrario deberá de regresar VERDADERO.

En el algoritmo se hace mención a una pila. Esta estructura de datos sirve para almacenar que variables han cambiado su dominio debido a la revisión realizada. El objetivo de mantener esas variables en una pila es el de propagar el efecto de borrar un valor de un dominio. Puesto que si al asignar un valor a una variable puede causar inconsistencia en otras, el borrar valores de una variables causaría el mismo efecto, por lo cual se debe mantener un control de las variables y hacerles una revisión respectiva.

Ahora bien, ¿donde se debe de aplicar la revisión en el Algoritmo de Retroceso?. Para ello se necesita implementar otra función, ForzarConsistencia(), la cual se encargará de revisar las variables que hallan modificado sus dominios en forma reciente, ya sea debido a una asignación de valores durante la ejecución del algoritmo normal, o bien mediante la supresión de los mismos valores pero a través de la revisión para el mantenimiento de la consistencia de arco. La estructura de esta función quedaría como se muestra en la Figura 2.16.

2640.gif

La función Revisar( ) toma como parámetros una restricción c y una variable a perteneciente a dicha restricción. Examina el dominio de las restricción, buscando un soporte para cada valor a de la variable v analizada. Si durante la revisión existe algún valor que no posea algún soporte, ese valor deberá ser eliminado (asegurando así la consistencia del problema). Una vez que termina la revisión, se debe verificar si todavía existe algún valor que se pueda asignar a la variable v. Si no existe ninguno ( D(v) =   ) la función deberá regresar FALSO para indicar que ya no existe forma de hacer consistente al problema. De lo contrario deberá de regresar VERDADERO.

En el algoritmo se hace mención a una pila. Esta estructura de datos sirve para almacenar que variables han cambiado su dominio debido a la revisión realizada. El objetivo de mantener esas variables en una pila es el de propagar el efecto de borrar un valor de un dominio. Puesto que si al asignar un valor a una variable puede causar inconsistencia en otras, el borrar valores de una variables causaría el mismo efecto, por lo cual se debe mantener un control de las variables y hacerles una revisión respectiva.

Ahora bien, ¿donde se debe de aplicar la revisión en el Algoritmo de Retroceso?. Para ello se necesita implementar otra función, ForzarConsistencia(), la cual se encargará de revisar las variables que hallan modificado sus dominios en forma reciente, ya sea debido a una asignación de valores durante la ejecución del algoritmo normal, o bien mediante la supresión de los mismos valores pero a través de la revisión para el mantenimiento de la consistencia de arco. La estructura de esta función quedaría como se muestra en la Figura 2.16.

2641.gif

Con la función de ForzarConsistencia() terminada solo restaría mostrar el Algoritmo Gac3 completo, la forma en que quedaría el Algoritmo de Retroceso original, incorporando el control de Consistencia de Arco. Esto último se ilustra en la Figura 2.17.


2.3.2.4 Algoritmo de Retroceso incorporando Consistencia de Arco de nivel 4 (Ac4)


Este algoritmo es descrito en extensión en [15]. La idea básica es que este Ac4 representa una mejora para Gac3. Su enfoque se dirige hacia soporte, mas que centrarse en la simple propagación del efecto de borrado de valores de dominio.

Este algoritmo mantiene 2 estructuras nuevas, soporte y contador.

La estructura contador mantiene el total de variables vi que soportan la asignación del valor a a la variable vj. Existen una estructura contador por cada combinación (variable, valor de dominio) exista. Cuando el valor de alguno de los elementos pertenecientes a la estructura contador se vuelve cero, el valor de variable asociado a ese elemento deberá ser elimina. Se vuelve inconsistente.

La otra estructura, soporte, posee la relación de pares   (variable, valor de dominio) que son soportador por un determinado par   (variable, valor de dominio).

2642.gif

Considerando el ejemplo de  la Figura 2.8. La estructura contador para este problema quedaría como en la Figura 2.18. Ahí se logra apreciar la inconsistencia inicial del problema. Esta se demarca por la aparición de un contador igual a 0 (Contador[ (x0, x2), 1 ] = 0) lo cual indica que es un valor que debería ser removido del dominio de la variable asociada. Con esto se demuestra la aplicación de la estructura contador, esto es que cuando alguno de sus elementos se vuelva cero, indica que el valor asociado a una variable en ese elemento deberá de ser removido ( p.e. en Contador[ (x0, x2), 1 ] = 0, 1 deberá ser removido de x0).

2643.gif

La estructura Soporte contribuye a hace más eficiente el proceso de chequeo llevado a cabo para forzar la Consistencia de Arco. Al mantener un registro de que pares (variable, valor de dominio) están asociados a cada par (variable, valor de dominio) facilita la búsqueda de los elementos que se deben de checar al borrar un valor de una variable específica. La estructura Soporte se refleja en la Figura 2.19.

2644.gif

La implementación del Algoritmo Ac4 se centra relativamente en la creación de una función que permita aplicar las dos estructuras antes mencionadas. El algoritmo que sirve de base, obtenido de [15], emplea en parte la estructura de la función ForzarConsistencia( ), utilizada para resolver el Algoritmo Gac3. Para Ac4 también se genera una función  ForzarConsistencia( ) que hace uso de una pila, para mantener un control sobre los pares (variable, variable de dominio) que deberán de ser analizados.

2645.gif

A diferencia del algoritmo de ForzarConsistencia( ) diseñado para Gac3, el de Ac4 no requiere del uso de alguna función adicional.

2.3.2.5 Algoritmo de Retroceso incorporando Consistencia de Arco de nivel 7 (Gac7)


Este es el último algoritmo de retroceso por analizar. Gac7, al igual que Ac4, contempla el uso de 2 estructuras auxiliares,  soporte y valores, con las cuales se mantiene información de relativa importancia sobre el ejemplar que se pretenda solucionar.

La estructura soporte es una estructura tridimensional por que para tener acceso a ella se necesitan tres parámetros, una restricción c, alguna variable xi   c y algún valor a    xi. Se almacenará en esta estructura el conjunto de tuplas que son el soporte actual para algunos valores sobre c tal que su variable xi tome el valor de a. El ejemplo de esta estructura se muestra en la Figura 2.21.
2646.gif

La estructura valores es de tipo bidimensional. Sus parámetros son una restricción ci, y una tupla t   ci. El con propósito de esta estructura es mantener un seguimiento sobre las etiquetas a las cuales sirve de sopórtela tupla t en la restricción ci. La aplicación de esta estructura se refleja en la Figura 2.22.

2647.gif
Figura 2.22. Estructura valores del Algoritmo Gac7 para el Problema CSP de la Figura 2.8.

Las estructuras se emplean para encontrar algún soporte para una etiqueta    (xi, a) que haya sido removida por la propagación del efecto de borrado de otra etiqueta (xj, b). Si la etiqueta (xi, a) no encuentra algún soporte, entonces el valor a deberá de ser removido de xi y se deberá propagar el efecto de esta eliminación hacia el reto del problema.

La inclusión de este control de Consistencia de Arco en un Algoritmo de Retroceso se lleva a cabo mediante la implementación de una función ForzarConsistencia(), la cual se muestra en Figura 2.23.

2648.gif

La función ForzarConsistencia() requiere de la llamada a una función que propague el efecto de borrar un valor del dominio de una variable, esta función se denomina Propagar( ), y mediante la etiqueta (xi, a) borrada y las restricciones ci en las cuales está involucrada la variable xi va a ubicar en Soporte(ci, xi, a) las tuplas t que eran soporte para la etiqueta eliminada para analizar el efecto que causo sobre esas tuplas el borrar (xi, a). Si los pares (xj, b)   t no tienen soporte, el valor b deberá de ser eliminado de xj, y se deberá de propagar el efecto de (xj, b).

2649.gif
Para encontrar soporte a una etiqueta se usa la función EncontrarSoporte( ). En esta función se usa la estructura soporte para indicar que tuplas quedan todavía como soporte para la etiqueta (xj, b) todavía quedan disponibles, de existir alguno se introduce en la estructura valores(ci, t) y se sigue con el análisis. Si no existe ningún soporte para la etiqueta entonces se remueve b del dominio de xj. Si D(xj) se vuelve vacío entonces el problema se hace inconsistente y se tiene que efectuar un retroceso.

2650.gif

Figura 2.25. Función EncontrarSoporte( ) del método gac7 que se encarga de buscar soporte para tuplas inválidas.


2.4 Algoritmo de Ramificación y Acotamiento


Esta es otra técnica algorítmica para resolver problemas computacionales del tipo de optimización.

Es importante decir, que como se menciona en [4], para poder desarrollar la Ramificación y Acotamiento, basta con implementar una función de cota mínima y otra de cota máxima.

A continuación se mencionan los pasos básicos del Algoritmo de Ramificación y Acotamiento, que de acuerdo a [12] son 4:

Paso 1    [Inicialización]:

Este paso indica la forma en como se va a reflejar el principio del algoritmo, para ello se incluye una cota máxima (o mínima, dependiendo de lo que se desee encontrar) como parámetro de entrada c*, a partir del cuál se van a ir realizando ramificaciones.

Paso 2    [Ramificación]:

En esta etapa el algoritmo lo que va haciendo es siguiendo un camino dirigido de acuerdo a como los resultados de la consistencia preliminar le vayan indicando. Es decir, el algoritmo va asignando variables con valores válidos en esta etapa. El algoritmo se aplica recursivamente a los subproblemas, generando un árbol de subproblemas.


Paso 3    [Acotamiento]:

Esta fase del algoritmo, que junto con la anterior le dan su respectivo nombre, lo que hace es checar valores de la función principal y contrastarlo con el de la cota superior (c*), si el valor actual de la función principal es mejor que el de la cota superior entonces se modifica el valor de la cota al valor de la función actual, esto es para obtener la solución óptima.

Paso 4 [Terminación].

Una vez que todos los nodos han sido revisados (ejecutando repetidamente los pasos 2 y 3), el proceso da por terminada su ejecución, el valor final que contenga c* representará el valor óptimo que resuelva al problema.

Ahora bien, el algoritmo de la Figura 2.26 muestra el Algoritmo de Ramificación y Acotamiento mostrado en [16]. En este algoritmo  interviene una función de Propagar( ) y otra de Restaurar( ).

La función de Propagar( ), como su nombre lo dice, se encarga de propagar el efecto de la asignación de un valor a una variable. Mantiene una similitud con la función de VerificarRestricciones( ) en los Algoritmos de Retroceso, ambas realizan el mismo objetivo, verificar que se sigan cumpliendo las restricciones.

En la función de Restaurar( ) se vuelve al estado en que estaba el problema momentos antes de propagar el efecto de asignar un valor a una variable xi.

2651.gif





Creative Commons License
Estos contenidos son Copyleft bajo una Licencia de Creative Commons.
Pueden ser distribuidos o reproducidos, mencionando su autor.
Siempre que no sea para un uso económico o comercial.
No se pueden alterar o transformar, para generar unos nuevos.

 
TodoMonografías.com © 2006 - Términos y Condiciones - Esta obra está bajo una licencia de Creative Commons. Creative Commons License