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

 

Algoritmos de retroceso parte 1 - 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.




Capítulo 1



Capítulo 1. Introducción



1.1 Antecedentes


En la presente propuesta de tesis, se plantea el uso de Algoritmos de Retroceso como método de solución para el problema del diseño de la  distribución de datos modelado por FURD. Se presentan algunos conceptos básicos sobre las técnicas que se pretenden emplear, así como la descripción de varios algoritmos de retroceso, en particular de aquellos basados en la técnica de Consistencia de Arco.

La razón más importante por la cuál se decidió enfocar el proyecto de residencia en resolver este tipo de problemas fue el hecho de que el modelo FURD se ha resuelto por varios algoritmos heurísticos: Recocido Simulado [22], Búsqueda Tabú [18], Algoritmos Genéticos [11] y Redes Neuronales; pero sólo se ha empleado un algoritmo exacto: Ramificación y Acotamiento [7]. Es por eso que se ha decidido llevar a cabo la investigación y tratar de darle solución al modelo FURD mediante otro método exacto: Algoritmos de Retroceso, tratando de verificar el comportamiento de otras técnicas, no utilizadas, y ver que nuevos resultados se obtienen.

Ahora bien, relativo a la importancia de este tema de estudio se hace referencia al hecho de que actualmente las bases de datos distribuidas representan una importante área de estudio debido a la globalización actual. en particular las fases de diseño y distribución de la base de datos son de gran importancia ya que influyen mucho en el desempeño de la misma. Debido a que el Modelo FURD permite optimizar el diseño de la distribución de datos en una red entonces si se profundiza en este tema de estudio, se podrá tener mejores herramientas para el futuro de las bases de datos distribuidas.

1.2 Objetivos


La presente tesis tiene por objetivo el diseñar e implementar un conjunto de algoritmos que permitan resolver el problema de la distribución de datos Modelado por FURD (Fragmentación, Ubicación y Reubicación Dinámica de Datos) presentado en los sitios de una red al momento de compartir información proveniente de una base de datos distribuida. En particular se implementarán algoritmos de retroceso  para la solución del problema.

El objetivo específico es dar pauta al rediseño y adaptación de programas capaces de resolver el Modelo FURD empleando técnicas algorítmicas de solución exacta y reglas heurísticas que permitan hallar una solución de manera rápida y eficiente, sin consumir mucha memoria.

1.3 Restricciones


Las restricciones que se pueden encontrar durante la implementación de las técnicas algorítmicas pueden afectar tanto  a: el tiempo de solución empleado, como a la cantidad de memoria consumida, entre otros.

El tiempo de solución empleado se ve afectado por la velocidad del procesador con el cual se esté trabajando, mientras más rápido sea éste, mejor será el tiempo de solución de la instancia tratada. Sin embargo, existe otro factor que también influye en este aspecto, y éste es el hecho de que se encuentren programas en ejecución al mismo tiempo que se corre la instancia. Por eso es recomendable trabajar sin ningún programa residente en memoria.

La memoria consumida depende del tamaño de la instancia y del número de variables que esta genere. Estos dos factores determinan una limitante para la instancia, si tienden a consumir mucha memoria principal entonces se necesitará contar con suficiente memoria para resolverlos, de lo contrario será imposible.

En conclusión, es posible que las limitantes básicas sean referentes al equipo de trabajo y al tiempo requerido para la solución. Para solucionar estas restricciones se recomienda emplear equipos más potentes.

1.4 Justificación


Las bases de datos de hoy en día y las redes computacionales luchan por la necesidad de contar con una mejor distribución de sus recursos. La información es el recurso más importante de ambos, por eso es necesario involucrarle cierto grado de interés. Mientras mejor esté distribuida la información, más fácil y eficiente será su acceso. El Modelo FURD y trata de encontrar la mejor ubicación de los datos de acuerdos a las características de los sitios que posee una red, basándose para ello en la fragmentación inicial de datos y en la posterior ubicación de fragmentos.

Además de lo mencionado anteriormente, también se incluye el deseo de ampliar los conocimientos existentes sobre técnicas algorítmicas que dan solución al Modelo FURD, tratando de proporcionar con este proyecto nuevos resultados que pudieran ser relevantes al área.

1.5 Producto Final


Como producto final de la tesis se entrega un programa que permite resolver el problema de la distribución de datos en bases de datos distribuidas modelado como CSP, empleando para ello el modelo matemático conocido como FURD (Fragmentación, Ubicación y Reubicación dinámica de Datos) y una serie de algoritmos de retroceso.  Se espera que sirva de base para futuras investigaciones relacionadas con el tema.


1.6 Contribución Esperada


La contribución que se da con esta investigación es un marco de referencia sobre el comportamiento de los algoritmos de retroceso en la solución del Modelo FURD. Es decir, en base a los datos recolectados mediante la experimentación se indican las ventajas y desventajas que posee el procedimiento desarrollado para resolver el problema de la distribución.


1.7 Organización del Documento


Este documento se encuentra dividido en 6 capítulos. En el capítulo uno se encuentra la introducción a la tesis; se mencionan sus objetivos y restricciones, así como las razones por las cuales se decidió elaborarse; también se incluyen una pequeña descripción del producto final que se obtiene y la contribución que se hace con la tesis. Es en esta parte donde se encuentra incluida esta sección.

El capítulo dos desarrolla el marco teórico en el cual se fundamente la tesis. Contiene conceptos básicos sobre técnicas algorítmicas y heurísticas, y describe las herramientas empleadas para desarrollar el programa implementado. En este capítulo se concentra todo el material recopilado de las diferentes literaturas consultadas.

El capítulo tres es el capítulo de la experimentación. Describe la metodología empleada para poder darle seguimiento a la tesis, como se seleccionaron los casos de prueba, que equipo se empleó, cuál fue el orden de desarrollo del trabajo.

Dentro del contenido del capítulo cuatro se mencionan los resultados obtenidos por la experimentación que se menciona el capítulo tres. Se describe en forma exhaustiva el producto final de la tesis.

El capítulo 5 describe la contribución de la tesis en toda su extensión. Por último, en el capítulo 6 se dan las conclusiones y se presentan los trabajos futuros para este documento. Aparte de esta organización inicial, también se incluye una sección de bibliografía empleada, otra de glosario y una de anexos.


Capítulo 2



Capitulo 2. Revisión Bibliográfica



2.1 Antecedentes


Dentro de este documento se encuentra un marco de referencia bibliográfico que orientará, a quien lo lea, sobre el contenido de la propuesta de tesis que se plantea elaborar.

En los párrafos que se mostrarán en la sección de contenido se incluirán la razones por las cuales se seleccionaron las referencia bibliográficas que se tienen al final del documento, así como algunas de las ideas principales que fueron tomadas de ellas.
.
A manera de resumen, el contexto que se muestra refleja lo que son los Algoritmos de Retroceso, su aplicación en el campo de la investigación, cómo se define al problema de la distribución de datos y algunos otros conceptos básicos.

2.2 Definición de Problemas de Satisfacción de Restricciones (CSP)



Según [20], [10] y [6] un Problema de Satisfacción de Restricciones o CSP (por sus siglas en inglés, Constraint, Satisfaction, Problem) es una tripleta (X, D, C) donde X es un conjunto de n variables, D es un conjunto de dominios finitos sobre las variables y C es un conjunto de m restricciones aplicables al  conjunto de las variables en X. La meta de esta tripleta es encontrar una o todas las soluciones para el problema CSP, en el cuál una solución representara una asignación de valores a   D(X) a sus variables X de tal forma que satisfagan cada una de las restricciones C que se presentaran para el ejemplar del problema tratado.

En esta tesis se identifican dos tipos de restricciones para los problemas CSP, las restricciones explícitas y las restricciones implícitas. Las primeras son aquellas que se pueden incluir como parte del conjunto de restricciones del problema, poseen una serie de tuplas válidas que las identifican, y forman parte de cualquier ejemplar que represente al tipo de problema básico (CSP). Por otra parte se encuentran las restricciones implícitas, que se basan en condicionales y, debido a esta característica, no poseen un conjunto de tuplas válidas, se construyen mediante código (sentencias condicionales) dentro del programa que los resuelve y no se pueden manipular directamente en los ejemplos de problema. Otra forma de definir a estos tipos de restricciones es como se menciona en [24], que dice que cuando las restricciones son especificadas en forma explícita, es decir, cuando se enumera todo el conjunto de tuplas válidas, se dice que son almacenadas en extensión o extensionalmente de otra forma estarán almacenadas intencionalmente.

Con el objeto de ejemplificar el problema CSP, a continuación se muestra el Problema del Crucigrama (crossword).

El Problema del Crucigrama se encuentra formado por un tablero y  un diccionario. El tablero es un matriz bidimensional (como la mostrado en la      Figura 2.1) formada por espacios y blancos. El diccionario es el conjunto de palabras válidas que se pueden admitir para dar solución al Problema del  Crucigrama.

