Page 101 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

En la figura 4.3 se observa la ejecución del programa utilizando lo enseñado en la figura 4.1. Véase
que a los nodos que no eran conexos se les dio el valor de cero.

Figura 4.3. Ejecución del programa utilizando lo enseñado en la figura 4.1

el proBleMa del ageNte vIajero (tHe travelINg SaleS perSoN proBleM, tSp)

Un problema que se resuelve por medio del agente viajero es el siguiente: suponga que se tiene la
ruta de una camioneta postal que recoge el correo localizado en n sitios diferentes. Una gráfica de
n+1 vértices pueden ser usada para representar tal situación. El vértice origen representa la oficina
postal donde la camioneta inicia su recorrido y donde debe retornar. Toda arista <i, j> tiene asignado
un costo igual a la distancia desde el sitio i al sitio j. La ruta tomada por la camioneta postal es una
gira (visitar todos los sitios en forma no repetida) y lo que se espera es minimizar el trayecto. Un co-
mentario interesante es que el costo de la arista <i, j> es diferente al costo de la arista < j, i >.

Hablando matemáticamente, sea G = (V, E) una gráfica dirigida con costo de cada arista c , c se
ij ij
define tal que c > 0 para todo trayecto existente de i a j. Y c = ∞ si <i, j> E. Sea |V| = n y asuma que
ij i j
n > 1. Una gira de G es un ciclo dirigido que incluye todos los vértices en V. El costo de la gira es la
suma de los costos de las aristas en la gira. El problema del agente viajero es encontrar una gira que
minimice los costos.

95