Problema del viajante de comercio - Branch and Bound
jca1:
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.
Machacador:
No estará lo que buscas en GitHub???...
Saludos.
:rolleyes: :o :rolleyes:
jca1:
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.
Serapis:
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.
jca1:
Entiendo lo que me decis; pero dejando un poco de lado la eficiencia, no existe ningun programa que lo resuelva de manera eficaz, ademas de la fuerza bruta?
Es decir que tarde lo que tarde no hay programa que siempre encuentre la solucion mas optima?
Mi programa lo comprobe tanto de manera practica como logica (teorica). Es decir que siempre encuentra el valor mas optimo. De ahi a que sea lo suficientemente eficiente es otro tema.
Navegación
[#] Página Siguiente