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

 

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




2.5 El Problema de la Distribución de Datos


En [23], [9] y [2] se presenta el problema de distribución de datos, su fragmentación y reubicación de manera que se optimice la estancia de ellos dentro de los nodos de una red, para su administración por la base de datos.

Una etapa del desarrollo de un Sistema de Base de Datos Distribuidas es el diseño de la distribución cuya finalidad es determinar las unidades de almacenamiento adecuadas y decidir la ubicación de estas en cada sitio de la red, los fragmentos pueden ser horizontales, verticales o mixtos [21].

El Modelo FURD, presentado en [17], ha sido desarrollado para resolver el problema del diseño de las Bases de  Datos Distribuidas, el cual de acuerdo a [3], esta divido en dos etapas o fases: la fragmentación y la ubicación de fragmentos. Estas fases ya se concentran en el  Modelo FURD.

Una vez que se resuelve el Modelo FURD se puede dar solución al problema del diseño. Sin embargo la dificultad radica precisamente en la forma de resolverlo, pues es un problema de optimización muy complejo que a medida que va creciendo su tamaño, se va haciendo más difícil la forma de resolverse.

En el Modelo FURD, la decisión de almacenar un atributo m en un sitio j es representada por una variable binaria xmj.  Así xmj = 1 si  m se almacena en  j, y    xmj = 0 en caso contrario.

La función objetivo modela los costos de transmisión y el acceso a los datos usando cuatro términos. El primer término modela los costos de transmisión ocasionados por la transmisión de los datos necesarios para satisfacer las consultas de todos los sitios. El segundo término  modela los costos en los que se incurre en consultas que acceden a varios fragmentos; en este caso, el diseñador tiene que proporcionar el valor de un parámetro que indique el costo de acceder a varios fragmentos. El tercer término modela los costos de almacenamiento de los fragmentos en los sitios. Debido a que este costo puede variar de un sistema administrador de bases de datos a otro, este  aspecto se incluye como un parámetro cuyo valor tiene que ser proveído por el diseñador de la base de datos. El cuarto término modela los costos de transmisión  requeridos para migrar los datos de un nodo a otro.

En lo que sigue, k, i, j y m denotan consultas, sitios de consultas, sitios de atributos, y atributos, respectivamente, siendo cl, s, y t el total de consultas, sitios y atributos.

El modelo matemático que se resuelve es :
2652.gif

Donde:

2653.gif

Dado que no se considera la replicación de atributos, se tiene una restricción que especifica que cada atributo será ubicado solamente en un sitio. Adicionalmente, cada atributo debe ser ubicado en un sitio que al menos ejecute una consulta que acceda al atributo. Estas restricciones se expresan de  la siguiente manera:

26542.gif

El desarrollo de este modelo da como resultado un problema de optimización complejo el cual se resuelve mediante los algoritmos de retroceso propuestos anteriormente.

Capítulo 3


Capitulo 3. Metodología y Métodos


En el área que abarca la tesis NO es posible aplicar los métodos cualitativos o cuantitativos, debido a que estos métodos sirven para llevar a cabo investigaciones de campo enfocadas a las Ciencias Sociales. Para poder llevar la investigación a la realidad es necesario definir el área a la que pertenece el trabajo, que en este caso es la de Ciencias Exactas. Con el fin de poder obtener datos que ayuden a analizar la investigación, la metodología que se siguió es la de experimentación; la cual es desarrollada mediante la selección de una serie de casos de prueba (ejemplares del Modelo FURD), su ejecución mediante los programas desarrollados y la verificación del comportamiento de los programas.

En otras palabras, para poder obtener un análisis de la investigación y tener información relevante se generaron una serie de pruebas que incluyen ejemplares del problema de la distribución modelados como problemas de satisfacción de restricciones, estas pruebas se ejecutaron en los programas diseñados para resolver el Modelo FURD y se analizó en ellas el tiempo consumido por dichos programas para encontrar la solución. Se llevó un registro de cada una de las instancias en cuanto a la cantidad de variables generadas para el problema, el tiempo tardado por cada algoritmo de retroceso en resolverlas y se infirió una conclusión en particular de acuerdo a los datos obtenidos. La razón por la cual se tomó esta metodología de investigación de campo es por la característica del tema de tesis que se esta desarrollando.

Como ya se mencionó, la experimentación es la base de la investigación de campo de esta tesis. Para poder llevarla a cabo se requirió de la definición de los algoritmos que permitieran resolver los ejemplares del Modelo FURD. En el siguiente capítulo se mostrará la forma en que fue desarrollado el proyecto de investigación.


Capítulo 4



Capítulo 4. Resultados de la Investigación



4.1 El Problema de la Distribución de Datos como Problema de Satisfacción de Restricciones



Para poder dar solución al tema de tesis es necesario considerar varios aspectos.  En primer lugar, debido a la complejidad del Diseño de la Distribución se decidió modelarlo mediante el modelo FURD descrito en el capítulo 2.

Para solucionar un ejemplar del modelo FURD mediante algún algoritmo de retroceso es necesario modelarlo como un caso CSP y tomar en cuenta que FURD modela un problema de optimización, en este caso de minimización, y CSP modela un problema de decisión, cuyo objetivo es encontrar una solución válida y no necesariamente la de mínimo costo.

Para poder modelar FURD como CSP se utilizan seis parámetros del ejemplar proporcionado, que son: el número de atributos (m), el número de sitios de atributos (i), el número de sitios de consultas (j), el número de consultas (k), la matriz qkm y la matriz fki. A un ejemplar del modelo FURD que contenga solo estos parámetros se le llamará en lo sucesivo ejemplar reducido del modelo FURD. En la Figura 4.1 se muestra un ejemplo.

m    = 3     (atributos)
i    = 2    (sitios de atributos)
j    = 2    (sitios de consultas)
k    = 2    (número de consultas)

2655.gif
Figura 4.1. Parámetros de un ejemplar reducido del modelo FURD.

A partir de la variable de decisión xmj se obtiene el conjunto X, cada celda de la matriz es un elemento de dicho conjunto, de esta manera la cardinalidad de X es   m x j.

El dominio de todas las variables será el mismo {0,1}, ya que la variable de decisión xmj es binaria.

Para generar el conjunto C primero se analizará la primera restricción del modelo FURD. Esta restricción fuerza a que un atributo se almacene solo en un sitio, es decir no se permite la duplicación de atributos, visto de otra manera, la sumatoria de todos los valores de las celdas de cada renglón de la matriz solución xmj debe dar exactamente uno, por tanto se debe generar una restricción CSP por cada renglón de la matriz xmj, y las tuplas válidas para cada una de las restricciones generadas serán todas las combinaciones válidas de valores (0,1) cuya suma sea igual a uno, en la Figura 4.2 se muestra como quedaría modelada la primera restricción de FURD.

2656.gif

La siguiente restricción a analizar es aquella que obliga a almacenar un atributo en un sitio que al menos ejecute una consulta sobre dicho atributo. Para poder modelar esta restricción hay que expanderla tal como se muestra en la Figura 4.3. La matriz  ki se obtiene a partir  de la matriz fki como se explica en la restricción (3).

2657.gif

La única variable que se restringe es x12, ya que al expandir la restricción, se obtiene que el valor que puede tomar debe ser menor o igual a 0, por tanto como la variable es binaria solo podrá tomar el valor de 0, mientras que el resto de las variables quedan irrestrictas pudiendo tomar los valores 1 o 0.

Como se puede observar, solo se restringen aquellas variables que deban ser igual o menor que cero.

Para incorporar esta restricción a la instancia modelada CSP, se puede reducir el dominio de las variables restringidas, permitiendo que solo tomen el valor de cero, o se puede reducir el conjunto de tuplas en la restricción correspondiente, eliminando aquellas tuplas que permitan la asignación de uno a la variable restringida, en la Figura 4.4 se muestra un ejemplo de cómo quedaría finalmente la instancia FURD modelada como CSP.
2658.gif

4.2 Diseño de los Algoritmos para Solucionar el Modelo FURD


Para poder resolver un caso del modelo FURD inicialmente se transforma en un problema de tipo CSP, siguiendo la estructura que se menciona en la sección anterior.

Una vez que se tiene un ejemplar del Modelo FURD en su equivalente CSP se procede a aplicar un algoritmo que permita encontrar su solución.

Debido a que el problema CSP es un problema de decisión y por lo tanto, las técnicas que se emplean para resolverlo lo resuelven como tal, entonces intentar resolver el Modelo FURD como problema de decisión implicaría integrar algunas actividades adicionales con el fin de poder encontrar la solución óptima. Esto es, si se aplica un algoritmo de retroceso para resolver el Modelo FURD, este encontraría una solución, la primera, o bien todas las soluciones. Para poder determinar la solución óptima se tendría que comparar cada una de las soluciones de forma que se encontrase aquella que minimizará la función objetivo. Si se sigue este criterio, el algoritmo resultante para solucionar el Modelo FURD puede llegar a perder mucho tiempo en la búsqueda de todas las soluciones y en la posterior búsqueda de la solución óptima.

Otra forma de resolver el Modelo FURD es emplear un algoritmo para solucionar problemas de optimización, como por ejemplo el algoritmo de Ramificación y Acotamiento (R&A). Este algoritmo mantiene una cota superior) que permite determinar el límite superior sobre el cual no deberá de pasar el valor de la solución óptima. Si durante el proceso de búsqueda se obtiene una solución parcial cuya evaluación en la función objetivo exceda el mejor valor que se tiene hasta el momento (almacenado en la cota superior), el algoritmo detendrá la búsqueda (el árbol podará la rama) para continuarla en una nueva rama del árbol de búsqueda. Cada vez que algoritmo encuentra una solución mejor que la cota superior, sustituirá esta última por la nueva solución, asegurando que cuando termine el proceso, se tenga la solución óptima.

Si se emplea el algoritmo de R&A para solucionar el Modelo FURD es posible que se pierdan las ventajas que se le podrían dar al problema cuando se modela como CSP, entre ellas que se puedan hacer análisis previos de consistencia para evitar explorar nodos inútiles.

Debido a las cualidades que tiene por separado ambos algoritmos, en esta tesis se propone, para dar solución al problema de la distribución de datos, modelado como FURD, el desarrollo de un algoritmo de retroceso que incorpore R&A para aprovechar al máximo las características del problema a resolver, tratando de asegurarle un comportamiento eficiente.

El algoritmo que se implementó, se creó a partir del esquema general de algoritmos de retroceso que se muestra en la Figura 4.5, en conjunción con el algoritmo de R&A mostrado en la Figura 4.6.

2659.gif

El esquema mostrado en la Figura 4.5 representa una base para todos los algoritmos de retroceso existentes. En el algoritmo general se perciben los elementos básicos de cualquier paradigma de retroceso, que deberán incluirse para que conserve sus características.

2660.gif
La principal diferencia que existe entre el algoritmo de retroceso y el de R&A es que en el algoritmo de retroceso existe la posibilidad de revisar la consistencia del caso a analizar, mediante técnicas para forzar la consistencia de arco, y en el algoritmo de R & A se puede encontrar la solución óptima mediante el uso de una cota máxima (c*) que limite la búsqueda de la solución a medida que se avanza en el problema. La forma en que queda el algoritmo que incorpora tanto el Paradigma de Retroceso como el de R&A se muestra en la Figura 4.7.

26611.gif

En este algoritmo se nota la presencia de una cota superior (c*) y de una función Limite() que se encargará de hacer un cálculo parcial de cada nodo que se vaya obteniendo en el algoritmo.

A partir del algoritmo mostrado en la Figura 4.7 se implementan diversas variantes. La principal diferencia de los algoritmos implementados radica en la forma de elegir las variables a asignar (técnica de ordenamiento de variable) y el nivel de consistencia aplicado.

A continuación se presenta la regla heurística que permite seleccionar el orden de asignación de las variables que constituyen el problema. Esta regla fue la de donde:
tamaño del dominio de la variable xi = | D(xi) |
grado de la variable xi = | { xj   X | xj != xi y xj esta relacionada con xi } |

La consistencia de arco fue necesaria para la implementación de algunos de los algoritmos. Inicialmente se mantuvieron tres algoritmos que incluían el  manejo de consistencia de arco:

1.    El algoritmo de retroceso incorporando GAC3
2.    El algoritmo de retroceso incorporando AC4
3.    El algoritmo de retroceso incorporando GAC7

Sin embargo debido a que los resultados mostrados en la Tabla 4.1 que reflejaban la superioridad de GAC3 sobre GAC7, el número de algoritmos que hacen uso de la consistencia de arco se redujo solamente a dos, el GAC3 y el AC4, los cuales demostraban una cualidad competitiva entre ellos, es decir para algunos ejemplares Gac3 resultó tener mejores tiempos y para otros AC4.

tamaño del dominio de la variable
———————————–
grado de la variable

2663.gif

Tabla 4.1. Tiempo en encontrar una solución a la instancia dada del problema del crucigrama
Por último, para poder implementar la parte correspondiente a R&A, se implementó un función de cálculo parcial de Z de la función objetivo que plantea el modelo FURD. Esta función sustituye a la función Límite( ) en el algoritmo rediseñado.

El cálculo parcial de Z se realiza a medida que se va asignando cada variable del ejemplar. Si alguna de las variables no ha sido asignada, su valor será igual a cero, de lo contrario tomará el valor que le fue dado. De esta forma se evalúa la función Z para poder determinar si se debe seguir o no explorando por la rama de búsqueda actual.

Con esto se define que los algoritmos rediseñados que se obtuvieron al final fueron:

1.    Algoritmo de Retroceso Cronológico (BC) con R & A
2.    Algoritmo Gac3 con R & A
3.    Algoritmo Ac4 con R & A

Los elementos empleados para el desarrollo de la tesis son de tipo físicos y humanos, dentro de los requerimientos físicos se anota lo que sigue:

- Una máquina computadora con las siguiente características:
o    Procesador Pentium II a 233Mhz.
o    Memoria RAM de 128 Mb.
o    Tarjeta de video con 8Mb.
o    Disco Duro de 20 Gb.
o    Monitor, teclado, ratón e impresora.
- Hojas de papel, bolígrafos y lápices.
- Compilador de  C++
- Ambiente de desarrollo Visual C++ 6.0 o  Borland C++ en cualquier versión
- Sistema Operativo Windows 9x o MS - DOS  en su defecto.
- Cuenta de Internet para acceso a información bibliográfica y comunicación con los asesores.

En cuanto a la infraestructura humana solamente se requirió de los asesores que ayudaron a llevar a buen término el trabajo, así como de personas ajenas al proyecto que contribuyeron en su orientación.


4.3 Experiencia computacional


Dentro de esta sección se describe el comportamiento de los algoritmos rediseñados e implementados sobre algunos ejemplares del Modelo FURD. Los algoritmos fueron: BC, AC4 y GAC3 descritos en la capítulo 2.

4.3.1 Casos de prueba


Los ejemplares del Modelo FURD se clasificaron en tres tipos:
1.    Ejemplares con restricciones de capacidad máxima (todos los sitios tienen la restricción de capacidad)
2.    Ejemplares con restricciones de capacidad media (sólo algunos sitios tienen la restricción de capacidad)
3.    Ejemplares sin restricciones de capacidad (ningún sitio tiene restricción de capacidad)

En la Tabla 4.2 se muestran las características de los casos de prueba.

2664.gif

En la primera columna se lista el número del caso a describir. En el apartado FURD se citan los atributos, sitios, consultas y tipo de capacidad del ejemplar, de acuerdo a su equivalente en el Modelo FURD.

En el apartado CSP se muestran las características del ejemplar una vez que se ha transformado de FURD a CSP. El apartado CSP se compone de: numero de variables, numero de valores y numero de restricciones, estos datos son los componentes del ejemplar ya como CSP.

La última columna posee el valor óptimo de la instancia, su resultado, para contrastarlo al momento de correr la instancia de la implementación del algoritmo rediseñado.


4.3.2 Implementación de los algoritmos rediseñados


En a esta sección se realiza un análisis de la eficiencia de los algoritmos. Con  base en la  información recolectada de los casos de prueba resueltos por los algoritmos, se prueba  la utilidad de los algoritmos para el propósito establecido, solucionar el Modelo FURD.

El algoritmo se implementó con el compilador Microsoft Visual C++ versión 6.0. su estructura le permite ser exportable a otros ambientes de desarrollo que empleen el lenguaje C para el diseño de sus programas.

4.3.2.1 Parámetros del Algoritmo


El algoritmo rediseñado solamente posee un parámetro a incluir. Este parámetro es la cota máxima inicial del problema, a partir de la cual se empezará a hacer las podas necesarias para encontrar la solución del problema.

Para proporcionar este parámetro solamente se requiere correr el algoritmo una vez hasta que encuentre la primera solución. Ésta será la primera cota a partir de la cual se empezará con el recorrido completo del árbol.

4.3.2.2 Estrategia



Antecedentes



Lo que se pretende hacer es correr todas las instancias y verificar que el comportamiento de los algoritmos seleccionados se cruce, para garantizar que la solución de los casos del Modelo FURD no dependen únicamente de un solo algoritmo, sino que de acuerdo a la instancia los resultados pueden ser diferentes.

Los algoritmos fueron diseñados de manera que se pudiese calcular el tiempo total de solución de un ejemplar de FURD. También incorporaron una herramienta que permitía calcular el número de nodos explorados.


Hipótesis



¿Es posible obtener al menos dos algoritmos de retroceso que resuelvan el modelo FURD, y que se crucen en las soluciones obtenidas?


Experimentación



Con el fin de demostrar la hipótesis se corrieron todas los ejemplares de FURD y se creó una tabla de datos junto con su respectiva gráfica, a través de los cuales se infirió el resultado obtenido.

En la Tabla 4.3 se muestran los resultados obtenidos después de correr los casos de prueba que se tenían del  Modelo FURD. Se muestran los algoritmos seleccionados, indicando para cada uno de ellos el tiempo de ejecución logrado para resolver cada una de las instancias, así como el número de nodos que fueron examinados.

2665.gif

Conclusión de la hipótesis



En conclusión se advierte que no existe un algoritmo de retroceso que pueda solucionar el Modelo FURD mejor que los demás. De acuerdo a los resultados mostrados en la Tabla 4.3 y a la forma gráfica mostrada en la Figura 4.8 se logra percibir que el comportamiento de los tres algoritmos es cruzado, es decir, ninguno de los tres algoritmos seleccionados gobierna la resolución de los casos de prueba FURD, y por lo tanto, cualquiera de ellos puede obtener un comportamiento diferente en la solución de un ejemplar FURD, sin tener un indicativo de cual será el mejor.

4.4 Notas de Implementación


El desarrollo de los Algoritmos de Retroceso Cronológico, Retroceso Cronológico incorporando GAC3 y de Retroceso Cronológico incorporando AC4 se llevó a cabo mediante un compilador C++. El diseño del código creado para estos algoritmos les permite ser ejecutados tanto en ambientes de desarrollo como Borland C++ (en las versiones 2.0 y posteriores), así como en Visual C++ 6.0 (trabajando bajo un proyecto de consola).

Los avances que se fueron obteniendo para el algoritmo en cuanto a su implementación dieron lugar a una serie de modificaciones. Esto principalmente debido a que el tiempo de ejecución que se obtenía con las primeras versiones no era aceptable para los propósitos de la investigación.

En forma general para la implementación de los tres algoritmos desarrollados, lo primero que se realizó fue el diseño de una estructura que permitiera manejar cada uno de los parámetros de un Problema de Satisfacción de Restricciones (Variables, Restricciones y sus respectivos dominios), en forma de conjuntos, de manera que la implementación se apegará lo más posible a los algoritmos. Esta estructura fue formada inicialmente bajo el nombre de LCadena, la cual era una clase que encapsulaba funciones para insertar, suprimir, buscar o unir objetos de la misma clase, pero posteriormente fue sustituida por una nueva denominada CSetOrdenado que vendría a incorporar mejoras significativas al programa y finalmente quedaría como la estructura definitiva para la implementación de los Algoritmos de Retroceso.

Las dos limitantes más importantes a las que se afrontaron las dos clases mencionadas anteriormente fueron la memoria consumida y el tiempo de localización de los elementos.

LCadena empleaba una lista enlazada simple para la concentración de sus elementos, mientras que CSetOrdenado mantiene a sus elementos agrupados mediante un arbol 2-3 (el cual se encuentra implementado en la clase CTree23). La ventaja de LCadena radicaba únicamente al momento de querer insertar un elemento, puesto que en el mejor de los casos este se hacia en el orden de O(1) y en el peor en el orden de O(n), sin embargo esto no benefició mucho a esta estructura puesto que el fuerte de la implementación de los algoritmos radicaba en la búsqueda y eliminación de elementos, y debido a que LCadena  empleada un lista enlazada, la búsqueda siempre era de orden O(n) (tanto para localizar como para eliminar), lo cual decrementaba enormemente la eficiencia del código que se obtuvo inicialmente. Por esta razón se optó por emplear el árbol 2-3, esta estructura mantendría a la inserción, búsqueda y supresión en el orden de O(log n).

Otra Característica importante en la implementación que dio lugar a un cambio fue el uso de la clase CString soportada únicamente por el compilador Visual C++ 6.0. Esta clase fue usada únicamente por LCadena y fue sustituida en CSetOrdenado por una nueva clase CString que incorpora la funcionalidad de la anterior pero que permite exportarse a otros compiladores, además de incorporar “caracteres” de 2 bytes.

Ahora bien, a parte de las estructuras generalizadas que emplean todos Algoritmo de Retroceso también existen algunas estructuras particulares para cada uno de ellos, estas creadas para darles funcionalidad al momento de implementarse.

En el Algoritmo de Retroceso Cronológico no fue necesaria ninguna estructura adicional, este fue implementado mediante las estructuras ya mencionadas anteriormente.

El Algoritmo de Retroceso Cronológico incorporando GAC3 requiere de una estructura adicional para mantener una pila que almacene elementos inconsistentes en cada llamada a la función ForzarConsistencia(), esta estructura se llama CStack.

Por último, en la elaboración del Algoritmo de Retroceso Cronológico incorporando AC4, se requirió, además de la estructura pila (CStack) requerida para el Algoritmo de Retroceso Cronológico incorporando GAC3, una estructura supports y una counter las cuales fueron creadas mediante un arreglo dinámico de 2 dimensiones de estructuras CSetOrdenado y arreglo dinámico de 3 dimensiones de enteros sin signo, respectivamente.





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