26241.gif

Figura 2.1.  Tablero. Una B representa un blanco, mientras que una E  representa un espacio.

Para ejemplificar el Problema CSP mediante el Problema del  Crucigrama se necesita transformar este último mediante alguno de los modelos existentes: el modelo letra, dual y el modelo oculto. En [24] y en [20] se muestra la definición de los tres métodos de modelado previamente mencionados, los cuales trabajan de la siguiente manera:

-    El Modelo Letra.

En este método las variables que pasarán a constituir el problema CSP serán cada uno de los espacios que contenga la matriz del Crucigrama. Por lo tanto, el dominio de cada una de las variables estará constituido por las letras del alfabeto que forman las palabras del diccionario. Por su parte, las restricciones estarán formadas por cada palabra que se encuentre en el Crucigrama.

-    El Modelo Dual.

Mediante este modelo las palabras que componen al Crucigrama pasan a formar las variables duales de su equivalente Problema CSP. Su dominio será el tamaño del diccionario con que se cuente. Las restricciones serán de carácter binario entre las variables, asegurando que las palabras que sean asignadas, sean consistentes para el problema.

-    El Modelo Oculto.

  Esta técnica se podría considerar como una combinación de las anteriores, es decir, las variables del Problema CSP equivalente desarrollado por el Modelo Oculto, son los espacios y las palabras que componen el crucigrama. El dominio dependerá de la variable que se trate, pero solamente podrá ser cualquiera de estos dos: el alfabeto manejado o el diccionario empleado. Las restricciones fuerzan a una asignación compatible entre una variable letra (espacio) y una variable palabra.

El método completo para transformar un ejemplar del Problema del Crucigrama a CSP empieza seleccionando alguno de los modelos mencionados en los párrafos anteriores. Para ejemplificar esto se muestra el ejemplar de Crucigrama mostrado en la Figura 2.2.

26251.gif

Figura 2.2. Un ejemplar del Problema del Crucigrama.

Una vez que se ha definido qué ejemplo va a ser el que se traduzca a  CSP, se selecciona el método para llevar a cabo el modelado. En este caso se seleccionó el Modelo Letra. Al  tener seleccionada la técnica, se procede a la transformación del problema.

Lo primero que se menciona en el Modelo Letra es que las variables que pasarán a constituir el problema CSP, estarán formadas por los espacios que se encuentren en el tablero del crucigrama. El resultado de este paso se ilustra en la Figura 2.3.

2626.gif

xo    x1
x2    x3    x4
x5    x6

X = { x0, x1, x2, x3, x4, x5, x6 }
Figura 2.3. Conjunto de variables X para el Problema CSP.

Lo siguiente es determinar el dominio de  cada una de estas variables. Como se muestra en la Figura 2.4, debido a que las variables representan letras del alfabeto entonces, su dominio estará comprendido por aquellas letras que se puedan usar para formar palabras del diccionario.

26271.gif

Figura 2.4. Variables xi y sus Dominios D(xi) para el problema CSP.

Por último, se identifican las restricciones a las que estará sujeto el Problema del Crucigrama, ya como Problema CSP. En el ejemplo manejado, las restricciones encontradas son las que se muestran en la Figura 2.5. Sus respectivos dominios estarán compuestos por las palabras que posea el diccionario del crucigrama.
26281.gif

Figura 2.5. Restricciones C del problema CSP.

Con esto se da por terminado el algoritmo para modelar un Problema de Crucigrama a Problema CSP. La misma técnica se puede emplear para transformar cualquier otro tipo de problema en CSP. El problema CSP resultante del crucigrama de ejemplo mostrado, queda resumido en la Figura 2.6.

26291.gif
Figura 2.6. Problema del Crucigrama modelado como CSP.

El problema CSP se puede resolver, de acuerdo a [14], mediante un paradigma  de Retroceso (Backtracking), el cual consiste en ir asignando valores a las variables que componen una restricción y una vez que se complete una se verifica su validez. De esta forma se sigue hasta encontrar una solución que satisfaga todas las restricciones o bien se viole alguna, generándose entonces un retroceso. Este tema será visto posteriormente.

Debido a la amplia gama de algoritmos de retroceso disponibles para la solución en problema modelado como CSP, se pretende emplear un método de conversión de ejemplares FURD a ejemplares CSP, con el fin de aprovechar el conjunto de algoritmos existentes, para darle solución al modelo FURD.


