elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Top 20 herramientas Hacking más populares de 2020


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Problema viajante de comercio (TSP)
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Problema viajante de comercio (TSP)  (Leído 822 veces)
jca1

Desconectado Desconectado

Mensajes: 26


Ver Perfil
Problema viajante de comercio (TSP)
« 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.


En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 2.698


Ver Perfil
Re: Problema viajante de comercio (TSP)
« Respuesta #1 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.


En línea

jca1

Desconectado Desconectado

Mensajes: 26


Ver Perfil
Re: Problema viajante de comercio (TSP)
« Respuesta #2 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?
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
foro de comercio electronico
Sugerencias y dudas sobre el Foro
Buf0n 0 1,129 Último mensaje 25 Marzo 2007, 23:44 pm
por Buf0n
Problema del viajante
Programación C/C++
deifk 2 2,624 Último mensaje 8 Noviembre 2011, 16:31 pm
por deifk
Problema viajante de comercio dinamico
Java
josnick 0 2,123 Último mensaje 31 Mayo 2014, 01:23 am
por josnick
Viajante comercio
Programación C/C++
Dato Vagabundo 5 2,311 Último mensaje 13 Noviembre 2016, 18:30 pm
por alex64128
Problema del viajante de comercio - Branch and Bound
Programación General
jca1 3 785 Último mensaje 29 Abril 2021, 18:51 pm
por Serapis
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines