 Autor
|
Tema: Problema viajante de comercio (TSP) (Leído 3,270 veces)
|
jca1
 Desconectado
Mensajes: 59
|
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.
|
|
|
|
|
En línea
|
|
|
|
|
Serapis
|
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.
|
|
|
|
|
En línea
|
|
|
|
jca1
Desconectado
Mensajes: 59
|
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?
|
|
|
|
|
En línea
|
|
|
|
|
| Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
|
Problema viajante de comercio dinamico
Java
|
josnick
|
0
|
3,174
|
31 Mayo 2014, 01:23 am
por josnick
|
|
|
|
Viajante comercio
Programación C/C++
|
Dato Vagabundo
|
6
|
9,901
|
16 Octubre 2022, 22:00 pm
por jca1
|
|
|
Problema del viajante de comercio - Branch and Bound
« 1 2 3 4 »
Programación General
|
jca1
|
30
|
27,111
|
24 Mayo 2022, 18:37 pm
por jca1
|
|
|
|
Metodos de resolver el problema del "viajante de comercio" mediante programación lineal
Programación General
|
jca1
|
1
|
4,753
|
8 Junio 2023, 23:52 pm
por Serapis
|
|
|
|
Variante del problema del viajante de comercio o TSP
Programación General
|
jca1
|
0
|
1,138
|
10 Agosto 2024, 12:54 pm
por jca1
|
 |
