Beam pruning

In cases with Or Oj, the above technique does not help us much since it always requires a full set of target costs to be calculated. An alternative is to perform a different type of searching known as beam pruning, which dynamically prunes the candidates during the search. 

In beam pruning we move from time slot to time slot as before, but, instead of enumerating the full set of patiis, we enumerate only the best paths. At a given time slot, after we have calculated tire join costs, for each node we have the best path up to that point and the total score of tire best path that leads to that point. Now we sort these total score, and discard all but tire top Nb paths. We then move to the next time slot by calculating all the join costs between these Nb nodes and the full set of N nodes in the next slot. This process is repeated until the search is complete. Beam pruning rednces the number of target-cost calculations from TN to TNb and the number of join-cost calculations from TN to TNNb- 

---