Gráficos y RedesSalesman

Hasta ahora hemos ignorado el hecho de que algunas ciudades podrían estar más separadas que otras. Sin embargo, en la vida real, esta es una consideración muy importante: no solo queremos encontrar un camino, sino que queremos encontrar el más corto. Esto se llama el problema del vendedor ambulante . Tiene que resolverse no solo en el transporte y la logística, sino también al colocar transistores en microchips, para hacer computadoras más rápidas o al analizar la estructura del ADN .

Un método simple sería probar todos los caminos posibles, encontrar la longitud de cada uno y luego elegir el más corto. Sin embargo, acabamos de demostrar eso, incluso con solo ${tsn2} ciudades hay ${tsn2} ! = ${factorial(tsn2)} posibles caminos. Una vez que tenga cientos o miles de vértices, probar todos los caminos posibles se vuelve imposible, incluso utilizando computadoras potentes.