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

 

 


Tema destacado:


+  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 3,158 veces)
jca1

Desconectado Desconectado

Mensajes: 59


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: 3.391


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: 59


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
Problema viajante de comercio dinamico
Java
josnick 0 3,142 Último mensaje 31 Mayo 2014, 01:23 am
por josnick
Viajante comercio
Programación C/C++
Dato Vagabundo 6 9,729 Último mensaje 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 26,393 Último mensaje 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,536 Último mensaje 8 Junio 2023, 23:52 pm
por Serapis
Variante del problema del viajante de comercio o TSP
Programación General
jca1 0 755 Último mensaje 10 Agosto 2024, 12:54 pm
por jca1
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines