Algoritmos Vuelta Atras.

Índice

1. Describir la Metodología de resolución de problemas “Vuelta Atrás”.
1.1 Aplicación y alcance.
1.2 Elementos característicos.
1.3 Esbozo del coste computacional.

2. Problema para realizar la resolución "más barata computacionalmente" y el cual se lleva a cabo mediante esta metodología. Aplicarla.
2.1 Identificación de los elementos característicos.
2.2 Demostración/Justificación de porque el problema es resoluble por esta vía.
2.3 Resumen del código y análisis del coste computacional a partir del código reducido.

3.Bibliografía.

_____________________________________________________________


1. Describir la Metodología de resolución de problemas “Vuelta Atrás”.

Los algoritmos vuelta atrás (también conocidos como Backtraking), son una estrategia de programación que permiten encontrar soluciones a problemas que tienen unas determinadas
restricciones.

La forma de trabajar de este tipo de algoritmos, es muy semejante a la realización de un recorrido en profundidad dentro de un árbol de búsqueda. Así, para encontrar el conjunto de posibles soluciones, basta con recorrer el árbol construyendo soluciones parciales a medida que se avanza hacia la solución final.

Estas soluciones parciales, limitan las regiones en las que se puede encontrar una solución completa. De esta forma, si el recorrido tiene éxito, se puede continuar buscando otras soluciones o la mejor de todas ellas, y concluir con la más óptima.


1.1 Aplicación y alcance.

Este tipo de metodología es muy genérica, ya que trata de recorrer todas las posibles soluciones y encontrar la más apropiada para cada caso o las soluciones que satisfacen una condición, con lo que puede ser aplicada en la mayoría de problemas.

Por ello, esta técnica de resolución es usada en muchos ámbitos de la programación, por ejemplo, para el cálculo de expresiones regulares o para tareas de reconocimiento de texto y de sintaxis de lenguajes regulares. También es usado incluso en la implementación de algunos lenguajes de programación, tales como Planner o Prolog y da soporte a muchos algoritmos en inteligencia artificial.

A diferencia de los algoritmos voraces, en el caso de vuelta atrás, la elección de un sucesor en una etapa, no implica su elección definitiva, con lo que es probable que se vuelva a referenciar en un futuro.

Además, si son comparados con algoritmos de programación dinámica, se observa, que estos tratan de almacenar los resultados para no tener que recalcularlos, mientras que en vuelta atrás no podemos hacer esto, ya que el número de casos es muy elevado.

Si bien, aunque de forma general este tipo de algoritmos son muy ineficientes, es cierto que se pueden considerar otros métodos algorítmicos como voraces o programación dinámica, para realizar posibles optimizaciones de algoritmos vuelta atrás, ya que a veces estos son el único camino posible para resolver determinados problemas.

1.2 Elementos característicos

En general para poder aplicar vuelta atrás, la solución al problema debe poder expresarse como una Tupla (x1,x2, ...,xn) unidimensional, donde los xi representan elecciones de algún conjunto finito Ci. Es decir, cada componente xi se elige en cada etapa de entre un conjunto finito de valores y cada etapa es un nivel en el árbol de soluciones.

El funcionamiento del algoritmo, consiste en pasar por todos las posibles soluciones de forma metódica y ordenada, es decir, por todos los valores en cada elemento de la tupla. Para ello tenemos que determinar cuáles serán los valores posibles que podremos ir introduciendo en esta.

Además de esto tenemos que identificar los tipos de nodos con los que se va a trabajar:

- Nodo solución: El cual se establece cuando el recorrido del árbol tiene éxito (hoja del árbol).

- Nodo problema: Que es en el que hasta el momento encaja todo y se puede encontrar una solución.

- Nodo fracaso: Que es un nodo en el que el recorrido no tiene éxito, debido a que en alguna etapa, la solución construida no se puede completar.


1.3 Esbozo del coste computacional.

Este tipo de algoritmos no son eficientes, ya que se basan en el método de prueba y error, y en muchas ocasiones para conseguir solución se tiene que recorrer todo el árbol de búsqueda o gran parte de él.

