TY - JOUR
T1 - Perimeter search in restricted memory
AU - Manzini, G.
PY - 1996/10
Y1 - 1996/10
N2 - 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.
AB - 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.
KW - Artificial intelligence
KW - Combinatorial problems
KW - Design of algorithms
KW - Graph search
UR - http://www.scopus.com/inward/record.url?scp=0030263334&partnerID=8YFLogxK
U2 - 10.1016/0898-1221(96)00154-X
DO - 10.1016/0898-1221(96)00154-X
M3 - Article
SN - 0898-1221
VL - 32
SP - 37
EP - 45
JO - Computers and Mathematics with Applications
JF - Computers and Mathematics with Applications
IS - 7
ER -