Ahora estoy implementando una rutina, bajo un código que quiero que sea el óptimo en resultados, en tamaño y en tiempo. Expongo aquí las pautas y algunas de las limitaciones con las que me he encontrado de momento:
Supongamos que para un Conjunto Dado C tenemos N elementos, estos N elementos tienen todos por un lado un valor (podria ser un importe, p.ej) y tienen todos también un coste derivado de la relación entre C para llegar a cada undo de los elementos N.
Prentendo poder pasar unos valores CMin y CMax para los que las suma de valores de Subconjuntos del Conjunto C esten entre esos dos parámetros y de todos los posibles resultados encontrar el que me de un valor cuya suma de Costes del Subconjunto resultante sea la mínima posible de entre todas las posibilidades.
Voy a explicarlo en un ejemplo que quedará muchisimo más claro que todo este rollo raro:
Supongamos que B son Bancos y que el Conjunto C (BSCH) es el conjunto de recibos (Elementos) que deseo/puedo llevar a ese banco para descontar en N58.
Para cada Recibo N, tengo guardados 2 valores: 1º el importe del recibo, 2º el coste que me supone (aplicando los % y comisiones pactadas con el banco tratado y que tengo en una tabla de Cond. Bancarias).
CMin es un importe mínimo que yo debo llevar al banco, y del que no puedo bajar porque tengo por ejemplo, unos pagos que sé que hay que cubrir.
CMax es un importe máximo porque tengo la linea de descuento muy saturada y sólo me permite enviarles ese importe, con lo que no puedo llevar recibos que sumados superen este parametro. (con un relativo margen razonable, exacto es imposible).
Se Trata de Tratar todos Los Recibos enviados para este Banco y buscar sus posibles sumas combinatorias entre TODOS ellos y encajar ese importe entre los dos valores CMin y CMax obteniendo un Subconjunto Resultante tal que el coste de los intereses y comisiones bancarios sea el mínimo posible de todas las opciones que cumplan estos requisitos.
Notas:
Tengo desarrollados dos métodos.
- En método iterativo, es decir la programación habitual de todos nosotros, en general y la más rapida de pensar, pero no me acaba de encajar bien los resultados en cuanto al mejor coste posible.
- Lo tengo hecho por métodos de programación avanzada (y muy teoricos) por los teoremas de Dijkstra, Ford y Floyd... resumiendo... Backtraking de Seguimiento de Arboles y diagramas con el objetivo de obtener los caminos mínimos entre los distintos nodos del grafo (árbol). Este segundo la verdad es que me funciona muy bien al menos de momento, pero y parece ser el óptimo en resultados.... pero de momento me hallo en algún apurillo técnico... os lo resumo:
- El orden resultante de operaciones (sin optimizar demasiado)
- Este problema... es peor que el anterior....
Es de 2^n és decir 2 a la n, siendo n el nº de recibos. o sea que para n = 4 recibos, 6 recibos, 8, recibos, 16 recibos y 50 recibos me da un total de operaciones:
2^4 = 16 operaciones
2^6 = 64 operaciones
2^8 = 256 operaciones
2^16 = 65536 operaciones
2^25 = 33554432 operaciones
2^50 = 1125899906842624 operaciones
Quereis que os diga el problema o SALTA A LOS PUT... Ojos.... Perdonad !!!! :(
Es decir, que sera la mar de óptimo y pijo... pero al menos por el momento me es totalmente inviable... Alguien no conoce alguna empresa que lleve más de 50 recibos a descontar N58, o da igual, 25 que ya ronda los 33 millones de operaciones ????
Bueno, cabe decir que esto es para acojonar un poco, pq. hay mejoras relativamente fáciles de implementar que mejoran en algo el resultado, pero aún así ya aviso que no lo suficiente... Si estoy en algunas otras que creo que me lo pueden rebajar bastante y sino he pensado en la posibilidad de mezclar partes de los dos códigos (1º Iterativo y 2º Recursivo) y creo que por ahí tb. podria funcionar mejor (pq. así, ya es para dejarlo ahora mismo).
Ehhh... continuad leiendo... pq. a ver si me equivoco y tiene fácil solución...
Uso Técnicas de Backtracking y recursividad, eso significa llamadas dentro de la función X a la misma Función X, que pasa ??? que si no logro hallar un resultado o cortar (podar) el árbol de llamadas, llega un momento en que me salta un error de OverFlow por Anidamiento... no recuerdo cual es el máximo de llamadas anidadas permitidas en Vfp. 6.0 pero Toni Planas (Buen Compañero mío, saludos REY !!!!) me comento que le suena o cree que son 27... por lo que tengo el problema que aún solucionando lo de las combinaciones que seria resolver el tiempo de ejecución, estaria delante del problema técnico de que si no resuelvo (por bueno) o corto (por malo) el proceso de cada posibilidad antes de llegar a este "suspuesto" limite técnico... me "petará" por desborde.
La pregunta es ??? es evitable modif. algun parametro o set ??? pasa en Vfp. 8 o en Vfp. 9... y en ASP (pq. seguramente lo acabaré traduciendo) ???
Os pongo un ejemplo (con nº's totalmente aleatorios, pero para que veais el funcionamineto):
CMax = 9999999 (sin limite), pero CMin=15000 Conjunto C (Vector) && Valores aleatorios, son sólo para pruebas !!!! Pos Imp Coste [1] 8,727 (20.40) [2] 9,147 (22.15) [3] 1,142 ( 6.34) [4] 4,111 (11.67) [5] 3,152 (35.36) [6] 2,164 (19.09) ****************************************************************************************************************************** [1] 0 ( 0.00)+[2] 0 ( 0.00)+[3] 0 ( 0.00)+[4] 0 ( 0.00)+[5] 8,727 (20.40)+[6] 9,147 (22.15) = 17,874 * (42.55) [1] 0 ( 0.00)+[2] 0 ( 0.00)+[3] 0 ( 0.00)+[4] 4,111 (11.67)+[5] 8,727 (20.40)+[6] 9,147 (22.15) = 21,985 * (54.22) [1] 0 ( 0.00)+[2] 0 ( 0.00)+[3] 3,152 (35.36)+[4] 0 ( 0.00)+[5] 8,727 (20.40)+[6] 9,147 (22.15) = 21,026 * (77.91) [1] 0 ( 0.00)+[2] 0 ( 0.00)+[3] 3,152 (35.36)+[4] 4,111 (11.67)+[5] 0 ( 0.00)+[6] 9,147 (22.15) = 16,410 * (69.18) [1] 0 ( 0.00)+[2] 0 ( 0.00)+[3] 3,152 (35.36)+[4] 4,111 (11.67)+[5] 8,727 (20.40)+[6] 0 ( 0.00) = 15,990 * (67.43) [1] 0 ( 0.00)+[2] 2,164 (19.09)+[3] 0 ( 0.00)+[4] 0 ( 0.00)+[5] 8,727 (20.40)+[6] 9,147 (22.15) = 20,038 * (61.64) [1] 0 ( 0.00)+[2] 2,164 (19.09)+[3] 0 ( 0.00)+[4] 4,111 (11.67)+[5] 0 ( 0.00)+[6] 9,147 (22.15) = 15,422 * (52.91) [1] 0 ( 0.00)+[2] 2,164 (19.09)+[3] 0 ( 0.00)+[4] 4,111 (11.67)+[5] 8,727 (20.40)+[6] 0 ( 0.00) = 15,002 * (51.16) [1] 0 ( 0.00)+[2] 2,164 (19.09)+[3] 3,152 (35.36)+[4] 0 ( 0.00)+[5] 8,727 (20.40)+[6] 9,147 (22.15) = 23,190 * (97.00) [1] 0 ( 0.00)+[2] 2,164 (19.09)+[3] 3,152 (35.36)+[4] 4,111 (11.67)+[5] 0 ( 0.00)+[6] 9,147 (22.15) = 18,574 * (88.27) [1] 0 ( 0.00)+[2] 2,164 (19.09)+[3] 3,152 (35.36)+[4] 4,111 (11.67)+[5] 8,727 (20.40)+[6] 0 ( 0.00) = 18,154 * (86.52) [1] 1,142 ( 6.34)+[2] 0 ( 0.00)+[3] 0 ( 0.00)+[4] 0 ( 0.00)+[5] 8,727 (20.40)+[6] 9,147 (22.15) = 19,016 * (48.89) [1] 1,142 ( 6.34)+[2] 0 ( 0.00)+[3] 0 ( 0.00)+[4] 4,111 (11.67)+[5] 8,727 (20.40)+[6] 9,147 (22.15) = 23,127 * (60.56) [1] 1,142 ( 6.34)+[2] 0 ( 0.00)+[3] 3,152 (35.36)+[4] 0 ( 0.00)+[5] 8,727 (20.40)+[6] 9,147 (22.15) = 22,168 * (84.25) [1] 1,142 ( 6.34)+[2] 0 ( 0.00)+[3] 3,152 (35.36)+[4] 4,111 (11.67)+[5] 0 ( 0.00)+[6] 9,147 (22.15) = 17,552 * (75.52) [1] 1,142 ( 6.34)+[2] 0 ( 0.00)+[3] 3,152 (35.36)+[4] 4,111 (11.67)+[5] 8,727 (20.40)+[6] 0 ( 0.00) = 17,132 * (73.77) [1] 1,142 ( 6.34)+[2] 2,164 (19.09)+[3] 0 ( 0.00)+[4] 0 ( 0.00)+[5] 8,727 (20.40)+[6] 9,147 (22.15) = 21,180 * (67.98) [1] 1,142 ( 6.34)+[2] 2,164 (19.09)+[3] 0 ( 0.00)+[4] 4,111 (11.67)+[5] 0 ( 0.00)+[6] 9,147 (22.15) = 16,564 * (59.25) [1] 1,142 ( 6.34)+[2] 2,164 (19.09)+[3] 0 ( 0.00)+[4] 4,111 (11.67)+[5] 8,727 (20.40)+[6] 0 ( 0.00) = 16,144 * (57.50) [1] 1,142 ( 6.34)+[2] 2,164 (19.09)+[3] 3,152 (35.36)+[4] 0 ( 0.00)+[5] 0 ( 0.00)+[6] 9,147 (22.15) = 15,605 * (82.94) [1] 1,142 ( 6.34)+[2] 2,164 (19.09)+[3] 3,152 (35.36)+[4] 0 ( 0.00)+[5] 8,727 (20.40)+[6] 0 ( 0.00) = 15,185 * (81.19) [1] 1,142 ( 6.34)+[2] 2,164 (19.09)+[3] 3,152 (35.36)+[4] 4,111 (11.67)+[5] 0 ( 0.00)+[6] 9,147 (22.15) = 19,716 * (94.61) [1] 1,142 ( 6.34)+[2] 2,164 (19.09)+[3] 3,152 (35.36)+[4] 4,111 (11.67)+[5] 8,727 (20.40)+[6] 0 ( 0.00) = 19,296 * (92.86) ****************************************************************************************************************************** [1] 0 ( 0.00)+[2] 0 ( 0.00)+[3] 0 ( 0.00)+[4] 0 ( 0.00)+[5] 8,727 (20.40)+[6] 9,147 (22.15) = 17,874 *(42.55)
Notas: Cabe decir que en este ejemplo ya se ve una de las mejoras, pero no siempre sale así de rapido, aunque es bueno que tengamos este.
Los elementos, se deben procesar (TODOS CON TODOS, no es necesario un orden concreto, siempre que su suma supere CMIN y por debajor de CMAX (más o menos, este valor es más de referencia)
Mejoras propuestas (algunas ya implementadas, otras aún no):
- Ordenar los Elementos de de C por Importe ASC, de esta forma, hallando el 1er elemento que supere CMIN, podemos obtener un primer SubConjC que seran todos los valores que de por si ya superen CMin y de ellos buscar el de mín. coste con lo que obtendriamos un primer candidato a falta de procesar ahora ya con otro metodo los que han quedado por debajo de CMIN.
- Si al vector que nos ha quedado ahora con los elementos de C cuyo importe sea menor q CMIN y por tanto necesitaremos sumarlos con otro/s de este vector para cubrir el minimo requerido. Si ordenamos estos por Importe DESC... las primeras sumas llegaran mucho más rapido al mín. que si lo hacemos al revés... y de esta forma ya empezamos a tener unos costes mín. que nos permitiran (ver. Punto 3)
- Teniendo almacenado el Subconjunto que de momento nos de el coste mín. y la suma de costes de esos elementos nos dará ese valor... si procesamos otra posibilidad, y aunque no la hayamos terminado, en algun momento su mín ya supera el que nosotros tenemos como óptimo... no hace falta continuar... pq. no lo mejorariamos... ok ???
Buenos... Mentes !!!! Os pido, si teneis ganas... porque es un poco galimatias... que penseis en mejoras o si de existir en limitaciones técnicas... sabéis de formas de eviatrlas o de versiones que las amplien...
Y por dudas, ya sabeis... un mensaje y hablamos...
Grácias a todos y un fuerte abrazo.....
VIsual FoxPro ForEver !!!
Josep Mª Picañol
Solo para estar claro, los costes son porcentualmente iguales para los importes? Es decir, siempre los costes son un n% del importe o estos varian porcentualmente? Si varian, puedes calcular el porcentaje del coste sobre el importe y en funcion a dicho porcentual puedes ordenar ascendente y comenzar a sumar hasta que superes el valor cmin o hasta que alcances el valos cmax, segun lo desees.
ResponderBorrar