Ahora bien hay que decir que la eficiencia depende de:

* El número de nodos del árbol de búsqueda que se visitan para conseguir la solución
→v(n).

* El trabajo realizado en cada nodo, esto es, el coste de la función de solución completa o ver si la solución es aceptable hasta el momento. Este coste lo podemos expresar como →p(n), ya que generalmente será polinómico.

* El coste en general será: O(p(n)v(n)), este coste será exponencial en el peor caso.

Para conseguir mejoras en los costes se suele recurrir marcar los caminos ya recorridos que no llegan a ninguna solución como nodo fracaso o camino fracaso.

También se podrían crear funciones acotadoras para que reduzcan mucho el número de nodos generados, si estas sólo dejara un nodo el algoritmo se convertiría en voraz y su coste bajaría a O(p(n)n).

Aunque normalmente los costes más bajos que se pueden conseguir son el orden de O(p(n)2n).

Se puede concluir que los algoritmos de vuelta atrás no son todo lo eficientes que deberían, y se deben utilizar para resolver parte de otros problemas o problemas reducidos. Aún así la gran ventaja que tienen es que si hay solución la encontrarán.

2. Problema para realizar la resolución "más barata computacionalmente" y el cual se lleva a cabo mediante esta metodología. Aplicarla.

Una compañía de transporte exprés, tiene n puntos de distribución, D1,...,Dn y trata de mejorar su servicio al cliente. Con lo que dado un punto de distribución origen “Do” y un punto de recogida destino “Dd”, un terminal debe ofrecer, al empleado, la información sobre el orden de puntos de distribución a los que debe enviar el paquete para que llegue desde “Do” a “Dd” y que se minimice el tiempo de trayecto total.

Por tanto se plantea implementar un algoritmo que realice esta tarea a partir de la tabla con
los tiempos de reparto entre puntos de distribución, suponiendo que no existen pérdidas de tiempo en procesos intermedios y que, no todos los puntos de envío y distribución están conectados entre sí por líneas directas, con lo que en muchos casos hay que enviar los paquetes a puntos intermedios, en los que se supone que el tiempo que tarda en realizar el nuevo envío a el destino tardan tiempo cero en efectuarse. Se plantea realizar la solución del problema usando un algoritmo de Vuelta Atrás.

2.1 Identificación de los elementos característicos.

Para resolver el problema mediante un algoritmo Vuelta Atrás, se usará una Tupla X[x1, x2,…, xn] de n elementos. Dicha tupla nos servirá para ir almacenando la solución, siendo n el número de puntos de distribución que disponemos. Con lo que la tupla estará llena hasta la posición k-ésima, siendo k el número de puntos de distribución que se tienen que recorrer para ir desde el origen al destino.

Además, con respecto a los valores posibles de cada tupla, xi representará el número de punto de distribución (coincidiendo con su índice en la tabla de horarios) que compone el trayecto más corto (de 0 a n).

Nodo problema: Aquel que hasta el momento es válido para encontrar una solución, ya que no hemos pasado por el todavía y está conectado con el anterior.

Nodo Solución: Nodo hoja que es nodo problema.

Nodo Fracaso: Nodo por el que aún no se ha pasado, o que no está conectado con el anterior. Además será nodo Fracaso aquel nodo padre, en el que se da la situación de que todos los nodos hijos le llevan al fracaso.

Se usará un array auxiliar (Tiempos[][]), donde almacenaremos el tiempo que se tarda en ir desde el punto de distribución i, hasta el j.

2.2 Demostración/Justificación de porque el problema es resoluble por esta vía.

Se hace un estudio a fondo del problema, vemos que no puede ser resuelto por Voraz, ya que
la elección de una solución intermedia, no implica que sea la solución final, ya que puede volver a ser referenciada en el futuro si esta no era la óptima o si no va a ninguna solución.

Por otro lado se observa que el problema también podría ser resuelto mediante programación dinámica, ya que se puede alcanzar la solución más óptima, almacenando cálculos intermedios y basándonos en casos básicos. Si bien, es cierto que cuando tratamos de resolver el problema con un número de puntos de distribución muy grande es muy complejo almacenar tantos posibles casos.