2.3 Algoritmos para Solucionar CSP



Dentro de los problemas de computación, existe un tipo en especial de problemas que, para encontrar su solución, requiere de la combinación de varios componentes. Es decir, forman un espacio de soluciones dependiendo de las características del mismo. Para hallar la solución óptima escogen de entre ese espacio de soluciones, aquella que satisfaga todas las restricciones que se presenten para el caso tratado. El Problema CSP, que se mencionó en el apartado anterior, es uno de esos problemas. Cuando se tiene un ejemplar del Problema CSP,  éste posee un espacio de soluciones el cual puede ser identificado  empleando algoritmos adecuados.

La primer técnica que se analiza para resolver CSP es el paradigma que se menciona en [14],  Generar-y-Examinar (o Paradigma GT, de sus siglas en inglés          Generate-and-Test), el cual parte del principio de que cada una de las posibles combinaciones obtenidas a través de la asignación de valores de dominio a las variables, representa una posible solución al problema. Si una o más de esas combinaciones satisfacen las restricciones del problema, entonces pasarán a formar parte de su espacio de soluciones.

26301.gif
Figura 2.7. Algoritmo de  Generar-y-Examinar.

En el algoritmo de GT aparecen tres procedimientos que llevan a cabo un papel singular. En primer lugar se encuentra la función VerificarRestricciones( ). Esta función lo que hace es verificar que las asignaciones de valores a variables sean consistentes, es decir, que satisfagan todas las restricciones. De ser así devolverá verdadero, de otro modo regresará falso. La siguiente función a analizar  es SiguienteVariable( ), la cual mantiene un control sobre las variables que han sido asignadas durante la llamada a la función Generar-y-Examinar( ). Esta función recibe de parámetro el nivel de recursión actual, y de acuerdo a éste devolverá la siguiente variable que debe de ser asignada. Por último, se encuentra el procedimiento DesasignarVariable( ), que deberá borrar cualquier contenido previo de la variable que le sea pasada como parámetro.

A pesar de la relativa sencillez de GT, la eficiencia del mismo no es muy significativa. Por esta razón se muestra otra de las técnicas más comunes empleadas para la solución de un Problema CSP: el Paradigma de Retroceso (BT, de su referencia en inglés, Bactracking).

En algoritmia un método para dar solución a los ejemplos de Problemas CSP, de acuerdo a [1] y [12], es mediante un árbol, donde se van construyendo y analizando las alternativas, de forma que se descartan ramas que no son viables para hallar una solución.

Ahora bien, tanto el Paradigma Generar-y-Examinar como el Paradigma de Retroceso representan la implementación algorítmica del estándar definido en [15] como solucionador de Problemas de Satisfacción de Restricciones: el árbol de búsqueda.

Debido a que BT posee casi el mismo criterio de desarrollo que  GT, se puede considerar como una mejora al mismo. Según [20], el Paradigma de Retroceso va asignando valores a variables en forma secuencial, por cada asignación se va realizando una verificación de restricciones. Si durante la verificación se identifica 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 ejemplar.

En esencia, como se dice en [14], el Método de Retroceso desarrolla una búsqueda en profundidad del espacio potencial de soluciones del problema CSP.

A pesar de esta mejora, la eficiencia del algoritmo sigue siendo muy pobre. Es posible reflejar que esta técnica pasa por alto la consistencia del problema mediante la verificación de las variables que faltan por asignar y sus valores. Cuando se asigna un valor a una variable es posible que valores de otras variables pierdan consistencia, y por tanto, no deban de ser analizadas y se tengan que eliminar de sus dominios. A ésta definición se le denomina Consistencia de Arco, la cual va a ser el siguiente tema de estudio de la sección.

2.3.1 Consistencia de Arco



La consistencia de arco es la forma de decir que el dominio de las variables se comporta en forma consiste de acuerdo a las restricciones que se presentan, es decir, no existen valores que sean redundantes o inválidos  y que se puedan  asignar a las variables, dentro de sus dominios. De acuerdo a [9] cuando una variable es asignada, ella y otras quedan inconsistentes en algunos de sus valores asignados, debido a esto, es necesario aplicar ciertas técnicas para devolverle al problema su estado de consistencia de arco.

Para revisar más a fondo lo que es la Consistencia de Arco verifiquemos el siguiente ejemplo visto en [14]:

