Lab 2 2014
From 6.034 Wiki
(Difference between revisions)
Line 116: | Line 116: | ||
=== Beam Search === | === Beam Search === | ||
- | Beam search is very similar to breadth first search. There is | + | Beam search is very similar to breadth first search. There is modification to the ordering of paths in the agenda. The agenda at any time can have up to <tt>k</tt> paths of length <tt>n</tt>; <tt>k</tt> is |
- | also known as the beam width. <tt>n</tt> correspond to the level of the search graph. You will need to sort your paths by the graph heuristic to ensure that only the top k | + | also known as the <b>beam width</b>. <tt>n</tt> correspond to the level of the search graph. You will need to sort your paths by the graph heuristic to ensure that only the top k paths at each level are in your agenda. |
+ | You may want to use an array or dictionary to keep track of paths of different lengths. | ||
For this part, implement the following function: | For this part, implement the following function: |
Revision as of 21:15, 26 September 2010
This problem set will be due on Friday, October 8th.