Mensajes

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


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.

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.

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.

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.

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?

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.

Mi pregunta seria por ejemplo calcular el logaritmo de base 2 con la libreria math de un numero que es por ejemplo 2^(2^(100)) lo haria eficientemente?

Me refiero a si tiene alguna utilidad encontrarle alguna solucion.
Como extremadamente grande me refiero por ej al logaritmo en base 2 de 2^(2^n). Es decir que el resultado de ese logaritmo es 2^n; para n creciente linealmente, por ej. n=100 la solucion es 2^100

Buenas, quisiera saber si serviria de algo resolver un logaritmo exacto considerando que el resultado del mismo es de tamaño exponenecial. Por ejemplo el logaritmo en base 2 de 32 es 5. Pero para numeros extradamente grandes serviria para algo? Gracias