Técnicas para la resolución de problemas np-completos



Descargar 75.4 Kb.
Página1/4
Fecha de conversión12.08.2020
Tamaño75.4 Kb.
  1   2   3   4

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



else

;

for do

;

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

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



para problemas de minimización, y



para problemas de maximización. El algoritmo de aproximación A tiene un ratio r si



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.




Compartir con tus amigos:
  1   2   3   4


La base de datos está protegida por derechos de autor ©odont.info 2019
enviar mensaje

    Página principal