Portal de Periódicos da CAPES

Randomized Backtrack Search

2004; Springer Nature; Linguagem: Inglês

10.1007/978-1-4419-8917-8_8

2698-5489

Carla P. Gomes,

Data Management and Algorithms

Randomized search methods have greatly extended our ability to solve hard computational problems. In general, however, we think of randomization in the context of local search. While local search methods have proved to be very powerful, in some situations they cannot supplant complete or exact methods due to their inherent limitation: Local search methods cannot prove inconsistency or optimality. In recent years, we have seen the emergence ofan active research area focusing on the study and design of complete randomized search procedures. In this chapter we introduce the ideas and concepts underlying such randomized procedures. In particular, we describe a new generation of backtrack-style methods that exploit randomization while guaranteeing completeness. We analyze the ron time distributions ofsuch methods and show that quite often they exhibit so-called heavy tails. Heavy tailed distributions are non-standard distributions that have infinite moments (e.g., an infinite mean or variance). Such non-standard distributions have been observed in areas as diverse as economics, statistical physics, and geophysics. The understanding of the heavy-tailedness of complete backtrack search methods has led to the design of more efficient procedures. We describe such new techniques. In particular, we present different ways of randomizing complete backtrack style methods and show how restart and portfolio strategies can increase performance and robustness of such methods. We also provide formal models of heavy-tailed behavior in combinatorial search and results on performance guarantees for restart strategies.