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



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

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.


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