Con lo que podemos concluir que la forma más eficiente de resolver el problema es mediante un algoritmo vuelta atrás, donde se comenzará introduciendo la estación origen en la primera posición de la tupla. Para desde este punto, y con la ayuda de un árbol de búsqueda imaginario donde en cada etapa, se probarán las estaciones que pueden llevarnos a la solución final, podremos encontrar la solución más optima.

Para ello, estableceremos una restricción para no volver dos veces por el mismo punto de distribución, y que nos compruebe además, si es posible realizar el envío al punto de distribución al que estamos interrogando ((Función EsCorrecto(k)). Si no es así, marcaremos el nodo como nodo fracaso, de tal forma que si un padre, tiene sus nodos hijos como fracaso, este lo será también.

Con esto nos aseguramos que el algoritmo va a comprobar todas las posibles soluciones, de forma ordenada y metodológica, dando como resultado la opción más optima.


2.3 Resumen del código y análisis del coste computacional a partir del código reducido.

Resumiendo el código, obtenemos el siguiente resultado:

Entero n, Origen, Destino, mínimo = INT_MAX
Array Enteros Tiempos, SolucionOptima y X;

Programa principal{
Se introduce la estación origen y destino y se guardan en las variables oportunas. X[0] = Origen;

Se llama a la función PuntosDeDistribución( 1,0) que es donde se realiza el algoritmo vuelta atrás.

Se muestra la solución, si se ha encontrado.

Fin_Programa principal;

Funcion PuntosDeDistribucion( int k, int tiempoAcum ) X[k] = -1;

Hacer X[k] = X[k] + 1;

Si ( EsCorrecto(k) ) entonces
tiempoAcum = (tiempoAcum + Tiempos[X[k-1]][X[k]]);

SI ( tiempoAcum <= minimo )entonces    

Si ( X[k] == Destino ){
//Hemos llegado al destino          
SolucionOptima = X;      
minimo = tiempoAcum;       

Si_no  Si ( k < n ) {      
// Llamada recursiva. PuntosDeDistribucion( k+1, tiempoAcum);         
Fin_todos SI.  
Mientras  X[k] != n-1;   
Fin Funcion PuntosDeDistribucion.

Funcion  EsCorrecto ( int k )    
int t;    
para t = 0 mientras t != k-1 haz 
t++ // No hay estaciones repetidas.    
Si  X[t] == X[k] entonces
devuelve false;   
return false; Fin_para    
devuelve ( Tiempos[X[k-1]][X[k]] < INT_MAX );
Fin_esCorrecto.

Podemos concluir que el coste computacional vendrá determinado dependiendo del número de nodos (puntos de distribución) que se visitan en el árbol de búsqueda para lograr la solución, determinado por v(n) y del coste p(n) que tenga la función EsCorrecto(), que es la encargada de trabajar en cada uno de los nodos para determinar si son fracaso o no.

Observamos que v(n) tiene un coste de determinado por: T(n) = (NºNodos)n-1. Y que p(n) tiene un coste aproximado: T(n) = n.
Con lo que tenemos un coste total de T(n) = p(n) v(n) o lo que es lo mismo: T(n) = n * (Nº Nodos)^n-1.


3. Bibliografía.

- Apuntes de la asignatura Metodología de la Programación.

- http://es.wikipedia.org/wiki/Vuelta_Atrás.

- Universidad Complutense de Madrid, Facultad de Informática, http://www.fdi.ucm.es.

- Libro: Técnicas de Diseño de Algoritmos en Java, por Sonia Jaramillo Valbuena,Sonia
Jaramillo Valbuena, Sergio Augusto Cardona Torres, Maria Lili Villegas Ramirez.

- Universidad de Cataluña, Departamento de Lenguajes y sistemas informáticos, http://www.lsi.upc.es.

- Libro: “Análisis y diseño de Algoritmos”, Universidad de Málaga.