Download Tecnicas

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.