El problema del vendedor ambulante
El problema del viajante es un gran problema en la teoría de grafos. ¿Por qué? Porque tiene aplicaciones en el mundo real. Los verdaderos vendedores de viajes que trabajan para empresas se enfrentan a este problema todos los días. El problema radica en encontrar la ruta más barata que visite todos los lugares deseados una sola vez. Idealmente, terminas donde comenzaste.
Recuerde que, en teoría de grafos , no nos ocupamos de nuestros gráficos circulares tradicionales y demás; en cambio, tratamos con lo que parece un juego de conectar los puntos donde las líneas son bordes y los puntos se llaman vértices. En teoría de grafos, esto es lo mismo que encontrar el mejor circuito de Hamilton en una gráfica ponderada donde cada borde de la gráfica tiene un costo. En el mundo real, es la distancia o el costo de recorrer un camino determinado. Cuanto mayor sea la distancia, mayor será el costo de la gasolina u otros gastos de viaje.
Por ejemplo, si comienza en Los Ángeles y sus opciones de otras ciudades son San Diego y San Francisco, sería más barato viajar a San Diego porque está mucho más cerca de Los Ángeles. La distancia es mucho menor. Si solo tiene tres ciudades de las que preocuparse, como en este ejemplo rápido, entonces sería una tarea fácil encontrar una ruta de viaje ideal más barata. Pero, ¿y si tuviera una lista más larga de ciudades para visitar? Entonces, ¿cómo podrías encontrar tu mejor ruta? Esta lección en video trata esta pregunta exacta. Veamos qué opciones tenemos.
Método de fuerza bruta
La primera opción se llama método de fuerza bruta . Con este método, enumeramos sistemáticamente cada circuito de Hamilton y luego calculamos cada uno para ver cuál es el mejor circuito. Con este método estamos seguros de encontrar la mejor ruta porque habremos calculado el costo de todos y cada uno de los circuitos. Pero el inconveniente de este método es la ineficacia. Piensa sobre esto. Si tenemos una lista de solo diez ciudades, ¡el número de circuitos de Hamilton que necesitamos calcular es (10 – 1)! = 9! = 362.880 . ¡Son muchos circuitos! Piense en el tiempo necesario para calcular cada uno. Podemos decir que este método de fuerza bruta no es eficiente, pero es óptimo.
Método del vecino más cercano
La siguiente opción que tenemos disponible se llama vecino más cercanométodo. En este método, elegimos la siguiente ubicación más cercana en función de dónde nos encontramos actualmente. Seguimos hasta que hayamos visitado todas las ciudades. Por ejemplo, supongamos que nuestra lista de ciudades incluye Los Ángeles, San Diego, San Francisco, Eureka, Tucson y Phoenix. Si comenzamos en Phoenix, nuestra siguiente ciudad más cercana es Tucson. Desde Tucson, nuestra siguiente ciudad más cercana es San Diego. Seguimos trabajando así hasta que hayamos visitado todas las ciudades. Ahora bien, este método puede funcionar para producir una gran ruta si elegimos un buen punto de partida. Pero si elegimos un punto de partida no tan bueno, como San Diego, terminaremos con una ruta más cara. Mira, comenzando en San Diego, iríamos a Los Ángeles, luego a San Francisco. Pero, ¿qué pasa con Tucson y Phoenix? Terminarían siendo visitados en último lugar.
 |
