Mensajes

(Anexo a la respuesta anterior)

dado el siguiente caso:

Código [Seleccionar] Expandir


N.º Peso               Valor
1 14588629582201 5276815605906449
2 164481749688609 5309583717329863
3 205730373531307 5329619489437584
4 252647202569584 5351726706158925
5 294237552790977 5402634651035046
6 415181102709367 5405325301196649
7 434780283185498 5417046718888412
8 465917639958693 5418284601208041
9 554402676232595 5475914904362073
10 570762890865167 5509074226169616
11 676948759488896 5512123417247576
12 722432831098187 5586140217535448
13 724431178666991 5605648760042149
14 750115619388679 5659147215091773
15 767532286296282 5672758862613367
16 805479261049720 5718541164990366
17 933983003197288 5755950295957769
18 964903427617290 5817984823603671
19 968909610981529 5828974554324587
20 997164240119792 5881242195696504
21 1048554293757143 5955109549493639
22 1085570198596243 5970191308655077
23 1098851601119926 6021398401233982
24 1147687850942615 6057551745848646
25 1148433096804838 6279047299857968
26 1188411530030867 6366904495894766
27 1271938645908964 6393860287734480
28 1357117387177604 6519366374354713
29 1447195478900452 6551646480181343
30 1556534107790089 6557613168721194
31 1559119676724087 6590444598501222
32 1580471353626150 6629364614158954
33 1735225735130097 6696299838863670
34 1759133415526008 6697415756909721
35 1813730017820853 6699162991267490
36 1892357073236775 6735135925533815
37 1911259514509681 6764895627970755
38 1958167030106420 6770695126240527
39 1988235790360112 6783967615583307
40 2004018705707521 6830595071813376
41 2141104984662408 6837461712643138
42 2207317799259911 6911539385457124
43 2305245458608990 6951880747850561
44 2353285882893806 7199704563057061
45 2363762300213971 7228569651257108
46 2415912643427303 7280963172091236
47 2483335978970459 7285338167243996
48 2527310498394226 7290912494886235
49 2551558082842607 7331439557342070
50 2592323784553049 7414104963913833
51 2618462919006518 7417190758670783
52 2725340604879525 7451375374319646
53 2821191984321125 7456898659281466
54 2835636356341224 7524400557383184
55 2919694296870452 7556547691726496
56 3117855357230428 7643253397123820
57 3145882483177681 7672510310469968
58 3148517125221016 7715429902735608
59 3173753865595647 7771322288053085
60 3360562551278537 7914394010025391
61 3361737942812948 7927626434187542
62 3386568927394721 8062225188866445
63 3524312511843557 8066243838157770
64 3599003372021800 8097518611056720
65 3687280612987549 8287348439310476
66 3715781931278740 8383792061193192
67 3751158179366618 8398655622974535
68 3774487286153027 8519605300856544
69 3854286562672970 8611492791577488
70 3922938816117466 8618636776076155
71 3924102778834234 8656646539594801
72 3987367808660507 8719642379543156
73 3992220686647404 8798177552369334
74 4067815889695279 8831336822336017
75 4081090309524788 8984045549919634
76 4091090835755164 9067607970045600
77 4126990037052735 9196866186462930
78 4192980163989298 9239464367406860
79 4202952786124747 9306314970030520
80 4210642310426149 9329299874734760
81 4548566581986690 9346681178913830
82 4610897182334249 9366482189852440
83 4700747016242553 9374307609037140
84 4700763956342967 9395374111692680
85 4747516552870209 9405008740374730
86 4799519192435085 9417045063565950
87 4826205978907101 9515829014412590
88 4850454702930504 9542452333533330
89 4868109181475080 9544057672078040
90 4892015341643560 9596261329102120
91 4948212836341631 9615077594608100
92 4949994894249733 9616473285575660
93 4984917788690850 9641239080722050
94 5006490721341773 9668840597169840
95 5102409351675896 9680754460736420
96 5106902448954033 9738354540800340
97 5181181650349445 9738453838963910
98 5191189542489884 9826278439510520
99 5232372271067336 9902150581273970
100 5239315202757033 9991436711981470

Existe algun programa que lo resuelva de manera eficaz y relativamente de manera eficiente, para un capacidad de la mochila de 30000000000000000 ?

Para este caso especifico pude conseguir el resultado mas optimo, encontrandolo y verificandolo como tal en 1 segundo.

P.D.: es cierto que la relacion entre los pesos y valores favorecen a la eleccion de la mejor solucion. Proximamente voy a mostrar otro caso y a ver como lo resuelve

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

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?

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.

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.

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)

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.

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.

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.

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.