|
Título: Problema viajante de comercio (TSP) Publicado por: jca1 en 18 Febrero 2021, 18:03 pm Buenas tardes, estoy tratando de averiguar cual es la BIG O del algoritmo que resuelve mas rápidamente el problema del viajante de comercio de manera optima.
Es O(n!)? Gracias. Título: Re: Problema viajante de comercio (TSP) Publicado por: Serapis en 18 Febrero 2021, 18:53 pm El problema del viajante, petenece a la clase NP-Completo, luego la solución óptima conocida es la fuerza bruta, así que sí, es O(n!).
Hay heurísticas para mejorar el coste en tiempo aceptando a cambio una solución subóptima pero que se aproxima (mas o menos) a la solución óptima. Título: Re: Problema viajante de comercio (TSP) Publicado por: jca1 en 19 Febrero 2021, 17:15 pm Una consulta mas, resolverlo de con programacion dinamica sirve para algo? Porque entiendo que usando ese metodo tiene tiempo de O(n^2*2^n) y hace uso de mucha memoria. Se puede considerar que es mejor usando este metodo?
|