Introduction to the A* Algorithm (2014) • Hacker News Board

Re: Introduction to the A* Algorithm (2014)

#81

Post by JohnKemeny » Wed, Jun 18, 2025, 8:55 PM UTC

salamanderman wrote: post #63

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…

Breadth-first is a queue. Depth-first is a stack. A* is a priority queue.

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.

Re: Introduction to the A* Algorithm (2014)

#82

Post by JohnKemeny » Wed, Jun 18, 2025, 8:58 PM UTC

kriro wrote: post #80

Best introduction to A* in my opinion is travelling in Romania :) AI a Modern Approach.

I always use A* when going to Bucharest.

Re: Introduction to the A* Algorithm (2014)

#83

Post by pantulis » Wed, Jun 18, 2025, 8:58 PM UTC

upghost wrote: post #14

Interesting that this used to be called "AI". I'm still trying to figure out what to call the umbrella field of Artificial Intelligence now that "AI" has come to mean the genAI subset of DL which is a subset of ML which is a subset of what used to be called "AI".

> Interesting that this used to be called "AI".

I remember learning about A* in the AI lab at the University. Now these things sound trivial and we take them for granted. The joys of becoming old.

Re: Introduction to the A* Algorithm (2014)

#84

Post by lukeyoo » Wed, Jun 18, 2025, 9:09 PM UTC

Relavants of mine

- https://lukeyoo.fyi/recap/2025/5/a-star

- https://github.com/micttyoid/quantized-pathfinding

Re: Introduction to the A* Algorithm (2014)

#85

Post by awesome_dude » Wed, Jun 18, 2025, 9:15 PM UTC

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…

Which algorithm should I apply:

I have no information other than the fact that my agent has a decision to make (left or right).

- DFS or BFS

I have some information about the cost of the decision.

- UCS or Djikstra's algorithm

I have some idea of the cost of the decision, and a rough idea which direction the goal is in.

- A star

As well as knowing the cost, and a rough idea of the direction, I also know that I have a uniform cost grid.

- Jump point search

Re: Introduction to the A* Algorithm (2014)

#86

Post by nostrademons » Wed, Jun 18, 2025, 9:17 PM UTC

JohnKemeny wrote: post #81

salamanderman wrote: post #63

Earlier quoted context omitted.

Breadth-first is a queue. Depth-first is a stack. A* is a priority queue.

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.

Likewise, you can represent a queue as a priority queue with key = i, where i is an integer monotonically increasing at insertion time. And you can represent a stack as a priority queue where key = -i.

This is the insight behind the decorate-sort-undecorate pattern; it's just heapsort, with a different key function allowing you to represent several different algorithms.

Re: Introduction to the A* Algorithm (2014)

#87

Post by lblume » Wed, Jun 18, 2025, 9:22 PM UTC

Kye wrote: post #77

Not to be confused with Sagittarius A*. https://en.wikipedia.org/wiki/Sagittarius_A *

The star appears to have been cut off from the link, leaving an article about the corresponding radio source, Sagittarius A. This (official Wikipedia) short link leads to the desired article: https://w.wiki/5A7e

Re: Introduction to the A* Algorithm (2014)

#88

Post by nostrademons » Wed, Jun 18, 2025, 9:35 PM UTC

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 with heuristic function

Topological sort = priority queue keyed by number of unvisited inbound edges

Copying garbage collector = pointer address

Mark & sweep garbage collector = dirty bit on the object pointed to

Generational garbage collector = multi-level grey set represented by the write barriers between each generation.

Re: Introduction to the A* Algorithm (2014)

#89

Post by thaumasiotes » Wed, Jun 18, 2025, 9:37 PM UTC

JohnKemeny wrote: post #81

salamanderman wrote: post #63

Earlier quoted context omitted.

Breadth-first is a queue. Depth-first is a stack. A* is a priority queue.

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.

Re: Introduction to the A* Algorithm (2014)

#90

Post by Kye » Wed, Jun 18, 2025, 10:14 PM UTC

lblume wrote: post #87

Kye wrote: post #77

Not to be confused with Sagittarius A*. https://en.wikipedia.org/wiki/Sagittarius_A *

The star appears to have been cut off from the link, leaving an article about the corresponding radio source, Sagittarius A. This (official Wikipedia) short link leads to the desired article: https://w.wiki/5A7e

HN escaped the * when I posted. I tried to escape the escape, but it kept adding escapes to my escapes. After a while I conceded defeat and decided folks might enjoy taking the scenic route through disambiguation.

I never got in the habit of using share links, so it's interesting to learn Wikipedia has a URL shortener.