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.

[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.

[Serapis]

... 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?

No. Es un problema no resuelto.
No existe ningún algoritmo conocido al margen de la fuerza bruta que garantice la solución correcta.
Nota que el diseño de un algoritmo que lo resuelva debe resolver todos los casos (para ser tenido como tal), y no uno que solo resuelva casos demasiado simples (para estos casos siempre podrá crearse un algoritmo eficaz y aceptable en tiempo).

Se recurre a heurísticas (aproximación a la solución, pero sin poder saber realmente si es la solución real), como te comentaba al señalarte:

La eficacia en estos casos están basado en heurísticas y ahí es muy dependiente de los ejemplos usados.

[jca1]

Te agradezco la pronta respuesta.

Y con respecto al programa que hice resuelve cualquier caso de manera eficaz sin importar digamos las ciudades ni los costos de los trayectos. Lo que no se si es lo suficientemente eficiente.

Te doy un ejemplo: para 23 ciudades en una computadora con un CPU de 4 núcleos se resuelve en un par de minutos.

Con casos de menos ciudades, por ejemplo hasta 13 ciudades, lo compare con la fuerza bruta y me daba el mismo resultado. Ademas comprobé que la parte lógica funcionara correctamente para que siempre, como dije recién, me de el resultado mas óptimo.

[Serapis]

Bien...
Si crees haber creado un algoritmo que resuelva el problema, lo primero es asegurarte que es así.
Para ello genera muy diferentes ejemplos, calculas por fuerza bruta la solución y tiempo empleado y luego lo comparas con tu algoritmo (importa sobre todo que la solución sea correcta, pués el tiempo es de suponer que será más eficiente que la fuerza bruta, si esto último no fuere así, no solucionaría nada, obviamente).
Cuando lo anterior quede satisfecho, intenta ponerte en contacto con un centro que tenga un superordenador, pregúntales si tienen datos de algún problema del viajero cuya solución hayan calculado, pídeles los datos para algo como 1000, 100.000 y 10 millones (por ejemplo), cuando lo resuelvas con tu algoritmo, dales la solución para que la comparen con la que ellos obtuvieron, si no coincide, pide la solución donde no coincide (la comparación en primera instancia sería la medida total, fallando, conviene tener como solución la ruta seguida, de modo que tú mismo puedas comparar si la suma de ellos es errónea, aunque pudiera ser que el problema fuere debido a la precisión de los decimales (es habitual esta discrepancia cuando se usa un PC y se compara el resultado con los obtenidos en un superordenador cuya coma flotante es muy superior), es decir que quede claro si la discrepancia es debida a la cuestión de la precisión o a un error en tu algoritmo.

- Si la solución coincide perfectamente, plánteate primero registrar tu algoritmo (al menos la propiedad intelectual, que quede acreditada a tu nombre), luego según lo que quiesieres hacer debes operar, si quieres que quede libre, solicita ayuda técnica para publicar un paper a los que te ayudaron en el superordenador... y si quieres obtener beneficios, podrías ponerte en contacto con grandes empresas.
Es muy conveniente antes de esto, intentar optimizarlo, pues no faltará quien partiendo de tu algoritmo haga unos simples cambios (a veces obvios) y reclamar que hizo una mejora sustancial sobre tu algoritmo (en general suele pasar a la historia el autor del algortimo más óptimo, especialmente si los menos óptimos, son además muy engorrosos de implementar).
Al margen de ello, el instituto Clay ofrece una recompensa para los 'Problemas del Milenio', creo recordar que éste (no exactamente el problema, si no que su resolución demostraría que los problemas NP son equivalentes a los problemas P y que por tanto pueden ser resueltos en tiempo polinómico). Por supuesto ese 'paper' debieras crearlo antes, porque sería lo que al final entregarías para reclamar el premio. (prize.problems@claymath.org , admin@claymath.org Nota para Admins, no borrar emails, son públicos)

- Si la solución no coincide (y ya probaste que no fue debido a error en la precisión de decimales), intenta escrutar donde pudiera estar el problema y tratar de arreglarlo. Si lo consigues, considera el paso anterior.

Si la solución no coincide, y no consigues resolverlo, intenta al menos determinar hasta que tamaño tu algoritmo resulta válido, seguramente todavía tenga interés un algoritmo que resuelva eficientemente (la fuerza bruta es muy ineficiente), para un número medio de nodos (pongamos entre cientos y pocos miles, pues cosas como semáforos, paradas de buses, etc... andan en esos términos). Simplemente sería un 'algoritmo menor del agente viajero' y a buena fé podría dar pistas a otros para intentar partiendo del mismo una solución total.

Considera que aunque se diga 'fuerza bruta' a menudo es razonable no practicarla en su totalidad, si no que puede ser podada... por ejemplo mi intuición me dice que en la práctica si los nodos tienen una distribución uniforme, bastaría con considerar para cada nodo la raíz cuadrada de los nodos, luego estos se escogerían entre los x más cercanos al mismo.
Resulta obvio lo absurdo de considerar cualquier ruta cuyo tramo parcial consista en ir de un nodo al nodo más lejano a éste, lo cual se puede descartar para todos los nodos, igualmente podría decirse lo mismo para el penúiltimo más lejano, etc... no queda claro el punto donde esto deja de ser cierto (ya digo que mi intuición me señala que es la raíz cuadrada aprox. para una distribución más o menos uniforme, como regla general).

Eso sí... prueba también con nodos cuya posición sea elegida al azar dentro de un área dada, para garantizar que no hay cierto vicio en los mapas seleccionados.

Tengo por ahí un programa de grafos para resolver determinados problemas, creo que se podría ajustar perfectamente para hallar soluciones por fuerza bruta (en realidad cortocircuita una ruta cuando la suma de un nodo supera la longitud de un trayecto que previamente ha sido más corto). Quizás tuviera que reajustarlo, porque creo recordar que lo hice para operar con pesos de valor entero (no con decimales)... Además tampoco precisa recorrer todas las rutas, ya que A-B-C es equivalente a C-B-A, a lo sumo precisa explorar = (((n-1)*2)/2) rutas.
...para nodos de pocas decenas calcularía perfectamente la solución en un tiempo asumible, así que si precisas comparar tus resultados, basta que me pases un mapa (una tabla de los nodos con las distancias al resto de ellos). Así se podría comparar si efectivamente tu algoritmo genera la solución óptima.

[Serapis]

Aca te mando un tabla donde la primer columna es la distancia, en la segunda una de las ciudades y la tercera es la otra ciudad que une.

Ese sistema es muy laaaaaargo de definir y sobretodo de interpretar al programarlo, pues va a requerir rellenar huecos...

623939   1   2
1341230   1   3
1652150   1   4
354682   1   5
...

No es necesario que me lo mandes por privado, son simplemente datos, cifras, nada que requiera discrección, de hecho si se deja público puede que alguien más se anime a hacer un cálculo por su cuenta... o pruebe con su propia solución... y te dé 'su solución'.

Una tabla es sencilla de hacer.... te paso un dibujo de ejemplo, pero tú debes anotarlo en un fichero de texto, que luego yo pueda leer desde el programa para cargar los datos... meterlo manualmente tiene el riesgo de error en la introducción de datos, aparte de lo tedioso de la introducción manual que supone cuando los datos son varios.

Un ejemplo y te comento brevemente:

Cada número supone el nodo enésimo representado por el número en su fila o columna. Nota que los números de fila y columna en la imagen están solo por claridad, en el fichero es preferible omitirlos, su orden de ubicación lo representa y es suficiente, si no, exige filtrarlo.

Cada fila representa un nodo (ciudad por ejemplo), y a su derecha se señala la distancia que hay de él a cada uno de los nodo bajo cuya columna se ubica.
En la imagen se observa que solo he rellenado las distancias que parten del nodo 4 al resto de nodos: Al nodo 1 hay una distancia de 15, al nodo 2 una distancia de 22, al nodo 3 una distancia de 36, al nodo 4 (a sí mismo), una distancia de 0 (pero que he marcado como 'x', todos los nodos a sí mismo tienen igual valor representan la violación de pasar 2 veces por él mismo...), al nodo 5 hay una distancia de 81, al nodo 6 de 54... ...y finalmente al nodo 13 de 61.

Como ves cada nodo ocupa una fila, lo que se traduce en el fichero de texto como una línea de texto, al final de la misma un salto de línea (no te preocupes si tu sistema exige salto de línea y avance de carro, o solo uno de dichos caracteres (diferencias entre win2, mac y Linux) ya lo determino yo mismo al cargar el fichero al programa).
Separa la distancia entre nodos en el fichero con un simple espacio (no te preocupes si en alguno pusiste 2 o más espacios, se filtrarán)...

Al final guarda el fichero, verifica que esté correctamente editado, lo comprimes en zip (para evitar que sea manipulado), lo subes a una página de descarga y publicas el enlace.

Si el texto fuera muy pequeño (pongamos 10-20 nodos), y las líneas no muy largas puedes copiar el texto una vez completo el fichero y pegarlo directamente aquí en el foro entre etiquetas code...
Si las líneas son muy largas, incluso las etiquetas code pueden forzar saltos de línea, cuando una línea exceda x tamaño de longitud, aunque supongo que con etiquetas code el tamaño de línea será más generoso (que con eqtiquetas quote o que sin etiquetas).
...si se cortan automáticamente las líneas, falsea la interpretación de los datos a la hora de leerlos con un programa que entiende que los datos de un nodo están en una línea.
Si a pesar de todo las líneas fueran tan largas, que quedaren cortadas, entonces es preferible subir el fichero a alguna página de descargas y poner enlace y listo.

Con el ejemplo de la imagen, el fichero se vería así (nota que como solo he rellenado la fila 4, debe suponerse 3 filas por delante, y muchas más por detrás).

Código [Seleccionar] Expandir

...
15 22 36 x 81 54 21 7 13 103 84 52 20 61
...

[jca1]

Gracias por la explicacion, aca te envio de manera mas aceptable.

La solucion que encontre como optima fue de 7561324 como costo de trayecto, cual seria el siguiente: 1-12-2-19-7-9-20-14-6-18-4-10-16-3-17-8-13-11-5-15-1.

Código [Seleccionar] Expandir


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 X 623939 1341230 1652150 354682 1747483 1290310 1122942 1680743 1712687 453541 478852 743303 1795689 296984 1593894 1107880 1641036 992471 1710584
2 623939 X 1263724 1771242 793788 1660481 677790 805046 1161034 1886796 818413 256124 494772 1494657 875956 1723078 881419 1618177 370000 1329661
3 1341230 1263724 X 629682 1073545 411096 1344172 573846 1132166 800624 966022 1073778 769025 651920 1603652 608276 424381 358468 1395886 770064
4 1652150 1771242 629682 X 1311868 564358 1960841 1192057 1750457 182482 1203370 1540292 1295414 1145294 1850027 60827 1033924 390128 1970025 1341230
5 354682 793788 1073545 1311868 X 1464411 1380036 998599 1643441 1363121 111803 559016 667308 1607762 545893 1252557 935093 1338805 1149782 1572672
6 1747483 1660481 411096 564358 1464411 X 1650515 910000 1300000 741080 1354178 1481215 1168417 607289 2002823 584636 788479 187882 1756843 841189
7 1290310 677790 1344172 1960841 1380036 1650515 X 770778 628171 2116459 1365283 834865 784474 1249079 1553222 1928522 926984 1685140 360693 1001299
8 1122942 805046 573846 1192057 998599 910000 770778 X 692603 1352072 925904 702637 382753 698927 1418731 1162110 161245 920869 847584 587962
9 1680743 1161034 1132166 1750457 1643441 1300000 628171 692603 X 1927692 1587513 1204325 976933 756042 1972739 1736260 830240 1397891 952732 484148
10 1712687 1886796 800624 182482 1363121 741080 2116459 1352072 1927692 X 1259285 1647300 1424359 1327403 1887670 192353 1192015 571401 2106395 1523154
11 453541 818413 966022 1203370 111803 1354178 1365283 925904 1587513 1259285 X 570087 619838 1513472 657647 1144377 850000 1227232 1160560 1490301
12 478852 256124 1073778 1540292 559016 1481215 834865 702637 1204325 1647300 570087 X 329848 1400142 768439 1489765 735459 1418767 592030 1276244
13 743303 494772 769025 1295414 667308 1168417 784474 382753 976933 1424359 619838 329848 X 1074243 1040048 1250999 406078 1123610 685930 968297
14 1795689 1494657 651920 1145294 1607762 607289 1249079 698927 756042 1327403 1513472 1400142 1074243 X 2085689 1151086 687968 756637 1460855 272029
15 296984 875956 1603652 1850027 545893 2002823 1553222 1418731 1972739 1887670 657647 768439 1040048 2085689 X 1790000 1397855 1882976 1232233 2006614
16 1593894 1723078 608276 60827 1252557 584636 1928522 1162110 1736260 192353 1144377 1489765 1250999 1151086 1790000 X 1002646 403112 1928756 1337535
17 1107880 881419 424381 1033924 935093 788479 926984 161245 830240 1192015 850000 735459 406078 687968 1397855 1002646 X 778973 975089 640702
18 1641036 1618177 358468 390128 1338805 187882 1685140 920869 1397891 571401 1227232 1418767 1123610 756637 1882976 403112 778973 X 1753168 964624
19 992471 370000 1395886 1970025 1149782 1756843 360693 847584 952732 2106395 1160560 592030 685930 1460855 1232233 1928756 975089 1753168 X 1244869
20 1710584 1329661 770064 1341230 1572672 841189 1001299 587962 484148 1523154 1490301 1276244 968297 272029 2006614 1337535 640702 964624 1244869 X