1. Perimeter search in restricted memory
- Author
-
Giovanni Manzini
- Subjects
Artificial intelligence ,Graph theory ,Computer Science::Computational Geometry ,Graph search ,Combinatorial problems ,Perimeter ,Computational Mathematics ,Qualitative analysis ,Computational Theory and Mathematics ,Modelling and Simulation ,Modeling and Simulation ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Hardware_INTEGRATEDCIRCUITS ,Graph (abstract data type) ,Mathematics::Metric Geometry ,Pruning (decision trees) ,Minimum cost path ,Algorithm ,Large size ,Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS ,Design of algorithms - Abstract
In this paper, we consider the problem of finding a minimum cost path in a graph. In particular, we consider the perimeter search technique and we investigate the possibility of using very large perimeters. We present an algorithm designed to use perimeters of arbitrary size. Our algorithm generates the perimeter incrementally and makes use of a technique called backward pruning for reducing the search effort. A qualitative analysis and experimental results show that our algorithm can effectively use perimeters of very large size.
- Published
- 1996