Download Tecnicas
Transcript
TÉCNICAS PARA LA RESOLUCIÓN DE PROBLEMAS NP-COMPLETOS INTRODUCCIÓN La noción de la NP-completitud está basada en la teoría que identifica problemas que no tienen algoritmos polinomiales. Existen técnicas para solucionar problemas NP-completos que se comprometen a que la solución sea óptima, robusta, eficiente y completa, además de intentar resolver el problema de forma que el tiempo de ejecución resulte ser polinómico en promedio (no considerando esta situación para la "peor solución"). Las técnicas de resolución de estos problemas pueden agruparse en algoritmos o métodos heurísticos o aproximados. Los algoritmos exactos nos otorgan soluciones exactas al problema en cuestión, ahora bien, para aquellos problemas no resolubles en tiempo polinomial puede ser preferible perder exactitud en aras de obtener rápidamente soluciones razonables buenas. Se trata de conocer técnicas que permitan encontrar soluciones aceptables y en tiempo razonable para los problemas NP-completos. Entre estas técnicas vamos a considerar la siguientes: BACKTRACKING Y BRANCH & BOUND Tanto los algoritmos branch & bound como los algoritmos backtracking tratan de buscar solución en un espacio de soluciones. Para facilitar la búsqueda, dicho espacio se organiza de acuerdo con una estructura de árbol. Cada nodo del árbol define un estado del problema. La generación de todos los hijos de un nodo puede hacerse, por ejemplo, particularizando todos los valores que pueda tomar la variable X1, valores que estarán en un conjunto finito S1. El árbol de búsqueda debe ser tal que una exploración exhaustiva del mismo nos determine todas las soluciones del problema. Los algoritmos branch & bound y los algoritmos backtracking difieren en el orden en que se exploran los nodos del árbol para encontrar la solución del problema. Ambos métodos consideran funciones de acotación que permiten realizar una "poda" evitando la generación innecesaria de nodos. En los algoritmos backtracking la búsqueda en el árbol puede realizarse según "depth first search" mediante la que se avanza a un nodo terminal y posteriormente se hace una vuelta atrás. En los algoritmos Branch & bound se generan todos los nodos hijos de uno dado antes de tomar un nuevo padre. El nuevo padre es el primer nodo de una lista que puede tener estructura de cola (FIFO, breadth first search) o de pila (LIFO, D-Search). Las técnicas Branch & bound (ramificación y acotación) son técnicas para enumerar las posibles soluciones factibles de un problema. Como su propio nombre indica la utilización de estos métodos consiste en dos procedimientos fundamentales: ramificación y acotación. La ramificación es el proceso mediante el cual un problema se particiona en dos o mas subproblemas, reemplazando el problema original por un conjunto de nuevos problemas y el proceso de acotación, es el problema de calcular cotas inferiores de las soluciones para limitar la ramificación, calculando una cota inferior de la solución de cada subproblema generado en el proceso de ramificación. Así, si en una etapa intermedia se obtiene una solución completa para la función objetivo; y el proceso de ramificación nos ha proporcionado un subproblema para el que se conoce una cota inferior, entonces no es necesario considerarlo como subproblema para futuras ramificaciones ya que nos proporciona soluciones peores. BÚSQUEDA CON RETROCESO (BACKTRACKING) En los algoritmos backtracking la búsqueda en el árbol que recoge el espacio de soluciones del problema puede realizarse según "depth first search" mediante el avanza a un nodo terminal y posteriormente se hace una vuelta atrás hasta el primer nodo del que no se hayan generado todos los hijos, avanzando entonces por un hijo de dicho nodo. Describiremos esta técnica a través de un ejemplo. Ejemplo: Coloreado de un grafo con tres colores. Es un ejemplo de un problema que requiere encontrar valores óptimos para n parámetros, correspondiendo a tres colores. El número de soluciones potenciales es 3n, siendo estas todas las posibles formas de colorear n vértices con tres colores. Para generar todos los caminos de coloreo de vértices, podemos comenzar asignando un color arbitrario a uno de los vértices y continuar coloreando el resto teniendo en cuenta las restricciones por las aristas. Cuando coloreamos un vértice, tenemos en cuenta todos los colores posibles de acuerdo con las restricciones y los colores previos. Este proceso puede ser hecho por un algoritmo de tree traversal que es la esencia de las técnicas backtracking y branch & bound. La raíz del árbol corresponde al estado inicial del problema, cada rama corresponde a la decisión concerniente a cada parámetro. Se determinan los colores a utilizar. Inicialmente se eligen dos vértices adyacentes y se colorean. A partir de ahí se colorean con los diferentes colores validos, no importando el color que se elige. El color de los dos primeros vértices corresponde al estado inicial del problema, asociado a la raíz. Se va construyendo el árbol. Para cada nodo del árbol, se selecciona el próximo vértice a colorear y se añaden uno, dos o tres hijos de acuerdo con el número de colores que se puedan usar para ese vértice. Cada vez que se van colorando hay menos flexibilidad con el resto de los vértices. Si siguiendo este proceso se consigue tener coloreado todo el grafo, se acaba con éxito. Si por el contrario, se llega a un vértice del grafo que no se puede colorear, se aplica el retroceso sobre el árbol y, para un nodo se continua explorando los restantes hijos. Si se representa el grafo mediante una matriz de adyacencia, el algoritmo correspondiente se puede expresar mediante el siguiente procedimiento: Type Vertice-> 'A'..'Z' procedure Colorear3 (in grafo: Grafo, OUT coloreados: (Vértice)) var c: 1..3; (*posibles colores*) begin coloreados := (); if coloreados = v then <imprimir solución completa> else <elegir un vértice v aun no coloreado>; for <ningún vértice adyacente a v está coloreado con el color c> do <marcar v con el color c>; coloreados := coloreados U {v}; Colorear3 (grafo, coloreados); BIFURCACIÓN Y ACOTACIÓN (BRANCH & BOUND) Este método es una variante de las técnicas de retroceso para problemas donde se trata de encontrar un mínimo (o máximo) de un función objetivo. Para el ejemplo del coloreado del grafo, seria encontrar el número mínimo de colores requerido para colorear el grafo sin la restricción de tres colores. Esta técnica consiste en recorrer el árbol y si se alcanza una hoja que tiene solución con k colores y al seguir avanzando (mediante la aplicación de varios pasos de retroceso) se alcanza un nodo que requiere k+1 colores, se puede retroceder y no avanzar por esa rama pues ya tenemos una solución mejor. Así k sirve de cota inferior de retroceso. Este mismo proceso se repite en el resto de los nodos del árbol, evitando la exploración de gran parte de la estructura. Es importante tener un buen método de recorrido para encontrar soluciones aceptables rápidamente. ALGORITMOS DE APROXIMACIÓN Son algoritmos que a pesar de no proporcionan una solución óptima, nos garantizan una cota en el margen de imprecisión. Sea un problema de optimización consistente en un conjunto de instancias y un conjunto de soluciones. Cada instancia I es asociada a un conjunto F(I) o soluciones factibles, y cada solución s tiene un valor c(s). Se asume que todas la soluciones son siempre enteros positivos. Para cada I, opt(I) es el óptimo (mínimo o máximo), valor de s sobre todo s F(I). Un algoritmo A es un algoritmo de aproximación de si para cada I dada, A devuelve alguna solución factible s F(I). Se define A( I ) c(s) donde s es la solución devuelta por A con una entrada I. Una forma de medir lo bueno de la solución es por el ratio de este valor al valor óptimo. Definimos RA( I ) A( I ) OPT ( I ) RA( I ) OPT ( I ) A( I ) para problemas de minimización, y para problemas de maximización. El algoritmo de aproximación A tiene un ratio r si RA( I ) r para todas las instancias I. Se ilustrará el tratamiento de problemas NP-completos con los siguientes ejemplos: CUBRIMIENTO DE VÉRTICES Este problema trata de encontrar un conjunto con el número mínimo de vértices tal que toda arista sea incidente por lo menos a uno de los vértices. Se podrá resolver a través de otro "aproximado" como es el ajuste maximal del grafo. Consiste en calcular un subconjunto A de aristas de forma que dos aristas cualesquiera de ese subconjunto no tengan ningún vértice común y todas las aristas de A-A' compartan algún vértice con alguna arista de A'. El procedimiento consistirá en ir tomando aristas del grafo, de una en una en cualquier orden, e ir eliminando las incidentes al conjunto que se está construyendo hasta recubrir todo el grafo. Para poder aplicar el nuevo problema "aproximado", seria necesario demostrar que el conjunto de todos los vértices incidentes a las aristas de un ajuste maximal M para un grafo G es un recubrimiento con no más de dos veces el número de vértices del recubrimiento de tamaño mínimo. Esto es evidente, ya que por la definición de ajuste maximal, los vértices inciden a las aristas de M son un recubrimiento de G. También por la propia definición, ningún vértice perteneciente a M puede recubrir a más de una arista en M. En consecuencia, por lo menos la mitad de los vértices de M debe pertenecer a un recubrimiento. Como ejemplo, el grafo de la figura puede servir para mostrar gráficamente la relación entre el recubrimiento mínimo y el ajuste maximal de un grafo G. ONE DIMENSIONAL BIN PACKING El problema bin packing trata de empaquetar diferentes objetos con tamaño único usando el mínimo numero de bins posibles. Por ejemplo, nosotros queremos mover el contenido de una casa usando el mínimo numero de coches y colocando paquetes en el coche tan densamente como sea posible (o los mismos coches en poco tiempo). Este es un problema de tres dimensiones, pero nosotros utilizaremos una sola dimensión. Además por simplicidad el tamaño de los bins tendrá tamaño 1. El problema: Dado x1 , x2 , x3 .... xn un conjunto de números reales entre 0 y 1; dividiendo los números en pocos subconjuntos de forma que en cada conjunto haya al menos uno. Una heurística para este problema es poner x1 en el primer bin, y para cada i, poner xi en el primer lugar que tiene para ello, o comenzar un nuevo bin si no hay sitio en los bins usados. Este algoritmo es llamado "first fit". Este algoritmo no es demasiado malo. El algoritmo first fit requiere al menos 2 OPT bins, donde OPT es el mínimo número de bins. First fit no puede dejar dos bins a no ser que no esté medio lleno; por otro lado; el item en el segundo bin podría ser colocado en el primer bin. Sin embargo, el número de bins usados no es mas que la suma del tamaño de todos los items (redondeando).El teorema siguiente da por hecho que el número de bins en la mejor solución no puede ser menos que la suma de todo el tamaño (en cuyo caso todos los items son perfectamente empacados). El first fit puede ser mejorado con una simple modificación. El peor caso se produce cuando aparecen al principio todos los números pequeños entonces, en vez de colocar los números en los bins en el orden que aparecen, nosotros los ordenamos en orden decreciente, y entonces usamos first fit. Esta modificación del algoritmo es llamada decreasing first fit. El algoritmo decreasing first fit requiere al menos 11/9 OPT + 4 bins, donde OPT es el mínimo número de bins. Esta constante es también tigh. First fit y decreasing first fit son ambos heurísticas. Hay otros métodos que nos proporcionan mejores constantes. En muchos casos, el análisis es complicado. Las estrategias descritas son típicas de algoritmos heurísticos. EUCLIDEAN TRAVELING SALESMAN El problema traveling salesman (TSP), es un problema importante con muchas aplicaciones. Se discute aquí una variación del TSP con restricciones adicionales que el peso corresponde a distancias Euclídeas. El problema: Sea C1 , C2 , C3 , .... Cn un conjunto de puntos en el plano correspondientes a la localización de n ciudades; encontrar entre ellos la mínima distancia del ciclo Hamiltoniana (traveling salesman tour). El problema es todavía NP-duro, pero veremos las ayudas asumidas Euclídeas en designar un algoritmo de aproximación para el problema. Podemos simplificar este hecho asumiendo que las distancias forman un triángulo desigual, cuyos estados y la distancia entre dos puntos cualquiera es mas corta que cualquier ruta entre otros puntos. El algoritmo comienza calculando el mínimo coste de exploración del árbol (el coste equivale a la distancia), lo que es mas fácil. Para nosotros el coste de el árbol no es mas que la longitud de el mejor TSP tour. Esto es porque el TSP tour es un ciclo que contiene todos los vértices; por lo tanto, eliminando cualquier arista del TSP tour hace ello un árbol expandido, cuyo coste es al menos el mínimo coste de expansión del árbol. Una expansión del árbol no corresponde directamente a TSP tour. Necesitamos modificarlo. Primero, considerar el circuito que consiste en atravesar el árbol por medio de depth-first (comenzando desde cualquier ciudad), e incluye una arista en la dirección opuesta que permite la búsqueda con retroceso. (Este circuito corresponde, por ejemplo, a recorrer un “tree-shaped with exhibits” en ambos lados por la parte derecha). Cada arista será recorrida exactamente dos veces, así el coste de este circuito es dos veces el coste de el mínimo TSP tour. Podemos ahora convertir este circuito en un TSP tour tomando rutas directas en vez de siempre backtracking (ver figura 5.1). Esto es, en vez de backtracking usando la misma arista, nosotros vamos directamente al primer vértice nuevo. El asumir que las distancias son Euclídeas es importante, porque garantiza que la ruta directa entre dos ciudades cualquiera es siempre al menos tan buena como una ruta no directa. La longitud del resultado TSP tour no es por tanto todavía mas que dos veces la longitud de el mínimo TSP tour, aunque es normalmente menor que eso. COMPLEJIDAD El tiempo de ejecución de este algoritmo viene determinado por el tiempo de ejecución del algoritmo de expansión del árbol de costo mínimo, el cual, en el caso de grafos Euclídeos, es O(n log n). MEJORA El algoritmo visto puede ser mejorado de la siguiente forma. La parte mas inconsistente del algoritmo es la conversión del tree traversal a TSP tour. Otra forma de ver esta conversión es construir un circuito Euleriano en la parte superior del árbol, repitiendo cada arista dos veces. Obtendremos entonces el TSP tour tomando caminos cortos del circuitos Euleriano. Podemos convertir el árbol en un grafo Euleriano mas efectivo. Un grafo Euleriano debe incluir solo nodos de grado par. Considérense todos los nodos de grado impar en el árbol habría un número par de ellos (por otro lado. el total de la suma de todos los grados seria impar, lo cual es imposible, esa suma es exactamente dos veces el número de aristas). Si añadimos suficientes aristas al árbol para hacer el grado de todos las aristas sea par, entonces obtendremos un grafo Euleriano. El TSP tour consistirá de un circuito Euleriano (con algunos subcaminos) que nos gustaría minimizar la longitud de la adición de aristas. Abstraigamos el problema. a) b) Figura 5.1: (a) Árbol de expansión. (b) El TSP tour obtenido a partir del árbol comenzando en el punto central, y yendo primero a la derecha. Damos un árbol en el plano y queremos añadirle aristas, minimizando su longitud total, de forma que el grafo resultante es Euleriano. Debemos añadir al menos una arista cada vértices de grado impar. Trataremos de añadir exactamente uno. Supongamos que hay 2k vértices de grado impar. Si añadimos k aristas, cada una uniendo dos vértices de grado impar, entonces todos los vértices tendrían grado par. El problema será entonces un problema de matching. Queremos encontrar la longitud mínima que cubriera todos los vértices de grado impar. Encontrar el peso mínimo para el matching perfecto puede ser realizado con O(n3) para grafos generales. Hay un algoritmo reciente, dado por Vaidya [1988] que trabaja en casos especiales de distancias Euclídeas con un orden temporal dado por O(n2.5(log n)4). (En la práctica no está claro cuándo es mejor el uso de este algoritmo). El TSP tour resultante es obtenido del grafo Euleriano (el cual incluye la longitud mínima de expansión del árbol mas la longitud matching) cogiendo los caminos cortos. a) b) Figura 5.2: El camino Euclídeo mínimo y su correspondiente TSP tour. (a) El árbol de expansión mas el matching. (b) La ruta obtenida a partir del camino Euclídeo.