<p>Un Problema de Satisfacción de Restricciones o CSP se representa por medio de variables, dominios y restricciones. La forma en que se encuentra una solución para un CSP, depende entre otros de las Técnicas de Consistencia que se utilicen. Las técnicas de consistencia ayudan a reducir la cantidad de nodos que se instancian en el proceso de búsqueda. La técnica utilizada en el presente proyecto es la Arco-Consistencia, la cual se aplicará a restricciones binarias. Existe una amplia gama de algoritmos de arco-consistencia, pero esta investigación se centrará en los algoritmos AC-1 y SAC-1. La idea es intercalar ambos algoritmos bajo un esquema de Arco-Consistencia Adaptativa, en el cual se aplicará la técnica más apropiada en las diferentes partes del proceso en base a indicadores de rendimiento</p>
<p>A Constraint Satisfaction Problem or CSP is represented by means of variables, domains, and constraints. The way in which solutions are found for a CSP, depends among others on the Consistency Techniques employed. The consistency techniques help to reduce the amount of nodes that are instantiated in the search process. The consistency technique used in this thesis is Arc-Consistency, which is applied to binary constraints. There exist several arc-consistency algorithms, but this work focuses on the AC-1 and SAC-1 algorithms. The idea is to interleave both algorithms under an Adaptive Arc-Consistency schema, in which the more appropriate technique will be applied on the different parts of the process based on performance indicators</p>
last modification
Ingeniero de Ejecución en Informática
INGENIERIA DE EJECUCION INFORMATICA
<p>Un Problema de Satisfacción de Restricciones o CSP se representa por medio de variables, dominios y restricciones. La forma en que se encuentra una solución para un CSP, depende entre otros de las Técnicas de Consistencia que se utilicen. Las técnicas de consistencia ayudan a reducir la cantidad de nodos que se instancian en el proceso de búsqueda. La técnica utilizada en el presente proyecto es la Arco-Consistencia, la cual se aplicará a restricciones binarias. Existe una amplia gama de algoritmos de arco-consistencia, pero esta investigación se centrará en los algoritmos AC-1 y SAC-1. La idea es intercalar ambos algoritmos bajo un esquema de Arco-Consistencia Adaptativa, en el cual se aplicará la técnica más apropiada en las diferentes partes del proceso en base a indicadores de rendimiento</p>
<p>A Constraint Satisfaction Problem or CSP is represented by means of variables, domains, and constraints. The way in which solutions are found for a CSP, depends among others on the Consistency Techniques employed. The consistency techniques help to reduce the amount of nodes that are instantiated in the search process. The consistency technique used in this thesis is Arc-Consistency, which is applied to binary constraints. There exist several arc-consistency algorithms, but this work focuses on the AC-1 and SAC-1 algorithms. The idea is to interleave both algorithms under an Adaptive Arc-Consistency schema, in which the more appropriate technique will be applied on the different parts of the process based on performance indicators</p>