Lab 2 2014
From 6.034 Wiki
(Difference between revisions)
(fixed minor typos etc) |
|||
| Line 2: | Line 2: | ||
| - | This problem set will be due on | + | This problem set will be due on Friday, September 30, at 11:59pm. |
| Line 17: | Line 17: | ||
This section is an explanation of the system you'll be working with. There aren't any problems to solve. Read it carefully anyway. | This section is an explanation of the system you'll be working with. There aren't any problems to solve. Read it carefully anyway. | ||
| - | We've learned a lot about different types of search in lecture the last | + | We've learned a lot about different types of search in lecture the last week. This problem set will involve implementing several search techniques. For each type of search you are asked to write, you will get a graph (with a list of nodes and a list of edges and a heuristic), a start node, and a goal node. |
| - | A graph is a class, defined in <tt>search.py</tt> that has lists <tt>.nodes</tt> and <tt>.edges</tt> and a dictionary <tt>.heuristic</tt>. Nodes are just string names, but edges are dictionaries that contain each edge's <tt>"NAME"</tt>, <tt>"LENGTH"</tt>, and two endpoints, specified as <tt>"NODE1"</tt> and <tt>"NODE2"</tt>. | + | A graph is a class, defined in <tt>search.py</tt>, that has lists <tt>.nodes</tt> and <tt>.edges</tt> and a dictionary <tt>.heuristic</tt>. Nodes are just string names, but edges are dictionaries that contain each edge's <tt>"NAME"</tt>, <tt>"LENGTH"</tt>, and two endpoints, specified as <tt>"NODE1"</tt> and <tt>"NODE2"</tt>. |
The heuristic is a dictionary, for each possible goal node, mapping each possible start node to a heuristic value. | The heuristic is a dictionary, for each possible goal node, mapping each possible start node to a heuristic value. | ||
| Line 66: | Line 66: | ||
* nodes that have already been extended (if an extended-nodes set is being used.) | * nodes that have already been extended (if an extended-nodes set is being used.) | ||
| - | As an example, if node ''A'' is connected to nodes ''S'', ''B'', and ''C'', then the path ['S', 'A'] is extended to the new paths ['S', 'A', 'B'] and ['S', 'A', 'C']. | + | As an example, if node ''A'' is connected to nodes ''S'', ''B'', and ''C'', then the path ['S', 'A'] is extended to the new paths ['S', 'A', 'B'] and ['S', 'A', 'C'] (but not ['S', 'A', 'S']). |
The paths you create should be new objects. If you try to extend a path by ''modifying'' (or "mutating") the existing path, for example by using list <tt>.append()</tt>, you will probably find yourself in a world of hurt. | The paths you create should be new objects. If you try to extend a path by ''modifying'' (or "mutating") the existing path, for example by using list <tt>.append()</tt>, you will probably find yourself in a world of hurt. | ||
| Line 129: | Line 129: | ||
=== Beam Search === | === Beam Search === | ||
| - | 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 <b>k</b> paths of length <b>n</b>; <b>k</b> 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 <b>k</b> paths of length <b>n</b>; <b>k</b> is also known as the <b>beam width</b>, and <b>n</b> corresponds 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. |
| - | also known as the <b>beam width</b> | + | |
You may want to use an array or dictionary to keep track of paths of different lengths. | You may want to use an array or dictionary to keep track of paths of different lengths. | ||
| Line 177: | Line 176: | ||
== Graph Heuristics == | == Graph Heuristics == | ||
| - | A heuristic value gives an approximation from a node to a goal. You've learned that in order for the heuristic to be admissible, the heuristic value for every node in a graph must be less than the distance of the shortest path from the goal to that node. In order for a heuristic to be consistent, for each edge in the graph, the edge length must be greater than or equal to the absolute value of the difference between the two heuristic values of its nodes. | + | A heuristic value gives an approximation from a node to a goal. You've learned that in order for the heuristic to be admissible, the heuristic value for every node in a graph must be less than or equal to the distance of the shortest path from the goal to that node. In order for a heuristic to be consistent, for each edge in the graph, the edge length must be greater than or equal to the absolute value of the difference between the two heuristic values of its nodes. |
In lecture and tutorials, you've seen examples of graphs that have admissible heuristics that were not consistent. Have you seen graphs with consistent heuristics that were not admissible? Why is this so? For this part, complete the following functions, which return True iff the heuristics for the given goal are admissible or consistent, respectively, and False otherwise: | In lecture and tutorials, you've seen examples of graphs that have admissible heuristics that were not consistent. Have you seen graphs with consistent heuristics that were not admissible? Why is this so? For this part, complete the following functions, which return True iff the heuristics for the given goal are admissible or consistent, respectively, and False otherwise: | ||
