Evaluando la eficiencia de utilizar funciones de seleccion en Busqueda Autonoma para resolver problemas de satisfaccion de restricciones

摘要

La programacion con restricciones (CP, del ingles Constraint Programming) es un poderoso paradigma que permite resolver problemas de optimizacion y satisfaccion de restricciones (CSPs, del ingles Constrain Satisfaction Problems). En este contexto, la eficiencia en la resolucion de un problema cumple un rol fundamental, debiendo ser considerada y abordada al momento de emplear la estrategia de solucion. Infortunadamente, la correcta seleccion de una estrategia de enumeracion es una tarea compleja debido a que su comportamiento es comunmente impredecible. Recientemente, la busqueda autonoma (AS, del ingles Autonomous Search) aparecio como una nueva tecnica para enfrentar esta problematica. La idea es proveer al solver de un componente que permita adaptar la estrategia de resolucion durante el proceso busqueda. Esta tarea se realiza mediante una funcion de seleccion (CF, del ingles Choice Function) que decide como actualizar el proceso de resolucion en base a cierta informacion de rendimiento. En este trabajo, evaluamos el impacto y la eficiencia al utilizar 16 diferentes funciones de seleccion. Para esta evaluacion, se resolvieron diferentes instancias de problemas de satisfaccion de restricciones conocidos. Los resultados obtenidos son prometedores, permitiendo determinar cual es la mejor funcion de seleccion para resolver todas las instancias propuestas.