Lab 2 2014
From 6.034 Wiki
(Difference between revisions)
(fixed minor typos etc) |
m (consistent-ized "agenda"/"queue" terminology) |
||
| Line 57: | Line 57: | ||
=== The Agenda === | === The Agenda === | ||
| - | Different search techniques explore nodes in different orders, and we will keep track of the nodes remaining to explore in a list we will call the '''agenda'''. Some techniques will add paths to the top of the agenda, treating it like a stack, while others will add to the back of the agenda, treating it like a queue. Some agendas are organized by heuristic value | + | Different search techniques explore nodes in different orders, and we will keep track of the nodes remaining to explore in a list we will call the '''agenda''' (in class we called this the '''queue'''). Some techniques will add paths to the top of the agenda, treating it like a stack, while others will add to the back of the agenda, treating it like a queue. Some agendas are organized by heuristic value, others are ordered by path distance, and others by depth in the search tree. Your job will be to show your knowledge of search techniques by implementing different types of search and making slight modifications to how the agenda is accessed and updated. |
| Line 166: | Line 166: | ||
=== A* === | === A* === | ||
| - | You're almost there! You've used heuristic estimates to speed up search and edge lengths to compute optimal paths. Let's combine the two ideas now to get the A* search method. In A*, the path with the least (heuristic estimate + path length) is taken from the | + | You're almost there! You've used heuristic estimates to speed up search and edge lengths to compute optimal paths. Let's combine the two ideas now to get the A* search method. In A*, the path with the least (heuristic estimate + path length) is taken from the agenda to extend. A* always uses an extended list -- make sure to use one. |
<pre> | <pre> | ||
