Cuando hablamos de grafos ponderados, en el
que cada arista tiene asociado un valor positivo (peso), se sabe que el ciclo
hamiltoniano de menor costo es a su vez también la solución al Problema del
Vendedor Viajero que consiste en encontrar una ruta que, empezando y terminando
en la misma cuidad, recorra sólo una vez las ciudades restantes y que a la vez
esta ruta sea la mínima posible.
No se conocen algoritmos eficientes para la
resolución del problema en términos de tiempo, ni aunque el número de ciudades
sea muy pequeño. Las soluciones que han sido obtenidas son aproximaciones,
ofreciendo sólo soluciones aproximadas a la óptima llegando a porcentajes de
optimización del 97%.
EJEMPLO
El grafo de la figura es un grafo ponderado,
sus ponderaciones se encuentran sobre cada arista, las cuales se hallan en el
cuadro adjunto.
En este caso, por ejemplo se lee que la
arista que une los vértices A y B tiene una ponderación de 100.
Ahora, imaginemos que los vértices del grafo
anterior son ciudades y que sus aristas son posibles caminos entre cada ciudad,
la ponderación indicaría la distancia entre ciudades.
Las ponderaciones no solo representan
distancias, pueden ser valores monetarios, tiempos, entre otros.
0 comentarios:
Publicar un comentario