BS∗: An admissible bidirectional staged heuristic search algorithm

摘要: Abstract In order to reap the potential advantage of less extensive searching which bidirectional heuristic search algorithms offer, strategies are needed influence two wavefronts meet such that early termination will occur. The principled control strategy aims achieve this without trading running time, but can be found wanting still. An improved algorithm BS∗ is described expands significantly nodes on average than any other in same class non-wave-shaping admissible algorithms. When pitted against BHPA, only heuristically guided member class, BS∗'s efficiency time and space about 30% better. superior performance stems from use all opportunities elimination unfruitful avenues by reduction operations: nipping, pruning, trimming screening. Such operations exploit information gathered during have several spin-offs: more accurate guidance control, exposure nonpromising reduced bookkeeping overheads, further enhance performance. A noteworthy feature it first staged preserves admissibility.