Tesis doctoral de Carlos Mateu Piñol
Part of the current research in artificial intelligence is focused in resolving and studying the problems known as search problems, especially the ones which are proven to have non-polinomial hardness (np). many of these problems (sat, csp, etc.) Are resolution-based logic search problems, and, interestingly, in many cases, present an explosion of hardness for some instances. Until ai research has centered his efforts in the research related in the worst case of these problems, how to test, for example, the np- completeness of concrete problems, compare the hardness with other np problems, that is, in fact, trying to answer the basic question: is n=np? recently more and more attention has been devoted to the study of such problems, but not in their worst case but in the typical case, that is, the behaviour of problems in their globality. This is because some instances of problems, spite not having, a priori, more hardness than others, require more (in some cases we are talking of orders of magnitude higher) computation efforts to be solved. The core of the question we try to answer is, for the chosen problems studied, why by simply changing a few simple parameters, the balancing of the distribution of holes in a sudoku, the number of colors in an edge puzzle, etc. The time required to solve those instances boosts, sometimes event making totally impossible to solve the problems. another important aspect of the research in ai is the building of test sets for benchmarking that help to the design of more and better programs and algorithms of resolution. Having available tools for building test sets and benchmarks that allow solver builders to choose hardness, adjust some other parameters as desired, etc. Is crucial for the correct development of solving algorithms. this thesis contributes to both problems, the one to comprise better the problems hardness and the other one, to create tools to build, as desired, sets of problems, with the selected hardness and having some predefined characteristics. On the one hand have studied several problems: random binary csp, generalised sudoku problems and edge matching puzzles. We studied which factors contribute to the hardness in the typical case, and modifying these factors one can increase hardness (increases that reach several orders of magnitude in some cases) and we propose explanations of which effect have these factors in the heuristic and algorithms of resolution.On the other hand have designed mechanisms for the systematic and easy building of problem instances, where the researcher can choose, easily, some building parameters that will have a re ection in the structure of the problem as well as in the level of resulting hardness. an additional result has been the formalitzation and definition of a new problem, edge matching puzzles, one variation of the kids puzzles and that have revealed as a structured np problem easily defined but with an extraordinary hardness. We have designed three variants of the problem, proposing very efficients mechanisms for building instances of the problem and that allow to obtain always satisfiable problems as well as normal problems. of this problem we have done also an extensive study of which factors in uence on the hardness of the instances, of how small variations on problem definitions, for example the number of colors, have a tremendous impact on problem hardness. We have also done an intensive and exhaustive analytical 1 analysis, characterizing and locating the phase transition, as well as, defining analytic expressions of boundaries of the phase transition. 2
Datos académicos de la tesis doctoral «Csp problemas as algorithmic benchmarks: measures, methods and models«
- Título de la tesis: Csp problemas as algorithmic benchmarks: measures, methods and models
- Autor: Carlos Mateu Piñol
- Universidad: Lleida
- Fecha de lectura de la tesis: 30/01/2009
Dirección y tribunal
- Director de la tesis
- Ramon Bejar Torres
- Tribunal
- Presidente del tribunal: felip Manya serres
- Álvaro Del val (vocal)
- chu-min Li (vocal)
- Manuel Ojeda aciego (vocal)