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

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


  Mostrar Mensajes
Páginas: 1 2 [3] 4 5 6
21  Programación / Programación General / Re: Problema de la mochila en: 20 Diciembre 2021, 20:27 pm
(No se si es posible responder un tema propio primero esta permitido, porque no puedo editar el inical)

Pregunte lo anterior porque hice un programa que resuelve el problema de forma eficaz, aunque a  veces tarda bastante siempre en pocos segundos me devuelve soluciones bastante aproximadas a la optima o encuentra la optima en ese momento.

Por ejemplo para un caso de n=160, siendo n la cantidad de elementos posibles para incorporar, dependediendo de la capacidad de la mochila, tarda en encontrar la solucion optima en una hora o 10 horas incluyendo verificandolo, por dos casos que probe. Con otros casos para ese n o mayor lo resolvio en un par de segundos.

No importa el tamaño de la entrada para el tiempo de ejecucion. Por ejemplo si la capacidad es de 100 o 1000000000 no modifica el tiempo de ejecucion del mismo.

Necesito algun caso que sea representativo para verficar la eficiencia. Por ejemplo para n=10 0.
22  Programación / Programación General / Problema de la mochila en: 16 Diciembre 2021, 07:03 am
Un programa que resuelva con un resultado aproximado al optimo en este problema, cuanto seria un rango de "garantia" de aproximacion para que sea considerado util?

Por ejemplo un programa que  te asegure el 1% de margen es bueno?
23  Programación / Programación General / Re: Problema del viajante de comercio - Branch and Bound 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.
24  Programación / Programación General / Re: Problema del viajante de comercio - Branch and Bound 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.
25  Programación / Programación General / Re: Problema del viajante de comercio - Branch and Bound 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)

Cita de: Serapis en 17 Agosto 2021, 07:21 am
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.

Cita de: Serapis en 17 Agosto 2021, 07:21 am
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)
26  Programación / Programación General / Re: Problema del viajante de comercio - Branch and Bound 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.
27  Programación / Programación General / Re: Problema del viajante de comercio - Branch and Bound 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.
28  Programación / Programación General / Re: Problema del viajante de comercio - Branch and Bound 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.
29  Programación / Programación General / Re: Problema del viajante de comercio - Branch and Bound 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.
30  Programación / Programación General / Re: Problema del viajante de comercio - Branch and Bound 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
Páginas: 1 2 [3] 4 5 6
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines