Page 46 - revista 2019

Revista de la Facultad de Ingeniería, Año 6, Número 1
const costOfSeries = (p, q) => {
const s = totalWidth(p, q); // suma de anchos de p hasta q
if (s <= AW) return { cost:(AW-s)**2, br:q };

let opt = Infinity;
for (let r = p; r < q; r++) {
const x= costOfSeries(p,r) + costOfSeries(r+1,q);
if (x < opt) opt = x;
}
return opt;
}
Listado 3: El cálculo del costo óptimo para el agregado de espacios en
blanco, usando el algoritmo descrito en el texto.

Un problema remanente

El algoritmo implementado resuelve eficazmente el problema, pero con un defecto,
particularmente notorio con cantidades altas de campos: con frecuencia recalcula el
costo de una posible partición que ya había calculado antes. Véase la figura 5, que
muestra todos los intentos que hace el algoritmo en nuestro ejemplo, y nótense
cuántas veces se repiten valores.

Figura 5: Los intentos que hace el algoritmo en nuestro ejemplo.
Muchas subsecuencias (como 5,3,6 o 2,5) aparecen múltiples veces
obligando a repetir cálculos ya hechos antes.

¿Cómo se puede resolver el problema? Esto cae en el área de la llamada
“programación dinámica”, y tiene una solución sencilla y funcional: aplicar
“memoización”, una técnica que utiliza una “cache” de valores previamente calculados
para evitar repetir procesos. En nuestro caso particular, la utilización de la librería
fast-memoize (disponible en https://www.npmjs.com/package/fast-memoize) fue
suficiente, y el algoritmo se tornó altamente eficiente; véase el listado 4.

const costOfSeries = memoize((p, q) => { … })
Listado 4: Utilizar memoización optimizó el algoritmo, evitando
recalcular costos ya computados anteriormente.

Confesión final

El lector avisado, que conozca el software de preparación de textos TEX, puede saber
de la existencia del algoritmo Knuth-Plass, que resuelve un problema análogo al
planteado en el artículo, buscando dar formato a un párrafo del modo más armonioso
posible, decidiendo qué palabras ubicar en cada línea, y agregando espacios en
blanco de un modo estético.
Una vez implementada la solución recursiva descrita arriba, y habiendo logrado una
comprensión más cabal de cómo se buscaba la solución óptima, pude convertir el

45