Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Introduction to the A* Algorithm (2014)

redblobgames.com

Post reply on HN
Print view View original

91–100 of 111 posts

Re: Introduction to the A* Algorithm (2014)

#91

Post by a-dub »

nostrademons wrote: post #88
apnorton wrote: post #33

The article doesn't explicitly state it in this manner in one concise place, but the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue: Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue) Di…

Another way I like to think about it is that every graph traversal can be represented as a white set of unknown nodes, a grey set of known but unvisited nodes, and a black set of visited nodes. The data structure used to represent the grey set defines the algorithm: DFS = queue BFS = stack Dijstra's = priority queue keyed by edge weight A* = priority queue with heuristic function Beam search = bounded priority queue…

A* = priority queue with heuristic function _with specific properties_ ... in particular it must be an "admissible" hueristic that never overestimates the true value.

Re: Introduction to the A* Algorithm (2014)

#92

Post by djmips »

apnorton wrote: post #33

The article doesn't explicitly state it in this manner in one concise place, but the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue: Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue) Di…

Any other tips for competitive coding ie a book or source of wisdom in a similar vein?

Re: Introduction to the A* Algorithm (2014)

#93

Post by kragen »

a-dub wrote: post #91
nostrademons wrote: post #88

Earlier quoted context omitted.

Another way I like to think about it is that every graph traversal can be represented as a white set of unknown nodes, a grey set of known but unvisited nodes, and a black set of visited nodes. The data structure used to represent the grey set defines the algorithm: DFS = queue BFS = stack Dijstra's = priority queue keyed by edge weight A* = priority queue with heuristic function Beam search = bounded priority queue…

A* = priority queue with heuristic function _with specific properties_ ... in particular it must be an "admissible" hueristic that never overestimates the true value.

It'll still find a path with an inadmissible heuristic, as the page explains. It's just not guaranteed to be the shortest path in that case. This is commonly done.

Re: Introduction to the A* Algorithm (2014)

#94

Post by kragen »

thaumasiotes wrote: post #89
JohnKemeny wrote: post #81

Earlier quoted context omitted.

OP's point is that · BFS is priority queue with key h(n) + g(n) , where h(n) = 0 , g(n) = #edges · Dijkstra's is priority queue with key h(n) + g(n) , where h(n) = 0 , g(n) = sum over edges · A* is priority queue with key h(n) + g(n) , where h(n) = heuristic(n) , g(n) = sum over edges It's cute.

> OP's point is that > BFS is priority queue with key h(n) + g(n), where h(n) = 0, g(n) = #edges He doesn't say that, and it isn't true.

I think it is true, although "#edges" needs to be understood as "the number of the edges in the path from the starting point to the node", which was not one of my first three candidate interpretations.

Re: Introduction to the A* Algorithm (2014)

#95

Post by gradstudent »

SnowflakeOnIce wrote: post #62
deadbabe wrote: post #54

A* is simple enough, but how do you handle pathfinding when the environment isn’t known to the entity?

https://en.m.wikipedia.org/wiki/Simultaneous_localization_an...

SLAM is for mapping. For planning (and execution) in unknown environments, probably something like D* Lite.

Re: Introduction to the A* Algorithm (2014)

#96

Post by gradstudent »

ViscountPenguin wrote: post #60
deadbabe wrote: post #54

A* is simple enough, but how do you handle pathfinding when the environment isn’t known to the entity?

Iirc, the best approaches for this nowadays are machine learning based. Otherwise, you probably want to do an exploration step first, and bake in the environment.

ML methods are poor pathfinders. I'm unaware of any pathfinding problem where SOTA is not dominated by state-space search.

Re: Introduction to the A* Algorithm (2014)

#97

Post by amy_petrik »

djmips wrote: post #92
apnorton wrote: post #33

The article doesn't explicitly state it in this manner in one concise place, but the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue: Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue) Di…

Any other tips for competitive coding ie a book or source of wisdom in a similar vein?

leetcode will strengthen the youngblood programmer for competitive matters such as competitions or interviews

Re: Introduction to the A* Algorithm (2014)

#98

Post by anitil »

nostrademons wrote: post #88
apnorton wrote: post #33

The article doesn't explicitly state it in this manner in one concise place, but the way I would always think about A* from a "practical/easy-to-remember" perspective back when I was doing competitive programming is that they're all the same algorithm, but with different priorities on the priority queue: Breadth-first Search: Priority is order of discovery of edges (that is, no priority queue/just a regular queue) Di…

Another way I like to think about it is that every graph traversal can be represented as a white set of unknown nodes, a grey set of known but unvisited nodes, and a black set of visited nodes. The data structure used to represent the grey set defines the algorithm: DFS = queue BFS = stack Dijstra's = priority queue keyed by edge weight A* = priority queue with heuristic function Beam search = bounded priority queue…

This is very insightful and a handy mental model I'll be using thanks. A small nit is that I think you have DFS and BFS swapped?

Re: Introduction to the A* Algorithm (2014)

#99

Post by kccqzy »

amy_petrik wrote: post #97
djmips wrote: post #92

Earlier quoted context omitted.

Any other tips for competitive coding ie a book or source of wisdom in a similar vein?

leetcode will strengthen the youngblood programmer for competitive matters such as competitions or interviews

Codeforces is so much better. Better community and better questions.

Re: Introduction to the A* Algorithm (2014)

#100

Post by nostrademons »

anitil wrote: post #98
nostrademons wrote: post #88

Earlier quoted context omitted.

Another way I like to think about it is that every graph traversal can be represented as a white set of unknown nodes, a grey set of known but unvisited nodes, and a black set of visited nodes. The data structure used to represent the grey set defines the algorithm: DFS = queue BFS = stack Dijstra's = priority queue keyed by edge weight A* = priority queue with heuristic function Beam search = bounded priority queue…

This is very insightful and a handy mental model I'll be using thanks. A small nit is that I think you have DFS and BFS swapped?

Oh yeah, I do. Too late to edit the post now.
Post reply on HN