Supongamos que las variables de un problema se asignan en orden ascendente v1,  v2, … vi, vj, vn. Si alguna de las restricciones entre las variables vi y vk hace que cuando vi tome el valor de ‘a’, vk no pueda tomar ningún valor de su dominio entonces, cuando vi sea igual a ‘a’ en el árbol de búsqueda formado por el  Algoritmo de Retroceso la búsqueda fallará cuando intente asignar algún valor a  vk (debido a que ninguno puede ser asignado). Este proceso se repetirá tantas veces como formas posibles de llegar a vk a partir de vi existan, dando lugar a una inconsistencia por parte del nodo vi.

Para ejemplificar lo que es la Consistencia de  Arco, analicemos un ejemplo sencillo del Problema CSP mostrado en la Figura 2.8.

2631.gif
Figura 2.8. Ejemplar de un Problema del Crucigrama modelado como CSP.

Como se muestra en la Figura 2.8, el problema consta de tres variables (x0, x1, x2) las cuales tienen dominios iguales (0, 1) y se encuentran limitadas por dos restricciones (c0, c1). En las restricciones de los Problemas de  Crucigrama, cuando son modelados como CSP, existe un particularidad muy importante y ésta es que el orden de las variables es importante, por ello debe tenerse cuidado en su manejo. Ahora bien, si el ejemplo descrito se muestra mediante un grafo, su definición quedaría como aparece en la Figura 2.9.

Como se aprecia en el grafo, si se asigna a la variable x0 el valor de 1, la variable x2 no podría tomar ninguno de sus valores. Esto es debido a que la  restricción c1, que limita o interrelaciona a ambas variables en el problema, no permite que la variable x2 tome algún valor cuando x0 sea igual 1.  Para que x2 pudiese ser consistente cuando x0 fuera igual a 1, se necesitaría la existencia de cualquiera de las tuplas  [10] o [11] en la restricción c1, lo cuál no se tiene para este problema de ejemplo.  Por otra parte, se analiza la restricción c0, se ve que para cada valor que sea asignado a x1, x2 tendrá algún valor para asignar.

2632.gif

Figura 2.9. Grafo de un problema CSP sin Consistencia de Arco.

Con la definición otorgada en el párrafo anterior se puede decir entonces que el problema es inconsistente en x0 ya que no todos los valores que se puedan asignar a x0 permitirán a x2 tomar alguno de los que él posee. Para que el problema sea consistente, deberá por lo tanto de eliminarse el valor 1 del dominio de la variable x0, de esta forma cualquier valor que ésta tome le permitirá a x2 ser asignado posteriormente. Si aplicamos esta regla, tendremos entonces que el problema tiene Consistencia de Arco, lo cual agilizaría la resolución de cualquier Problema CSP que sea resuelto mediante el Paradigma de Retroceso. En la Figura 2.10 se muestra el ejemplo de CSP con Consistencia de Arco.
Una vez revisada la forma práctica en que se refleja la Consistencia de Arco en un Problema CSP, ahora sigue definirlo teóricamente. Una vez que se han analizado todos los conceptos básicos que intervienen en la Consistencia de Arco y empleando la definición que aparece en [20] se concluye que:

“Dado un Problema CSP P = (X, D, C), donde c   C es una restricción, y            x    X(c) es una variable involucrada en c. Un valor a   D(x) es consistente con c si existe al menos una tupla t   c tal que  el valor a tomado por la variable x que la forma, siga haciendo válida a la tupla t. La tupla t podrá ser llamada entonces un soporte para la etiqueta (x, a) en c. La restricción c tiene consistencia en arco si para toda x    X(c), D(x)     y para toda a   D(x), a es consistente con c. El problema P es arco consistente si todas las restricciones en C son arco consistentes.”

Dicho de otra forma, si para cada valor posible que se puede asignar a cada variable en un Problema CSP, existe alguna tupla que permita tal asignación entonces el cumplirá con la definición básica de Consistencia de Arco. De otro modo el problema será inconsistente y si se sigue un Paradigma de Retroceso para resolverlo, es posible que realice operaciones innecesarias o que se podría evitar.

2633.gif

Figura 2.10. Grafo de un problema CSP con Consistencia de Arco.

Volviendo de nuevo cuenta al caso de Ejemplo, si al ejemplar inicial, mostrado en la Figura 2.9, le aplicamos la definición de  Consistencia de Arco obtenida, se tendrá como resultado algo similar a la información mostrada en la Tabla 2.1.

2635.gif

Tabla 2.1. Ejemplar de un Problema CSP sin consistencia de arco





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