Foro de elhacker.net

Programación => Programación General => Mensaje iniciado por: jca1 en 27 Abril 2021, 21:37 pm



Título: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 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.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Machacador en 27 Abril 2021, 23:23 pm
No estará lo que buscas en GitHub???...

Saludos.

 :rolleyes: :o :rolleyes:



Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 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/ (https://www.geeksforgeeks.org/traveling-salesman-problem-using-branch-and-bound-2/).

Es correcto el codigo ese?

Gracias.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis 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.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 en 7 Agosto 2021, 05:56 am
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.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 7 Agosto 2021, 15:54 pm
... 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.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 en 7 Agosto 2021, 22:23 pm
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.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 8 Agosto 2021, 17:23 pm
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.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 9 Agosto 2021, 16:04 pm
Citar
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...

Citar
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:
(https://i.imgur.com/GtWNyp8.png)
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:
...
15 22 36 x 81 54 21 7 13 103 84 52 20 61
...


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 en 9 Agosto 2021, 16:57 pm
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:
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


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 11 Agosto 2021, 16:33 pm
Hola.

Hice algunos cambios para adaptarlo y lo puse anoche antes de irme a dormir a calcular, sigue calculando...

Nota que el programa está diseñado para mostrar cada solución que supera el límite previo... de ahí la lista de soluciones, cada línea siguiente supera la anterior acortando la distancia.

Sin embargo al venir a poner este mensaje me doy cuenta que tu diseño es 'circular', es decir, exige que tras visitar todas las 'ciudades' vuelva al origen.
En este programa adaptado mínimamente, no está considerado dicha opción... en realidad aún siendo el mismo problema son casos distintos y es conveniente tener (en tu algoritmo), un parámetro para indicar el caso y por tanto poder solucionar ambos.
Ya sacó las soluciones (omito las previas), dando como origen el nodo 1. Introduje los datos para considerar la ruta más corta sin consierar cual es la ciudad de origen (aunque lógicamente empieza en la 1 (A) y sin considerar regreso al nodo de origen.

Aunque veas que las soluciones que presento, ofrecen una distancia menor, considera el caso donde no se exige volver al origen (pero sigue visitando todas las ciudades), tiene por lo general (sobretodo si los datos son al azar), una solución más corta y no solo por eliminar el trayecto entre la última ciudad visitada y la ciudad de origen. Ya que al exigir la vuelta, ciertos nodos en su camino son evitados para poder 'volver'... por tanto no consideres aún fallida tu solución.

Mira de ver si puedes crear otro algoritmo equivalente donde no precise volver al origen (desde tu implementación (asumo que) esto debería serte relativamente sencillo, además es algo que sí o sí debes tener igualmente resuelto).
Desde mi programa no es más complejo si me hubiera percatado de ello al inicio... pues tira de grafos y el diseño está orientado a consideraciones generales aunque luego pueda especificar ciertos detalles... que deben darse como parametro en la entrada de datos.



Nota que el número asignado a cada nodo (1-20) ha sido remplazado por una etiqueta en el rango (A-T), pues de ese modo es más cómodo representarlo al ocupar cada uno un solo carácter (dígito) y también es más fácil de una simple ojeada distinguir letras de números (de los pesos)...


01-02-03-04-05-06-07-08-09-10-11-12-13-14-15-16-17-18-19-20
 A- B- C- D- E- F- G- H- I- J- K- L- M- N- O- P- Q- R- S- T


Si damos por hecho que se exige que la ciudad inicial sea la 1 (A), entonces los datos siguientes ofrencen la solución final. En realidad los datos de entrada están expuestos de tal manera, para continuar hasta que la última ciudad (nodo 20 (T)), fuere la ciudad de origen.
Soluciones (cada entrada (temporalmente la solución) supera la previa, se omiten las primeras (habría unas 50-100 soluciones temporales previas desde ABCDE...T con una distancia inicial de unos 22 millones):
...
1 ---> ABLHQCPJDRFNTIGSMKEO   8045241
1 ---> ABLKEOMHQCPJDRFNTIGS   8029724
1 ---> ABLMHQCDJPRFNTIGSKEO   7944387
1 ---> ABLMHQCPJDRFNTIGSKEO   7909997
1 ---> ABLOEKMHQCDJPRFNTIGS   7842256
1 ---> ABLOEKMHQCPJDRFNTIGS   7807866
1 ---> ABLSGITNFDJPRCQHMKEO   7771109
1 ---> ABLSGITNFRDJPCQHMKEO   7631457
1 ---> ABSGITNFDJPRCQHMLKEO   7573052
1 ---> ABSGITNFRDJPCQHMLEKO   7534083
1 ---> ABSGITNFRDJPCQHMLKEO   7433400
1 ---> AEKMHQCDJPRFNTIGSBLO   7397106
1 ---> AEKMHQCPJDRFNTIGSBLO   7362716
1 ---> AEKOLMBSGITNHQCFRDPJ   7359071
1 ---> AKEOLMBSGITNHQCFRDPJ   7346176
1 ---> ALBSGITNFRDJPCQHMKEO   7264340 <--- esta solución es la MISMA que la tuya (sin vuelta al origen):
1 ---> AOEKBLMHQCPJDRFNTIGS   7240895
1 ---> AOEKCHQMLBSGITNFRDPJ   7201363
1 ---> AOEKCQHMLBSGITNFRDJP   7150228
1 ---> AOEKCQHMLBSGITNFRDPJ   7028573
1 ---> AOEKLMBSGITNHQCFRDPJ   6991267
1 ---> AOEKMLBSGINTHQCFRDPJ   6963299
1 ---> AOEKMLBSGITNHQCFRDJP   6924025
1 ---> AOEKMLBSGITNHQCFRDPJ   6802370  <---- solución final: La ruta más corta partiendo del nodo 1, sin regreso al origen y sin especificar tampoco el nodo destino.




1 ---> ALBSGITNFRDJPCQHMKEO   7264340 <--- esta solución es la MISMA que la tuya (sin vuelta al origen): 1-12-2-19-7-9-20-14-6-18-4-10-16-3-17-8-13-11-5-15
Si a tu solución le quitamos la distancia entre las ciudades 15-1 (que es el caso que yo calculo), debería resulta lo mismo que lo que aquí aparece: 7561324 - 296984 = 7264340

Considera además que en una solución circular (como la que presentas), puedes cortar por el par de ciudades cuya distancia es mayor, al caso en tu solución circular esto sucede en los los nodos 7-9 y cuya distancia es 628171, y por tanto incluso así tendrías una solución más óptima con distancia de: 7561324 - 628171 = 6933153 ...pero como digo, sin considerar el regreso al origen hay soluciones más óptimas aún (salvo (generalmente) casos simétricos y otros que se diseñhacen al efecto), que considerando el caso circular y retirar la distancia entre los nodos que determinen el origen y el final.
Si necesitas alguna demostración que lo aclare, avisas y en cuanto saque un tiempo te hago algún boceto sencillo que lo refleje y demuestre...



También nota que el algoritmo aún no ha terminado. Terminaría cuando el nodo 20 (T), fuera la ciudad de origen...
Empezando por el nodo 4 (D), aún se localizan soluciones más cortas que empezando por A.
1 ---> DJPRFCQHMKEOALBSGITN   6769839
1 ---> DJPRFCQHNTIGSBLMKEAO   6745798
...dejarlo corriendo hasta Z llevaría muchas horas más, aunque como cada vez la solución temporal es más corta, se cortocircuita antes (cuando la suma parcial de nodos visitados superan ya esa distancia temporal), por lo que a medida que se encuentran soluciones corre más deprisa y necesita visitar menos nodos... el programa cuando lo pare (o a petición), muestra la cantidad de nodos recorridos (no cuenta los no visitados si los cortocircuita).
Lo dejaré funcionando unas horas más a ver que sale...



Por último, te recomiendo que hagas también las siguientes variaciones a tu algoritmo (pongo las más genéricas que podrían pedirte):
Y exponlas como parámetro, así una función general pública recibe los parámetros de entrada y una vez claro que se quiere hacer llama a una de las siguientes funciones privadas:
* Dado un nodo de origen, visitar todos los nodos y vuelta al origen      <---- esto es lo que tienes hecho.
- Dado un nodo de origen, visitar todos los nodos, pero sin requerir vuelta al origen.  <----- esta es la solución que yo te he presentado.
- Dado un nodo de origen y otro de destino visitar todos los nodos intermedios. <--- esta opción suele arrojar presumiblemente (obvio), una solución con mayor distancia que la previa, pero a menudo el origen y el destino están prefijados, luego debe considerarse).
- Hallar la distancia menor sin considerar un nodo de origen ni de destino <---- Esto es lo que está haciendo mi programa (mientras no lo pare). Esto suele requerirse cuando una operación ha de repetirse millones de veces, y entonces poder elegir la ruta más corta es lo óptimo cuando el acceso a un nodo de origen y de destino es indiferente... (suele ser el caso por ejemplo de muchas máquinas CNC, para dibujado, corte, soldadura, fabricación de microchips, etc...).


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 en 12 Agosto 2021, 21:55 pm
Hola es bastante interesante tu programa y el resultado que arroja.

El mio aplica al problema del viajante que incluye volver donde empezó y también incluye la necesidad o no de que sea completo el sistema; es decir que no haya conexiones entre ciudades que existan. Por ejemplo en un sistema de 10, llamemosle, ciudades, si todas se conectan entre si van a haber 45 trayectos; pero en mi programa no es necesario ese requisito.



Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 12 Agosto 2021, 23:01 pm
Al final lo dejé corriendo hasta el final...

Cuando me fuí a dormir llevaba calculando alrededor de 24 horas y cuando me levanté (unas 6 horas después ya había terminado), con lo que ha tardado entre 24 y 30 horas (1 sólo núcleo 1'5Gh. el programa está en vb6, programado en NET sería bastante más rápido), pero vamos la idea de este programa no es la velocidad, si no la versatilidad de soluciones que puedo aplicarle y que cada cierto tiempo suelo ampliar.

El número de nodos visitados ha sido: 954.207.241.839 (casi 1 billón). En realidad aunque sea un número muy grande es mucho menor que todas las posibilidades que para 20 nodos (1*2*3*4*5*6*7*8*9... *19*20=  2.432.902.008.176.640.000 2'43Trillones ) .

Hay que añadir que usando fuerza bruta, todavía es posible evitar recorrer ciertos nodos por cortocircuito... para ello basta reordenar los pesos de mayor a menor... así cuanto antes una suma alcance y supere el valor menor actual, antes cortocircuita todas las derivaciones tras ese nodo. Es suficiente por tanto (para mi programa) con preparar los datos de entrada sin tocar nada del código... la desventaja en este caso es que las soluciones aparecerían 'desordenadas', aunque para lo que se pretende carece de importancia.

He aquí el resto de soluciones hasta el final...
1 ---> JDPFRCQHNTIGSBLMKEAO   6743168
1 ---> JDPRFCQHMKEAOLBSGITN   6736689
1 ---> JDPRFCQHMKEOALBSGITN   6638313
1 ---> JDPRFCQHNTIGSBLMKEAO   6614272
1 ---> JPDRFCQHNTIGSBLMKEAO   6611159 <--- Solución final mínima
1 ---> OAEKMLBSGITNHQCFRDPJ   6611159 <--- Solución final mínima
(estas dos últimas son iguales, porque el requisito era '< ó =' (interesa tener soluciones que sean iguales especialmente cuando sean la solución definitiva, si bien como se ve es el recorrido inverso... los recorridos inversos de las solucuones previas no aparecen porque antes de su tratamiento se alcanzó una solución menor).

- Revisando las soluciones se puede ver ciertas 'aglomeraciones' 'KEAO', 'GITN', 'LMBSG', etc... que van apareciendo contínuamente en cada solución con ligeras diferencias de orden. Lo que sugiere 'barriadas' de ciudades...
- Otra curiosidad es que todas las soluciones acaban (o empiezan si se considera las soluciones del revés), en unos pocos nodos específicos: O, S, J y N.

...también incluye la necesidad o no de que sea completo el sistema; es decir que no haya conexiones entre ciudades que existan.
Sí, mi programa al operar con grafos, puedes evitar tmbiñén eso, sin tocar el código, si no solamente los datos de entrada. De hecho, 'codificar' correctamente los datos de entrada con los parámetros debidos es parte del problema, que uno debe saber resolver.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 en 12 Agosto 2021, 23:39 pm
Si consideramos nodos a un ciruito completo (en mi caso  circuito cerrado), es decir cuando es una posible solucion siendo si es mayor o menor al costo encontrado hasta el momento, mi programa lo resuelve ese problema en 155 segundos aprox. analizando 12984 nodos, sobre un totoal de 19!/2, ya contempla la no repeticion de circuitos. es decir con la misma solucion podes empezar por cualquier ciudad.

Para las soluciones "mejores" q la mia y tu solucion optima, si le agregamos el trayecto para que sea circular, como resuelve mi programa, los resultados serian los siguientes:
8233366
8914050
8744122
8741260
8703954
8675986
8517919
8515057
8595825

Fijate que es mucho mayor que mi solucion, o sea que teniendo en cuenta un trayecto que no termine en el origen optimo (tu programa), y le sumamos el trayecto para que vuelva al origen supera por mucho a mi solucion, dejando la posibilidad a que si sea la mas optima mi solucion al problema planteado.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 13 Agosto 2021, 17:31 pm
Si consideramos nodos a un ciruito completo (en mi caso  circuito cerrado), es decir cuando es una posible solucion siendo si es mayor o menor al costo encontrado hasta el momento, mi programa lo resuelve ese problema en 155 segundos aprox. analizando 12984 nodos, sobre un totoal de 19!/2,
Sí. Por eso me pareció importante darte una cifra aunque sea aproximada del tiempo  empleado incluso aún siendo efectivo en no usar una 'fuerza bruta a ciegas' (que revisa todos los nodos sin ninguna optimización), Considera que a medida que aumente el número de nodos, el tiempo crece exponencialmente, de ahí el interés incluso por algoritmos heurísticos que aún no facilitando la solución óptima sea una aproximada, ya que el tiempo en tales casos se convierte en un requisito...

Para las soluciones "mejores" q la mia y tu solucion optima, si le agregamos el trayecto para que sea circular, como resuelve mi programa, los resultados serian los siguientes:
8233366
8914050
8744122
8741260
8703954
8675986
8517919
8515057
8595825

Fijate que es mucho mayor que mi solucion, o sea que teniendo en cuenta un trayecto que no termine en el origen optimo (tu programa), y le sumamos el trayecto para que vuelva al origen supera por mucho a mi solucion, dejando la posibilidad a que si sea la mas optima mi solucion al problema planteado.
Sí y no...

Como ya te dije son dos problemas distintos, sus soluciones difieren (peneralmente) de modo considreable. Lo que difiere no es tanto el algoritmo, como la solución hallada. Me he tropezado con profesionales que interpretaron (y no solo por la mera conveniencia de la aproximación, como es el caso presente) que eran el mismo problema y que bastaba con romper o unir por el punto deseado ...tuve que demostrarles su error, pues insiitían en ello empecinadamente.
Es decir vale para decir 'la solución puede parecerse mucho a esto', dentro de cierta tolerancia, pero no para tomarla como solución.

Dado que ya me percarté de tu solución circular cuando llevaba varias horas en marcha, no quería retrasarlo más parando y volviendo a componer los datos. A ver si saco el fin de semana algo de tiempo libre y abordo el problema desde el caso circular comenzando desde el nodo A.

En realidad no es más complejo, para que mi programa lo trate circular, pues basta con añadir un nuevo nodo reetiqeutado como otro distinto pero con los mismos pesos que el nodo inicial y  añadirlo al final de todos, y exigirle que este sea además el último en la secuencia (como también lo es el primero), lo que consigue que sea circular... Aunque en tal caso, debe hacerse lo mismo para tratar cada nodo como el inicial (debe marcarse igulmente como el final), lo que fuerza a tratar los datos específicamente a cada caso... se puede automatizar por supuesto, pero dado que  solo son 20, se puede hacer manualmente, por otro lado dado que tu lo tienes empezando por el primer nodo (A), considerar de momento solo ese caso, resultará interesante. Es más que probable que tu solución sea la óptima, si no lo fuera, podrías revisar algún simple error, sino contuviere errores en el código pero no sacare la solución óptima, sería una heurística más, uy en ese caso habría que ver de entrar en competencia con las heurísticas actuales (nota que muchos lo mantienen en secreto, pensando que la solución final debe estar compuesto con parte de algoritmo que han creado y que solo les falta algún detalle que esperan encontrar en algún momento).

Nota que el hecho de sumar un tramo más, no solo incrementa el valor de ese tramo, sino que por lo general la solución suele ser menos óptima, ya que por 'fuerza' el último nodo que vuelve al origen está tan cerca del origen como los más próximos a él... En el caso que has presentado sumando (forzando la circulación uniendo el nodo final al inicial), no puede ser óptima, porque ese nodo final no garantiza que sea uno de los más próximos al inicial... para la solución más óptima de los casos no circulares, esto será (salvo casualidades y casos de simetría), casi siempre cierto.
 
Insisito por eso en que si tienes alguna intención de explotación o de propiedad intelectual debes acometer al menos esos casos que te comentaba, que son el mismo problema con ligeras perspectivas particulares, so pena de que cuando publiques, alguien los aborde y se apropie de dichos casos (porque tú no lo cubres). Nada más triste que alguien mueva cielo y tierra y luego otro que se limite a pegar una patada a una piedra (basándose en lo hecho: 'el estado actual del arte') y solo por ello sea quien se lleve la gloria.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 en 13 Agosto 2021, 17:53 pm
Tenes razon que lo importante es ver el aumento de tiempo entre cantidad de "ciudades", es para definir que tan eficiente es. Es algo que tengo que comprobar bien.

Estoy pensando todavia como adaptar el programa como solucion al problema sin volver al origen. En este momento estoy teniendo tiempo libre, asi que voy a ver si puedo readaptarlo y cuando lo haga te muestro el resultado, que estimo sera el mismo que con tu programa, y el tiempo de ejecucion con la cantidad de nodos visitados.

Es totalmente cierto que ya 4 ojos ven mas que dos y este proyecto lo estoy haciendo solo. Segun toda la logica que utilice, para mi (de manera objetiva), resuelvo el problema de un circuito cerrado de manera eficaz.

Entre el tiempo de analisis de la solucion, pseudocodigos, codigo y pruebas llevo 5 años. En los cuales lo fui haciendo mientras tenia tiempo libre. Estimo que luego de hacer codigos, analizarlos y probarlos por el equivalente de un mes de trabajo 24/7, consegui que sea eficaz.

Espero que puedas adaptarlo al problema con vuelta al origen y ahi poder comparar de manera efectiva los resultados.

Ahora adapte el programa para tu caso. Como resultado fue el mismo, 6611159.
Tardo casi 12 minutos y analizo 15470 nodos.

Te agradezco mucho la colaboracion que estas haciendo y que me haces porque pude descubrir un par de falencias que tenia mi programa original y comparar mi programa modificado con el tuyo.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 15 Agosto 2021, 00:09 am
Tenes razon que lo importante es ver el aumento de tiempo entre cantidad de "ciudades", es para definir que tan eficiente es.
De forma absoluta será imposible establecerlo, pero interesará conocer tiempos para 10, 20, 30, 40, 50 ciudades y ver como evoluciona entre ellos. Por fuerza bruta en un pc llegado cierto número es inabordable.
 
Estoy pensando todavia como adaptar el programa como solucion al problema sin volver al origen. En este momento estoy teniendo tiempo libre, asi que voy a ver si puedo readaptarlo y cuando lo haga te muestro el resultado, que estimo sera el mismo que con tu programa, y el tiempo de ejecucion con la cantidad de nodos visitados.
Al margen de todo esto, cuando termines las adaptaciones a los diferentes problemas, deben también considerar la misma funcionalidad desde la perspectiva del paralaje, es decir ver de facilitar en pseudocódigo u diseño dle algoritmo para su tratamiendo en procesado paralelo. Los superordenadores, suelen agradecerlo... Aunque no es algo obligatorio, si conviene ver que tareas puedan ser concurrentes, pués eso facilitaría a los superordenadores hacer asumible millones de nodos, en un tiempo aceptable.


Te agradezco mucho la colaboracion que estas haciendo y que me haces porque pude descubrir un par de falencias que tenia mi programa original y comparar mi programa modificado con el tuyo.
Cuando temrines de ampliar su funcionalidad y probar su eficacia, será el momento de intentar hacerlo más óptimo de cara a la velocidad, rediseñando cada parte.

Espero que puedas adaptarlo al problema con vuelta al origen y ahi poder comparar de manera efectiva los resultados.
Acabo de hacer los cambios al código y ya lo he puesto a calcular, para recorrido circular... cuando termine se podrá comparar los resultados.
He aprovechado para reordenar los nodos por pesos, así se cortocircuita antes, muchos pesos sobrepasan el valor de 1millon, y sabiendo que el recorrido mínimo ronda los 7 millones, supone que incluso se cortocircuitarán rutas con pocos nodos (lo que evita el recorrido que de ellos desciende hasta llegar a los 20 nodos con todas sus combinaciones). De hecho hay algunos pesos de incluso 2 millones.


Entre el tiempo de analisis de la solucion, pseudocodigos, codigo y pruebas llevo 5 años. En los cuales lo fui haciendo mientras tenia tiempo libre. Estimo que luego de hacer codigos, analizarlos y probarlos por el equivalente de un mes de trabajo 24/7, consegui que sea eficaz.
Es normal. A cualquiera que le apasionen estas cosas, le dedica su tiempo... (a éste y otros problemas) yo suelo dedicarle cada año, 2 o 3 semanas de mi tiempo libre.
Creo en la posiblidad de la compresión infinita y también le suelo dedicar 2 o 3 semanas, también a los primos, etc...


p.d.: Acabo de pararlo, descubrí que al editar el orden de los nodos, me comí un dígito en uno de los pesos y un peso pasaba de 1.800.000 a solo 180.000, que muy probablemente podría falsificar la solución final...
Corregido vuelvo a ponerlo a funcionar.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 16 Agosto 2021, 16:59 pm
Cuando es circular, no importa que nodo se ponga como el inicio, pues empezando por cualquier otro el recorrido sería el mismo. Es decir basta calcular como inicio un solo nodo, cuando finalice la solución es la que haya, aún así como no estaba presente cuando saltó al siguiente y no marqué el parámetro de finalizar al término del primer nodo, siguió calculando repitiendo la misma solución...


1 ---> AOELBSGITNFRCQHMKPDJA   9615287
1 ---> AOELBSGITNFRCQHMKJDPA   9611402
1 ---> AOELBSGITNFRCQHMPDJKA   9102210
1 ---> AOELBSGITNFRCPDJQHMKA   8587674
1 ---> AOELBSGITNFRCPJDQHMKA   8561109
1 ---> AOELBSGITNFRCDJPQHMKA   8551237
1 ---> AOELBSGITNFRDPJCQHMKA   8053919
1 ---> AOELBSGITNFRDJPCQHMKA   7983226
1 ---> AOEKLBSGITNFRDPJCQHMA   7846717
1 ---> AOEKLBSGITNFRDJPCQHMA   7776024
1 ---> AOEKLMHQCPJDRFNTIGSBA   7730384
1 ---> AOEKMHQCRDJPFNTIGSBLA   7708270
1 ---> AOEKMHQCRPJDFNTIGSBLA   7700976
1 ---> AOEKMHQCPDJRFNTIGSBLA   7611071
---------------------------------------------------------- Desde aquí son la misma solución en distinto orden (incluso al revés).
1 ---> AOEKMHQCPJDRFNTIGSBLA   7561324
1 ---> ALBSGITNFRDJPCQHMKEOA   7561324
1 ---> BLAOEKMHQCPJDRFNTIGSB   7561324
1 ---> BSGITNFRDJPCQHMKEOALB   7561324

La solución que ofreces queda constatado que es la solución real.

Mención aparte es que deberías hacer tu algoritmo más rápido.
Nota que mi programa aún teniendo utilidad diversa calcula unos 9-10 millones de nodos por segundo (y es un núcleo funcionando a 1'5Ghz). Aún suponiendo que el trabajo que tuviera que hacer por cada nodo fuera 100 veces mayor, seguirían siendo 90.000-100.000 nodos por segundo.
Tu dices que la solución la encuentras visitando unos 15.000-16.000 nodos, pero tarda unos 2 minutos, luego te sale que recorre 125-135 nodos por segundo, lo que es una velocidad muy baja. Por supuesto falta saber qué trabajo hay que hacer con cada nodo, pero estoy convencido que debe ser muy mejorable...

De las soluciones puestas arriba hasta la que suma: 7983226, fueron arrojadas apenas solté el botón de puesta en marcha, el resto ha ido apareciendo con las horas... Para según que cosas y casos (básicamente que precisen funcionar en tiempo real), una heurística con un valor de 7983226, que tarda menos de 1 sg en salir puede ser preferible a una solución exacta de 7561324, que tarde 2 minutos. Pero esto es solo cuando el tiempo de respuesta sea una premisa indispensable.
Aún así debes tratar de mejorar tiempos, entre x10 - x100.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 en 17 Agosto 2021, 04:56 am
Solo queria decirte que mi manera de resolverlo es diferente, pero eso visita pocas soluciones (mejores o no) en tanto tiempo.

Me interesaria saber si tu programa utiliza bastante memoria o no. Ya que por ejemplo las solucion con programacion dinamica si es necesario mucha memoria.

Estoy pensando como plantear una mejora en la eficiencia pero hasta ahora no lo logro.

Por lo menos mi programa es un paso mas para la eficacia y un paso menos para la posibilidad de demotrar P=NP, si asi lo fuera.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 17 Agosto 2021, 07:21 am
Mi programa usa muy poca memoria... apenas 2-6Mb. Depende de la cantidad de datos a introducir.
Aumenta poco más cuando pretendo que la salida vaya a fichero, y en ese caso mantengo en un buffer X entradas... (escribir a fichero las salidas una a una es costoso en tiempo, es preferible almacenarlas en un buffer y cuando se llene volcarlo de una tacada...)... al tiempo se van mostrando en un listado y cuando alcanza cierta cantidad se borran (excepto las últimas n entradas, y si se exige, antes de borrar se guardan a fichero).  Por eso fluctúa entre 2 y 6Mb. y puede que puntualmente en algún momento suba muy poco más.

Los datos (nodos) los almaceno simplemente en un array de estructura. En esa estructura un campo es Hijos() que es un array de otra estructura con el costo y un indice absoluto.
Adicionalmente la salida (temporal) se va guardando en una pila (guarda el indice absoluto del nodo, dicho índice es el que lo localiza en el array).

Los únicos datos intermedios que guarda es a través de la recursividad, de la función que ejecuta el cálculo, pero que como se operan con pocos nodos (20 en este ejemplo), el nivel de recursividad es muy limitado y tampoco se dispara el uso de la memoria.




Olvidaba decirte que si quieres probarlo bien deberás verificarlo con una buena cantidad de ejemplos y al caso hay una página buena con soluciones resueltas... los datos los dan en formato 'cordenadas 2D' (se suele indicar en cada fichero), es decir posición X e Y, por lo que requiere calcular distancias (euclídeas si fuera el caso de distancias Manhattan el mismo fichero debería señalarlo) y obliga a trabajar en algunos casos con coma flotante (en otros se trunca a enteros, lo que resulta más cómodo para deshacerse de los decimales)...

http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html
El caso que estamos tratando (en el hilo) es el que en esta página aparece el primero, el simétrico (A...Z = Z...A  .La distancia de un nodo a otro es igual a la distancia inversa del otro al uno).
Cada apartado suele terner 2 enlaces:
- El primer enlace te lleva a la página que hace de índice, donde constan enlaces a cada fichero con los datos de cada uno.
- El segundo enlace llerva a una página que contiene todas las soluciones para dichos problemas (puede que no todas sean correctas y sean solo las más próximas).
Los ejemplos los hay desde pocos nodos hasta miles de nodos, lo que da para poner a prueba prácticamente cualquier algoritmo.




Eso sí, si necesitas verificar 2 o 3 ejemplos más, pongamos de 10, 15 y 25 nodos avisa... te irá bien además de para verificar la solución como se comporta tu algoritmo en tiempos con la variación de nodos.
Más allá de 25 nodos, es muy probable que en un PC se eternice lo suficiente (con fuerza bruta, incluso cortocircuitando), como para desistir del intento... Aunque dando por entrada como valor un peso total superior en un 10-20% al valor que a ti te resulte, podría acotarlo todavía más, ya desde el principio, sin siquiera esperar a que se vaya optimizando la poda a medida que arroja resultados más cortos. ...Mientras no pase de 2 o 3 días de cálculo, por problema, no me importará echarte un cable.

Si por otro lado quieres ensayar muchas soluciones, y no depender de la lenta espera de respuestas por fuerza bruta, ni de copiar datos de aquí o de allá (sino generarlos rápidamente al azar) mira de implementar el algoritmo de Christofides, que es una heurística que se estima ofrece soluciones de alrededor de 3/2 de separación de la solución óptima.

p.d.: Añadidas algunas aclaraciones para evitar dudas.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 en 23 Agosto 2021, 02:58 am
Pude mejorar algo el programa para rendir mejor. Con el primer caso baje los 150 segundos a 50 segundos, visitando 26(en realidad son las mismas que antes, cerca de 13000. Pasa que puse una comprobacion previa a la final entonces ya me filtraban las que superaban a la que tenia guardada como mejor) soluciones (de las cuales se va quedando con la mejor hasta llegar a la mas optima)

Aunque dando por entrada como valor un peso total superior en un 10-20% al valor que a ti te resulte, podría acotarlo todavía más, ya desde el principio, sin siquiera esperar a que se vaya optimizando la poda a medida que arroja resultados más cortos.
Mi programa tambien se acorta si les pasas una solucion aproximada a la optima desde el principio.

Eso sí, si necesitas verificar 2 o 3 ejemplos más, pongamos de 10, 15 y 25 nodos avisa... te irá bien además de para verificar la solución como se comporta tu algoritmo en tiempos con la variación de nodos.
Dale gracias, voy a probar con casos reales de 25 nodos (ahi te paso algun caso para ver como se comporta el algoritmo frente a otra cantidad de entradas).

Voy a empezar a probar con casos reales de n=30 tambien para ver como se comporta el programa.

Queria agregar que mientras busca el programa la mejor opcion va mostrando la mejor encontrada hasta el momento. por ej. si lo comparamos con una heuristica, mi programa encuentra la solucion de 7611071 en menos de dos segundos, antes de encontrar la optima (7561324)


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 2 Septiembre 2021, 22:12 pm
Vaya, no me había dado cuenta... Al editarte en el mismo mensaje, no aparece como nuevo contenido pues no cambia la fecha de creación y la de edición no comporta su actualización en el hilo.

Citar
Queria agregar que mientras busca el programa la mejor opcion va mostrando la mejor encontrada hasta el momento. por ej. si lo comparamos con una heuristica, mi programa encuentra la solucion de 7611071 en menos de dos segundos, antes de encontrar la optima (7561324)
Como hace el mío... bien.
Pero ten en cuenta de procurar que el primer cálculo sea ya un valor no subóptimo. Imagina que fuera la ruta más larga, esto podría suponer una larga enumeración.

Yo por ejemplo, para obtener sobre ese de 20 nodos de forma rápida si ordenos los nodos (la adyacencia para cada nodo) de menor a mayor, me devuelve ya media docena de soluciones muy próximas, antes siquiera de soltar el botón del ratón, luego para llegar a la solución dada tarda algo menos de 5 minutos, si bien como es fuerza bruta (con poda), no tiene forma de saber si hay o no una solución más óptima por lo que hasta que no complete la búsqueda no puede garantizarse la solución (lógicamente si ya se conoce...).
En cambio si la entrada de datos se ofrece tal y como me la entregaste, entonces tarda todo el tiempo que te dije y la solución final aparecía alrededor de 18 horas tras su puesta en marcha (este equipo no es muy potente en comparación a los actuales, pero aú así el número de horas es significativo).

Te pongo los datos tal cual los envío como parámetro (para claridad de presentación aquí añado un '0' a la derecha para valores de 2 dígitos).

Nota que cada nodo queda así numerado alfanuméricamente:

A= B:064|C:041|D:082|E:099|F:093|G:161|H:099|I:116|J:060
B= A:064|C:069|D:044|E:105|F:130|G:200|H:150|I:174|J:122
C= A:041|B:069|D:062|E:058|F:062|G:133|H:081|I:108|J:066
D= A:082|B:044|C:062|E:071|F:111|G:177|H:139|I:169|J:127
E= A:099|B:105|C:058|D:071|F:055|G:110|H:091|I:125|J:108
F= A:093|B:130|C:062|D:111|E:055|G:071|H:036|I:071|J:070
G= A:161|B:200|C:133|D:177|E:110|F:071|H:067|I:081|J:121
H= A:099|B:150|C:081|D:139|E:091|F:036|G:067|I:035|J:054
I= A:116|B:174|C:108|D:169|E:125|F:071|G:081|H:035|J:059
J= A:060|B:122|C:066|D:127|E:108|F:070|G:121|H:054|I:059

Ahí el orden es el de los nodos: A,B,C,D...J y de esa forma tarda como dije más de 1 día...

En cambio reordenando los pesos para cada nodo y los propios nodos (según la suma d epesos que lo componen) y pasando esto como parámetro:

C= A:041|E:058|D:062|F:062|J:066|B:069|H:081|I:108|G:133
F= H:036|E:055|C:062|J:070|G:071|I:071|A:093|D:111|B:130
H= I:035|F:036|J:054|G:067|C:081|E:091|A:099|D:139|B:150
J= H:054|I:059|A:060|C:066|F:070|E:108|G:121|B:122|D:127
A= C:041|J:060|B:064|D:082|F:093|E:099|H:099|I:116|G:161
E= F:055|C:058|D:071|H:091|A:099|B:105|J:108|G:110|I:125
I= H:035|J:059|F:071|G:081|C:108|A:116|E:125|D:169|B:174
D= B:044|C:062|E:071|A:082|F:111|J:127|H:139|I:169|G:177
B= D:044|A:064|C:069|E:105|J:122|F:130|H:150|I:174|G:200
G= H:067|F:071|I:081|E:110|J:121|C:133|A:161|D:177|B:200

Nota que para cada fila los nodos están ordenados por pesos... y además las filas están ordenadas según la suma de los pesos de sus nodos, en ambos casos de menor a mayor, así la primera combinación hallada, se forma prácticamente con pesos muy bajos y por tanto poda exageradamente la cantidad de nodos a visitar... el comportamiento de la búsqueda de este modo, al final viene a ser muy equivalente a ciertas características (pero mucho menos compleja) que ofrece el algoritmo de Steinhaus.
...y de esta forma la solución aparece en menos de 5 minutos y la verificación completa en algo menos de 1 hora (creo recordar)...

Mira de aprovechar a introducir los datos siguiendo el mismo esquema de orden explicado (no hay necesidad de que identifiques los nodos a mi manera (id ':' peso'|'... etc), con tal que tras marcar el orden sigas pudiendo identificarlos correctamente), si ahora tienes podado cuando el peso acumulado supera el total menor hallado hasta el momento, esto acotará aún más con lo que ganarás muchísimo en tiempo (probablemente lo dividas entre 10 o más, y tanto más cuanto más nodos tenga).
Obviamente que sea así, va a depender del tipo ramificación y poda que esté efectuando tu algoritmo.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 3 Septiembre 2021, 00:57 am
Olvidé señalar que los datos de los nodos y pesos que puse de ejemplo, no corresponden con los que me pasaste que con cifras tan grandes ocupa mucho ancho... pero que igualmente cualquier otra tabla de datos (como la presente más breve) cumple el cometido se servir de ejemplo por igual y con algo más de claridad si cabe...


Curioso... mi primer doble post forzado por la imposibilidad de editar el mensaje...  :laugh: :laugh: :laugh:


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 en 3 Septiembre 2021, 08:57 am
Te paso a comentar que basicamente mi algoritmo no se basa en ramificacion y poda. ademas lo puedo aplicar, con algunas variantes al codigo, a otros problemas del tipo np, cuales tambien resuelve, no tan eficientemente.

Por eso me es dificil encontrar una mejora en el tiempo de ejecucion aunque visite pocas soluciones.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 3 Septiembre 2021, 15:58 pm
Ok... Como el título del hilo lo lleva... pero he vuelto a releer tu primer mensaje y en efecto, la razón de ramificación y poda era que preguntabas para establecer diferencias y nada más.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: jca1 en 3 Septiembre 2021, 21:17 pm
Exactamente amigo, esa era mi intencion. Comparar un metodo conocido con el mio para ver si era "mejor" o no.

Por eso estaba averiguando los metodos conocidos que resuelven el problema y comprarlo con el mio. Pero ademas de los basados en ramificacion y poda no pude encontrar ningun otro.


Título: Re: Problema del viajante de comercio - Branch and Bound
Publicado por: Serapis en 3 Septiembre 2021, 23:21 pm
Hay varios... pero siempre se trata de heurísticas, pués como te dije no hay solución conocida al margen de la fuerza bruta.

Uno bastante asequible de implementar es:
---------------------------------------------------------
1 - Dividir el área en sectores (3x3 típicamente).
2 - Mientras cada sector tenga más de x nodos (5 o 6 típicamente), subdividir el sector de nuevo en más sectores (es una función recursiva, como se desprende).
3 - Cada sector finalmente se resuelve por fuerza bruta (5 o 6 nodos es algo muy rápido de resolver por fuerza bruta).
4 - Finalmente se van uniendo los sectores entre sí.

Esta última parte es la más compleja pues permite cierto margen de maniobra. Si el número de sectores al hacer la división no queda claramente acotado (esto es si son demasiados), se complica tomar decisiones, por eso la limitación de 3 es considerada muy aceptable.