¿Ves cómo esta ruta no es una ruta óptima debido a la distancia extra necesaria para dar marcha atrás a estas dos ciudades? Sin embargo, el método del vecino más cercano es un método eficiente porque podemos encontrar una ruta en el primer intento.
Método de vecino más cercano repetido
Podríamos expandir nuestro método de vecino más cercano al método de vecino más cercano repetido . En este enfoque, elegimos varias ciudades como nuestros puntos de partida y luego elegimos una ruta basada en el método del vecino más cercano. Por ejemplo, podríamos tener ciudades iniciales de San Diego, Tucson y Eureka. Luego vemos qué ciudad de partida nos da la mejor ruta siguiendo el método del vecino más cercano de cada ciudad de partida. Sí, este método proporciona una ruta más óptima que el método del vecino más cercano, pero aún no es tan óptimo como nos gustaría. ¿Por qué? Bueno, si volviéramos a elegir las ciudades equivocadas, todavía terminaríamos con rutas que no son óptimas. Entonces, este método nuevamente no es óptimo. Pero es eficiente porque solo tenemos que calcular algunas rutas.
Método de enlace más económico
Nuestra siguiente opción es el método de enlace más económico . En este método, buscamos sistemáticamente los bordes más baratos, comenzando por los más baratos y avanzando hasta los más caros. Comenzamos por encontrar la ventaja más barata. Conectamos las dos ciudades que conecta. Luego buscamos el borde que sea el siguiente más barato. Este borde no tiene que conectarse con las dos primeras ciudades que conectamos. Pero si se conectará a una ciudad que ya se ha conectado a otras dos ciudades, saltamos este borde y continuamos con la siguiente más barata. Terminamos cuando todas nuestras ciudades estén conectadas.
Por ejemplo, para nuestras ciudades Los Ángeles, San Diego, San Francisco, Eureka, Tucson y Phoenix, la ventaja más barata está entre Tucson y Phoenix. Conectamos estas dos ciudades primero. Entonces, nuestra próxima ventaja más barata es entre San Diego y Los Ángeles, por lo que conectamos estas dos ciudades. Continuamos de esta manera hasta que todas nuestras ciudades estén conectadas entre sí. Este método es eficaz porque hacemos una sola pasada por todas nuestras ciudades, pero no es óptimo. No es óptimo porque a veces terminamos tomando una ruta más larga para llegar a algunas ciudades de lo necesario.
Por lo tanto, parece que ninguna de nuestras opciones es óptima y eficiente. El único método óptimo es el método de fuerza bruta , pero no es eficiente. Todos los demás métodos son eficientes pero no óptimos. Si queremos eficiencia, tendremos que sacrificar la optimización. Si queremos optimización, debemos sacrificar la eficiencia.
Resumen de la lección
¿Qué hemos aprendido? Aprendimos que el problema del viajante es un gran problema en la teoría de grafos. ¿Por qué? Porque tiene aplicaciones en el mundo real. Los verdaderos vendedores ambulantes que trabajan para empresas se enfrentan a este problema todos los días. El problema radica en encontrar la ruta más barata que visite todos los lugares deseados una sola vez. Idealmente, terminas donde comenzaste. En teoría de grafos, esto es lo mismo que encontrar el mejor circuito de Hamilton en un gráfico ponderado.
Tenemos varias opciones abiertas para usar para encontrar la mejor ruta. Tenemos el método de fuerza bruta en el que enumeramos sistemáticamente cada circuito de Hamilton y luego calculamos cada uno para ver cuál es el mejor circuito. También tenemos el método del vecino más cercano donde elegimos la siguiente ubicación más cercana en función de dónde nos encontramos actualmente. Luego tenemos el método repetido del vecino más cercano donde elegimos varias ciudades como nuestros puntos de partida y luego elegimos una ruta basada en el método del vecino más cercano. Por último, tenemos el método de enlace más barato en el que sistemáticamente encontramos los bordes más baratos, comenzando por el más barato y avanzando hacia el más caro.
Ninguno de los métodos es a la vez eficaz y óptimo. El método de fuerza bruta es óptimo, pero no eficiente. El método del vecino más cercano , el método del vecino más cercano repetido y el método de enlace más económico son todos eficientes pero no óptimos.
Los resultados del aprendizaje
Debería tener la capacidad de hacer lo siguiente después de ver esta lección en video:
- Explicar el problema del viajante en términos de teoría de grafos.
- Describe las opciones para encontrar la mejor ruta.
- Resuma la eficiencia de cada método y si es óptimo
Continua con:
- Síntesis de Alcoholes: Métodos y Técnicas
- ¿Cuáles son los principales métodos utilizados en la minería a cielo abierto?
- Pruebas de fluidos corporales: tipos, métodos y análisis
- ¿Qué es la prueba textil? – Métodos e Importancia
- Funciones de biyección, sobreyección e inyección: Diferencias, métodos y descripción general
- Métodos, usos y ejemplos de algoritmos
Explora más sobre este tema
Selecciona un tema y sigue aprendiendo...
