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

 

 


Tema destacado: Introducción a la Factorización De Semiprimos (RSA)


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

Desconectado Desconectado

Mensajes: 26


Ver Perfil
Problema del viajante de comercio - Branch and Bound
« en: 27 Abril 2021, 21:37 pm »

Buenas, hace un tiempo hice un programa para resolver el problema mencionado en el titulo.

Quisiera saber que tan eficaz es para lo cual necesito compararlo con el metodo de solucion Branch and Bound, por lo cual necesito por si alguno tiene, sabe o conoce un enlace donde este el codigo del metodo recien mencionado aplicado para este problema. Si esta escrito en C mejor, ya que es con el cual hice mi programa.

Gracias.


En línea

Machacador


Desconectado Desconectado

Mensajes: 4.286


Sexi-can... sin censura...


Ver Perfil WWW
Re: Problema del viajante de comercio - Branch and Bound
« Respuesta #1 en: 27 Abril 2021, 23:23 pm »

No estará lo que buscas en GitHub???...

Saludos.

 :rolleyes: :o :rolleyes:



En línea

"Solo tu perro puede admirarte mas de lo que tu te admiras a ti mismo"
jca1

Desconectado Desconectado

Mensajes: 26


Ver Perfil
Re: Problema del viajante de comercio - Branch and Bound
« Respuesta #2 en: 29 Abril 2021, 00:18 am »

Hola, buscando encontre un codigo en el siguiente enlace https://www.geeksforgeeks.org/traveling-salesman-problem-using-branch-and-bound-2/.

Es correcto el codigo ese?

Gracias.
En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 2.694


Ver Perfil
Re: Problema del viajante de comercio - Branch and Bound
« Respuesta #3 en: 29 Abril 2021, 18:51 pm »

Es muy difícil verificar "que tan eficaz es" tu algoritmo comparado con otro para un problema cuya resolución no existe salvo la fuerza bruta.

Si tu algoritmo también sigue el método de ramificación y poda, el rendimiento de tu algoritmo, va a depender casi exclusivamente de la profundidad de conocimiento en el lenguaje usado. En casos así elegir la estructura de datos adecuada, puede suponer una gran diferencia aun cuando otras partes del algoritmo, no sean igual de eficientes.

Considera la eficiacia (para este caso) como la mejor aproximación al resultado real y la eficiencia o rendimiento como el tiempo empleado. Ambos son igual de deseables...
La eficacia en estos casos están basado en heurísticas y ahí es muy dependiente de los ejemplos usados. Es perfectamente posible que un algoritmo arroje mejores resultados con ciertos ejemplos respecto de otro algoritmo y peores resultados con otros ejemplos.

Por otro lado el mayor limitante para verificar la eficacia es el tiempo preciso para encontrar resultados allí donde el tiempo es una premisa mayor... para acotaciones limitadas, siempre podrá modificarse un algoritmo para arrojar mejores resultados, más aproximados a la solución real.
Con la eficiencia, pasa lo mismo. Hay algoritmos que son muy rápidos para un cierto orden y a medida que aumenta el orden, disminuye su eficiencia y viceversa (por ejemplo la 'búsqueda por el método de burbuja' es más eficiente que quicksort, para (por ejemplo) 100 elementos, es comparativamente similar con 1000 elementos, pero es notablemente deficiente con 1.000.000 de elementos). Dado la explosión combinatoria del problema del agente viajero, la eficiacia y eficiencia de un algoritmo frente a otro exige pruebas exhaustivas, precisamente en diferentes órdenes de tamaño, y la que mayor determine la eficacia es prohibitiva en el tiempo, aunque si para pocas es menor y con cada aumento en la complejidad, sigue una curva de menor, parece que no vaya a cambiar la tendencia. Aún así es fácil demostrar esto para la eficiencia, pero no para la eficacia (exactitud en el resultado), ya que no hay forma de valorar una eficacia basada en los resultados que se arrojen.

Si tienes una soluciones (hipotéticas, pongamos) como en la siguiente tabla:

nº de prueba  items en juego   solucion real   tu solucion su solucion
-------------------------------------------------------------------------------
1                 5                   500          500          500     
2                 10                 1800         1800         1800
3                 20                 4723         4723         4723
4                 40                22000        22000        22000
5                 80               110000       109000       109600
6                 160              456000        44000       438000
7                 320             1380000      1350000      1360000
8                 640             9000000      8880000      8879000
9                 1280           25000000     24820000     24840000


Como ves, cuando la cantidad de items es poca, la solución puede ser real, o variar muy levemente, pero a medida que aumenten los valores, y sobretodo dependiente de cada ejemplo, un algoritmo podría arrojar una solución más cercana a la real en un problema concreto y más elejada en otro.. entonce no hay forma de valorarlo con precisión para decidir que uno es más eficaz que otro. Más bien en estos casos, lo que se valoran son las premisas requeridas, en resumen se adapta a las necesidades que la situación exija. Por ejemplo el factor tiempo puede dar más peso... así un sistema que solucione en pongamos 10 segundos aunque el valor real pudiera ser menos preciso, puede ser preferible a otro sistema que arroja una mejor precisión pero que demore 5 minutos en dar dicha solución.
En este problema la precisión (eficacia) y el tiempo (eificnecia) están en contraposición y debe valorarse un equilibrio entre ambos.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Problema del viajante
Programación C/C++
deifk 2 2,622 Último mensaje 8 Noviembre 2011, 16:31 pm
por deifk
Problema viajante de comercio dinamico
Java
josnick 0 2,121 Último mensaje 31 Mayo 2014, 01:23 am
por josnick
Viajante comercio
Programación C/C++
Dato Vagabundo 5 2,308 Último mensaje 13 Noviembre 2016, 18:30 pm
por alex64128
Problema al mover Bound Import Problema para copiar y pegar
Análisis y Diseño de Malware
kisk 2 1,679 Último mensaje 4 Abril 2017, 03:13 am
por kisk
Problema viajante de comercio (TSP)
Programación General
jca1 2 818 Último mensaje 19 Febrero 2021, 17:15 pm
por jca1
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines