ESTUDIO COMPARATIVO DE ESTRATEGIAS ESTÁTICAS Y DINÁMICAS EN PROGRAMACIÓN CON RESTRICCIONES.

Abstract

En programación con restricciones, una de las tareas más cruciales es la elección de la estrate<U+00AD> gia de búsqueda a utilizar, puesto que todas presentan un rendimiento completamente distinto que no es posible predecir a priori. El objetivo de este trabajo fue desarrollar un solver que pennita aplicar las estrategias de forma dinámica, cambiando aquellas que presentan un mal rendimiento. Inicialmente, se escogieron tres problemas y distintos tamaos para cada uno, los cuales fueron resueltos utilizando nueve estrategias de búsqueda aplicadas estáticamente. Po&<U+00AD> teriormente, se desarrolló un esquema de estrategias que aplicaba las mismas nueve estrategias dinámicamente, desechando aquellas estrategias que no lograban avances en la búsqueda, y pri<U+00AD> vilegiando a las otras. La comparación de resultados mostró que la búsqueda con estrategias dinámicas obtiene buenos resultados, debido a que resuelve una mayor cantidad de instancias, al contrario del esquema de estrategias estáticas. Incluso, si se quiere obtener buenos resultados utilizando sólo una estrategia, es necesario conocer a priori cuál de todas presenta un buen rendimiento, no así al utilizar el esquema dinámico, donde no es necesario conocer ninguna información adicional para obtener buenos resultados.