Bienvenido Invitado!

Búsqueda Rápida:  

Búsqueda Avanzada

Idiomas: English Español

Valid XHTML 1.0 Transitional ¡CSS Válido! Icono de conformidad con el Nivel Doble-A, 
	de las Directrices de Accesibilidad para el 
	Contenido Web 1.0 del W3C-WAI

Contributions to Search and Inference Algorithms for CSP and Weighted CSP


Contributions to Search and Inference Algorithms for CSP and Weighted CSP
Contributions to Search and Inference Algorithms for CSP and Weighted CSP

Martí Sánchez Fibla

Filiación: Consejo Superior de Investigaciones Científicas. Institut d'Investigació en Intel-ligencia Artificial (Bellaterra, España)

Biografía: No disponible

Cerrar ventana

Martí Sánchez Fibla

Acerca de los autores 

Año de publicación: 2006

Idioma: inglés

Materias: Ciencia y Tecnología

Colección: Monografies de l'Institut d'Investigació en Intel-ligencia Artificial

eBook gratuito

Resumen:

This thesis presents a collection of new algorithms for solving Constraint Satisfaction Problems (CSP) and Weighted Constraint Satisfaction Problems (WCSP). We pursue two main objectives: enhancing solving methods forWCSP, which are of recent development, and narrowing the gap between search and inference methods. The first part of the thesis is devoted to search methods for solving WCSP. In a branch-and-bound context, the lower bound computation in each node of the search is of great importance and has a serious impact in the practical efficiency of algorithms. We start from an algorithm called Rus- sian Doll Search (RDS) that has a costly, yet very powerful lower bound and we develop three enhancements of it: Specialized RDS (SRDS), Full SRDS and Opportunistic SRDS. We then tackle the problem of exploiting the global structure of the problem inside search. An algorithm exists for CSP that is able to exploit what is called pseudo-tree structure. We extend it to WCSP, obtaining algorithm Pseudo Tree Partial Forward Checking (PT-PFC). This algorithm has a source of inefficiency mainly related to bad quality local lower and upper bounds. We suggest a solution to this problem by combining pseudo-tree search for WCSP with the RDS techniques that we previously developed obtaining algorithms PT-RDS and PT-SRDS. In all this first part the aim is enhancing the practical efficiency of existing search algorithms with respect to the time spent in solving several benchmarks. The second part of the thesis is devoted to complete inference methods for solving CSP and WCSP. Complete inference solves the problem by a sequence of transformations that obtain an equivalent problem. In these transformations variable elimination plays an important role. We present some new inference operations that permit us to factorize a constraint into a set of smaller size constraints. We then introduce factorization into variable elimination.

Ver Índice Ver Índice (0.05 Mb)

Vista previa Vista previa (0.12 Mb)

Información bibliográfica

Descripción física del libro: XVIII, 167 p. : gráf. ; 24 cm

ISBN: 978-84-00-08432-5

Publicación: Bellaterra (España) : Consejo Superior de Investigaciones Científicas, 2006

Referencia CSIC: 1330

Otros datos: Tesis. Universidad Politécnica de Cataluña (España), 2006

Adquirir la edición digital en

Este eBook está disponible en descarga gratuita

Descargas gratuitas

Para descargar el eBook debe estar registrado

Este título está en nuestro catálogo electrónico desde el jueves 18 junio, 2015.