4 ms·

What's the difference between the approaches?

by gowld 3y ago

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.

What's the difference between the approaches?

by gowld 3y ago

What's the difference between the approaches?

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.