Lab 2 2014
From 6.034 Wiki
(Difference between revisions)
| Line 106: | Line 106: | ||
=== Hill Climbing === | === Hill Climbing === | ||
| - | Hill climbing is very similar to depth first search. There is only a slight modification to the ordering of paths that are added to the | + | Hill climbing is very similar to depth first search. There is only a slight modification to the ordering of paths that are added to the agenda. For this part, implement the following function: |
<pre> | <pre> | ||
| Line 115: | Line 115: | ||
The hill-climbing procedure you define here ''should'' use backtracking, for consistency with the other methods, even though hill-climbing typically is not implemented with backtracking. | The hill-climbing procedure you define here ''should'' use backtracking, for consistency with the other methods, even though hill-climbing typically is not implemented with backtracking. | ||
| + | |||
| + | === Beam Search === | ||
| + | |||
| + | Beam search is very similar to breadth first search. There is only a slight modification to the ordering of paths that are added to 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 elements at each level are in your agenda. | ||
| + | |||
| + | For this part, implement the following function: | ||
| + | |||
| + | <pre> | ||
| + | |||
| + | def beam_search(graph, start, goal, beam_size): | ||
| + | |||
| + | </pre> | ||
== Optimal Search == | == Optimal Search == | ||
Revision as of 23:41, 21 September 2010
This problem set will be due on Friday, October 8th.
