Beam Search

Detailed Beam Search(contd.)

• Set B = ∅.
• Select the min {β, |C|} best nodes in C (usually the nodes with the lowest upper bound)
• And add them to B.
• Set C = ∅.
• Stopping condition:
• If the nodes in B are leaf (they hold a complete sequence), select the node with the lowest total cost as the best sequence found and stop.
• Otherwise, go to step 2.

Performance

• Priority evaluation functions are computationally cheap , but are potentially inaccurate & may result in discarding good nodes
• total cost evaluation functions on the other hand are more accurate but require a much higher computational effort

Filtered Beam Search

• it uses both priority & total cost evaluations in a two-stage approach
• computationally inexpensive filtering procedure is first applied in order to select the best α children of each beam node for a more accurate evaluation.
• α is the so-called filter width
• the selected nodes are then accurately evaluated using total cost function and the best β nodes are retained for further branching

Filtered Beam Search(contd.)

Let B = Beam Width and C = the set of offspring nodes

n0 be the parent or root node.

• Initialization:
• Set C = ∅.
• Set B = {n0 }
• For each node in B:
• Branch the node generating the corresponding children.
• Add to C the child nodes that are not eliminated by the filtering procedure.
• Set B = ∅. For all nodes in C:
• Perform a detailed evaluation for that node (usually by calculating an upper bound on the optimal solution value of that node)
• Select the min {β, |C|} best nodes in C (usually the nodes with the lowest upper bound) and add them to B.
• Set C = ∅.

Filtered Beam Search(contd.)

• Set B = ∅. For all nodes in C:
• Perform a detailed evaluation for that node (usually by calculating an upper bound on the optimal solution value of that node)
• Select the min {β, |C|} best nodes in C (usually the nodes with the lowest upper bound) and add them to B.
• Set C = ∅.
• Stopping condition:
• If the nodes in B are leaf (they hold a complete sequence), select the node with the lowest total cost as the best sequence found and stop.
• Otherwise, go to step 2.