3 ms·

A fantastic site. When I originally took over teaching Intro to AI, I initially relied on the A* search closed/open set pseudocode explanation[1]. However, when

A fantastic site. When I originally took over teaching Intro to AI, I initially relied on the A* search closed/open set pseudocode explanation[1]. However, when it would come time to ask students to implement it, I was constantly finding students absolutely confused by the approach. Once I swapped over to Amit's A* explanation, the number of confused students dropped significantly. Forever thankful for their walkthrough. [1] https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode https://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode

gowld 3y ago
What's the difference between the approaches?
- tsumnia 3y ago
  Amit describes the differences here [2], but briefly: - The Wiki pseduocode uses Set data structures for everything. While these are covered in classes, the up-tree concept isn't as heavily described as other trees - Looking at it now, it looks like the pseudocode is a little more beginner friendly, but "back in mah day" it was not - Although, RedBlob's pseudocode for obtaining neighboring nodes is clearer than "for each neighbor of current" (Wikipedia pseudocode) - RedBlob uses Priority Queues and Maps instead of Sets, which connect better to other AI searches / recommendation algorithms. Higher 'priority' recommendations move to root in PQs while nodes in Sets... don't... they just sort of 'exist' - The Maps make looking up node costs more intuitive than lists (aka "current := the node in openSet having the lowest fScore[] value") [2] https://www.redblobgames.com/pathfinding/a-star/implementation.html#algorithm https://www.redblobgames.com/pathfinding/a-star/implementati...
- amitp 3y ago
  1. I use words for variable names instead of single letters like the textbooks do. I use "priority" instead of "F", "cost_so_far" instead of "G", "heuristic" instead of "H", "cost" instead of "w", "frontier" instead of "OPEN" or "O", "visited" instead of "CLOSED" or "C", "current" instead of "u", "next" or "neighbor" instead of "v". 2. The textbooks use an "open" and "closed" set. But in code, these aren't explicitly stored in set data structures. Instead, they're implicit. The cost_so_far dict(map) contains as keys both the open and closed sets, and the frontier (priority queue) contains the open set. So in my explanation of A* I focus on these data structures (priority queue and dict) instead of the open/closed sets. And when I do talk about the sets, I talk about the combined open and closed sets, calling it "visited" or "reached", because it's the combined set that is actually in the data structures. 3. The textbooks use a priority queue with reprioritization. When you visit a node that has a lower cost than the previously found cost, you go into the priority queue and adjust the cost. In my presentation I don't use reprioritization. Instead, I insert another entry into the priority queue with the lower cost. This makes the priority queue simpler (reprioritization is complicated). And in practice, I think it's faster too.
amitp 3y ago
That's great to hear — thank you!
- tsumnia 3y ago
  No thank you! If you're ever near the NC side of the US let me know, I'll gladly buy you lunch for all the help you've given me.

gowld 3y ago

What's the difference between the approaches?

tsumnia 3y ago
Amit describes the differences here [2], but briefly: - The Wiki pseduocode uses Set data structures for everything. While these are covered in classes, the up-tree concept isn't as heavily described as other trees - Looking at it now, it looks like the pseudocode is a little more beginner friendly, but "back in mah day" it was not - Although, RedBlob's pseudocode for obtaining neighboring nodes is clearer than "for each neighbor of current" (Wikipedia pseudocode) - RedBlob uses Priority Queues and Maps instead of Sets, which connect better to other AI searches / recommendation algorithms. Higher 'priority' recommendations move to root in PQs while nodes in Sets... don't... they just sort of 'exist' - The Maps make looking up node costs more intuitive than lists (aka "current := the node in openSet having the lowest fScore[] value") [2] https://www.redblobgames.com/pathfinding/a-star/implementation.html#algorithm https://www.redblobgames.com/pathfinding/a-star/implementati...
amitp 3y ago
1. I use words for variable names instead of single letters like the textbooks do. I use "priority" instead of "F", "cost_so_far" instead of "G", "heuristic" instead of "H", "cost" instead of "w", "frontier" instead of "OPEN" or "O", "visited" instead of "CLOSED" or "C", "current" instead of "u", "next" or "neighbor" instead of "v". 2. The textbooks use an "open" and "closed" set. But in code, these aren't explicitly stored in set data structures. Instead, they're implicit. The cost_so_far dict(map) contains as keys both the open and closed sets, and the frontier (priority queue) contains the open set. So in my explanation of A* I focus on these data structures (priority queue and dict) instead of the open/closed sets. And when I do talk about the sets, I talk about the combined open and closed sets, calling it "visited" or "reached", because it's the combined set that is actually in the data structures. 3. The textbooks use a priority queue with reprioritization. When you visit a node that has a lower cost than the previously found cost, you go into the priority queue and adjust the cost. In my presentation I don't use reprioritization. Instead, I insert another entry into the priority queue with the lower cost. This makes the priority queue simpler (reprioritization is complicated). And in practice, I think it's faster too.

amitp 3y ago

That's great to hear — thank you!

tsumnia 3y ago
No thank you! If you're ever near the NC side of the US let me know, I'll gladly buy you lunch for all the help you've given me.