I had a beer with the awfully clever Sean Scarff who was a games programmer in the 80s. He mentioned that he and his peers were writing a lot of algorithms while ignorant of the academic work in the field. In particular, when they were solving mazes, they imagined a smell emanating from the end of the maze and the closer they were the stronger the scent. This is breadth-first searching.
"Breath-first search and depth-first search both visit all the nodes in a graph, but their manner of doing so is dramatically different... Breadth-first search amounts to an army of searchers fanning out to cover the territory; depth-first search search corresponds to a single searcher probing unknown territory as deeply as possible, retreating only when hitting dead ends." - Algorithms in C++, Sedgewick.
Because of this, breadth-first search is easier to parallelize but may take up more memory (see other pros and cons here)
Sean is involved in computer networks these days where the algorithm still applies. Funny how algorithms do that.
Finally, a click here for cartoon that's both amusing and entertaining.
"Breath-first search and depth-first search both visit all the nodes in a graph, but their manner of doing so is dramatically different... Breadth-first search amounts to an army of searchers fanning out to cover the territory; depth-first search search corresponds to a single searcher probing unknown territory as deeply as possible, retreating only when hitting dead ends." - Algorithms in C++, Sedgewick.
Because of this, breadth-first search is easier to parallelize but may take up more memory (see other pros and cons here)
Sean is involved in computer networks these days where the algorithm still applies. Funny how algorithms do that.
Finally, a click here for cartoon that's both amusing and entertaining.
No comments:
Post a Comment