<p>Este trabajo pretende proponer una forma interesante de resolver problemas complejos utilizando Programación con Restricciones (CP), particularmente el Problema del Vendedor Viajero (TSP). Para ello, se presentan conceptos y definiciones de la Programación con Restricciones, pasando por técnicas, algoritmos y heurísticas, poniendo énfasis en la Satisfacción de Restricciones (CSP), pues se orienta a los problemas con dominios finitos y posteriormente con Problemas de Optimización con Satisfacción de Restricciones (CSOP). También se describe el TSP, presentando su definición, un breve repaso histórico de los intentos por resolverlo para muchas ciudades y mencionando algunos métodos surgidos/utilizados en el desarrollo hehco por los primeros investigadores. Además se presenta una herramienta con la cual se enfrentó este desafío: Mozart/Oz, mostrando sus ventajas y características que nos ayudarán con el objetivo principal, el que es resolver el TSP y posteriormente se mostrarán unos problemas clásicos de CSP. Luego, se presentará un modelamiento del TSP como un CSOP y su adaptación a Oz, logrando elaborar un Prototipo de Sistema, pudiendo surgir alguna novedad digna de publicación</p>
<p>This report expects to suggest an interesting way to solve complex problems using Constraint Programming (CP), specifically the Travelling Salesman Problem (TSP). To manage this goal, here are showed concepts and definitions of Constraint Programming, as well the techniques, algorithms and heuristics, emphasizing the Constraint Satisfaction Problems (CSP), because this directs to the problems with finite domains and later with Constraint Satisfaction Optimization Problem (CSOP). Here is described the TSP too, presenting its definition, a short historic revision of the attempts to solve it oriented to a lot of cities and naming some methods emerged/used in the development done by the first researchers. Besides, here is presented a tool which will help us managing the main goal, which is solve the TSP as a CSOP and its adaptation to Oz, managing to elborate a System Prototype, maybe emerging a newness worthy of publication</p>
last modification
Ingeniero de Ejecución en Informática
INGENIERIA DE EJECUCION INFORMATICA
<p>Este trabajo pretende proponer una forma interesante de resolver problemas complejos utilizando Programación con Restricciones (CP), particularmente el Problema del Vendedor Viajero (TSP). Para ello, se presentan conceptos y definiciones de la Programación con Restricciones, pasando por técnicas, algoritmos y heurísticas, poniendo énfasis en la Satisfacción de Restricciones (CSP), pues se orienta a los problemas con dominios finitos y posteriormente con Problemas de Optimización con Satisfacción de Restricciones (CSOP). También se describe el TSP, presentando su definición, un breve repaso histórico de los intentos por resolverlo para muchas ciudades y mencionando algunos métodos surgidos/utilizados en el desarrollo hehco por los primeros investigadores. Además se presenta una herramienta con la cual se enfrentó este desafío: Mozart/Oz, mostrando sus ventajas y características que nos ayudarán con el objetivo principal, el que es resolver el TSP y posteriormente se mostrarán unos problemas clásicos de CSP. Luego, se presentará un modelamiento del TSP como un CSOP y su adaptación a Oz, logrando elaborar un Prototipo de Sistema, pudiendo surgir alguna novedad digna de publicación</p>
<p>This report expects to suggest an interesting way to solve complex problems using Constraint Programming (CP), specifically the Travelling Salesman Problem (TSP). To manage this goal, here are showed concepts and definitions of Constraint Programming, as well the techniques, algorithms and heuristics, emphasizing the Constraint Satisfaction Problems (CSP), because this directs to the problems with finite domains and later with Constraint Satisfaction Optimization Problem (CSOP). Here is described the TSP too, presenting its definition, a short historic revision of the attempts to solve it oriented to a lot of cities and naming some methods emerged/used in the development done by the first researchers. Besides, here is presented a tool which will help us managing the main goal, which is solve the TSP as a CSOP and its adaptation to Oz, managing to elborate a System Prototype, maybe emerging a newness worthy of publication</p>