Answers.Body: <p>You could show them the results with a given heuristics function, that has a single parameter which impacts how the heuristic function affects the cost estimate. </p>
  
  <p>As an example, </p>
  
  <pre><code>estimate = D * (horizontal_distance + vertical_distance)
  </code></pre>
  
  <p>where the <code>distance</code> is the one between the current node and the goal (quite straight forward in a maze, albeit not such a good choice for the heuristic)</p>
  
  <p>Here, <code>D</code> is a parameter that will, in essence, decide how influential the heuristic is. </p>
  
  <p>You can use this example with a number of different <code>D</code> values and show the student how the chosen path changes (if it finds it at all) as you change <code>D</code>. This will show the students how the heuristic changes the decision making. </p>
  
  <p>Another heuristic you could use is one that counts the number of steps, in the direction of the goal, that can be taken before the solver hits a wall of the maze (the usefulness depends on how dense the maze is).</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-05-30T16:45:39.783Z
Answers.Text: Upvoted. This was a very helpful answer to me.
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-05-30T15:23:55.290Z
Answers.LastActivityDate: 2017-05-30T15:23:55.290Z
Answers.UserDisplayName: ItamarG3
Answers.Body: <p>I usually teach <a href="https://algorithmicthoughts.wordpress.com/2012/12/15/artificial-intelligence-uniform-cost-searchucs/" rel="noreferrer">Uniform Cost Search</a> (UCS) before A*, since it is basicaly A* without the heuristic (and it reduces to BFS when all costs = 1, so it is pretty straightforward to explain). Then I teach A* and show them animated examples of the explored nodes in comparison to UCS (<a href="http://www.redblobgames.com/pathfinding/a-star/introduction.html" rel="noreferrer">here</a> you can find excellent interactive examples). </p>
  
  <p>In this step, one analogy I like to use is about mazes: Imagine yourself inside a maze from which you must find the exit, but you have no idea where it is. This is UCS. Now imagine there is no ceiling in the maze (like the Harry Potter one), and there is a tower in the exit which can be seen from anywhere in the maze. Now you can make more informed decisions in your search, biasing choices in that direction. This is A*.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-07-01T13:43:00.413Z
Answers.Text: I really like your "distance to tower" concept to illustrate a (straight line distance) heuristic
Answers.UserDisplayName: Adam Williams
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-04T06:10:00.540Z
Answers.LastActivityDate: 2017-06-04T06:10:00.540Z
Answers.UserDisplayName: rcpinto
Body: <p>I created a group lab where one student makes a random maze generator, one student makes a corresponding maze solver, and the last student calls the methods created by both students and creates an animated maze walker.  Currently, the students are told to use <strong>Prim's algorithm</strong> for maze generation, though I am open to any of these other algorithms as well:</p>
  
  <ul>
  <li>Kruskal's</li>
  <li>Recursive Backtracker</li>
  <li>Aldous-Broder</li>
  <li>Growing Tree</li>
  <li>Hunt-and-Kill</li>
  <li>Wilson's</li>
  <li>Eller's</li>
  <li>Cellular Automaton</li>
  <li>Recursive Division</li>
  <li>Sidewinder</li>
  <li>Binary Tree</li>
  </ul>
  
  <p>In practice, about 10% of students use other algorithms besides Prim's.</p>
  
  <p>For the maze solver, I teach my students about <strong>breadth-first search</strong>, and for next year, I would like to expand this a bit and teach them about <strong>depth-first search</strong> as well.  However, I would also like to give them a real shot at <strong>A*</strong>, since it is a much, much better algorithm.</p>
  
  <p>What I am looking for is how to get them to see the difficult piece of <strong>A*</strong>: how a heuristic concretely <em>fits</em> within the algorithm and gets us to a solution.  My target is for 25% of the students to choose to use A* next year.  I don't care which heuristics we use, but I would like them to see something that they can understand quite concretely (as I believe firmly in engendering concrete understandings before abstract understandings) and I would like them to understand the difference between an admissible and an inadmissible heuristic.</p>
  
  <p>For context, I do this all during my <strong>AP Computer Science class</strong>, so it is in <strong>Java</strong>, however the question is really about <strong>A*</strong>, so I am not adding those tags in.</p>
  
  <h1>Edit</h1>
  
  <p>Mike Zamansky posted a response to this question <a href="http://cestlaz.github.io/posts/a-star-is-born" rel="nofollow noreferrer">on his incredible blog</a> and it knocked my socks off! I'm going to integrate a lot of his approach into my own next year.  I would accept his answer, but it's not on this site, so the best I can do from here is link to it.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-23T17:20:43.497Z
Comments.Text: I'm curious how you decided to do it in the end.
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-23T17:26:33.040Z
Comments.Text: It's summer, so I haven't reworked the lab yet.  This lab is usually given some time around January, so there's plenty of time :)
Comments.UserDisplayName: Ben I.
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-07-23T17:27:50.040Z
Comments.Text: Oh, well that makes sense. Still, I'd like to see it (if you'll let me :P) after you've reworked it.
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-05-30T14:43:35.300Z
Comments.Text: Not sure I understand what you mean by "concretely fits within the algorithm"...
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-05-30T14:57:23.413Z
Comments.Text: Good point, that was rather unclear.  I edited the prompt - better now?
Comments.UserDisplayName: Ben I.
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-05-30T15:10:53.047Z
Comments.Text: So if I understand correctly, you want to show them how the heuristics play their part?
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-05-30T15:12:11.390Z
Comments.Text: I want them to see where the heuristic fits into the larger decision making process, and how the choice of heuristic impacts the overall performance.
Comments.UserDisplayName: Ben I.
Tags: <lesson-ideas><algorithms>
Title: Introducing A* Search Algorithm
ThreadText: # Introducing A* Search Algorithm
  
  (Asked by: username_0 on 2017-05-30)
  
  I created a group lab where one student makes a random maze generator, one student makes a corresponding maze solver, and the last student calls the methods created by both students and creates an animated maze walker. Currently, the students are told to use **Prim's algorithm** for maze generation, though I am open to any of these other algorithms as well:
  
  * Kruskal's
  * Recursive Backtracker
  * Aldous-Broder
  * Growing Tree
  * Hunt-and-Kill
  * Wilson's
  * Eller's
  * Cellular Automaton
  * Recursive Division
  * Sidewinder
  * Binary Tree
  
  In practice, about 10% of students use other algorithms besides Prim's.
  
  For the maze solver, I teach my students about **breadth-first search**, and for next year, I would like to expand this a bit and teach them about **depth-first search** as well. However, I would also like to give them a real shot at **A\***, since it is a much, much better algorithm.
  
  What I am looking for is how to get them to see the difficult piece of **A\***: how a heuristic concretely *fits* within the algorithm and gets us to a solution. My target is for 25% of the students to choose to use A\* next year. I don't care which heuristics we use, but I would like them to see something that they can understand quite concretely (as I believe firmly in engendering concrete understandings before abstract understandings) and I would like them to understand the difference between an admissible and an inadmissible heuristic.
  
  For context, I do this all during my **AP Computer Science class**, so it is in **Java**, however the question is really about **A\***, so I am not adding those tags in.
  
  # Edit
  
  Mike Zamansky posted a response to this question [on his incredible blog](http://cestlaz.github.io/posts/a-star-is-born) and it knocked my socks off! I'm going to integrate a lot of his approach into my own next year. I would accept his answer, but it's not on this site, so the best I can do from here is link to it.
  
  **Tags:** lesson-ideas, algorithms
  
  > **Comments:**
  > **username_1**: Not sure I understand what you mean by "concretely fits within the algorithm"...  
  > **username_0**: Good point, that was rather unclear.  I edited the prompt - better now?  
  > **username_1**: So if I understand correctly, you want to show them how the heuristics play their part?  
  > **username_0**: I want them to see where the heuristic fits into the larger decision making process, and how the choice of heuristic impacts the overall performance.  
  > **username_1**: I'm curious how you decided to do it in the end.  
  > **username_0**: It's summer, so I haven't reworked the lab yet.  This lab is usually given some time around January, so there's plenty of time :)  
  > **username_1**: Oh, well that makes sense. Still, I'd like to see it (if you'll let me :P) after you've reworked it.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2017-06-04. Score: 7
  
  I usually teach [Uniform Cost Search](https://algorithmicthoughts.wordpress.com/2012/12/15/artificial-intelligence-uniform-cost-searchucs/) (UCS) before A\*, since it is basicaly A\* without the heuristic (and it reduces to BFS when all costs = 1, so it is pretty straightforward to explain). Then I teach A\* and show them animated examples of the explored nodes in comparison to UCS ([here](http://www.redblobgames.com/pathfinding/a-star/introduction.html) you can find excellent interactive examples).
  
  In this step, one analogy I like to use is about mazes: Imagine yourself inside a maze from which you must find the exit, but you have no idea where it is. This is UCS. Now imagine there is no ceiling in the maze (like the Harry Potter one), and there is a tower in the exit which can be seen from anywhere in the maze. Now you can make more informed decisions in your search, biasing choices in that direction. This is A\*.
  
  > **Comments:**
  > **username_3**: I really like your "distance to tower" concept to illustrate a (straight line distance) heuristic  
  
  ---
  
  ### Answer by username_1 on 2017-05-30. Score: 5
  
  You could show them the results with a given heuristics function, that has a single parameter which impacts how the heuristic function affects the cost estimate.
  
  As an example,
  
  ```
  estimate = D * (horizontal_distance + vertical_distance)
  
  ```
  
  where the `distance` is the one between the current node and the goal (quite straight forward in a maze, albeit not such a good choice for the heuristic)
  
  Here, `D` is a parameter that will, in essence, decide how influential the heuristic is.
  
  You can use this example with a number of different `D` values and show the student how the chosen path changes (if it finds it at all) as you change `D`. This will show the students how the heuristic changes the decision making.
  
  Another heuristic you could use is one that counts the number of steps, in the direction of the goal, that can be taken before the solver hits a wall of the maze (the usefulness depends on how dense the maze is).
  
  > **Comments:**
  > **username_0**: Upvoted. This was a very helpful answer to me.  
  
  ---
  
  