Re:I am a great programmer, but horrible algorithmist
by nostrademons on Friday February 10, 2012 @02:40PM
(#3577180)
Many graph search algorithms can be expressed as a generic graph search algorithm where you have a "white set" of unvisited nodes, a "black set" of visited nodes, and a "grey set" of nodes that you've encountered but have yet to visit. The structure of the grey set determines the algorithm:
Queue = BFS
Stack = DFS
Priority queue by distance from start = Dijkstra's algorithm
Priority queue by distance + heuristic = A*
Bounded priority queue by heuristic = Beam search
Priority queue by connecting edge weights = Prim's algorithm
Pointer reversal = Mark & sweep garbage collector
Check on whether it points into from-space = Copying garbage collector.
Re:I am a great programmer, but horrible algorithmist
by justinhj on Friday February 10, 2012 @12:48PM
(#3576678)
Norvig's practical ai programming has a great chapter on search which also shows how similarly different algorithms can be expressed if you have the right abstraction
Re:I am a great programmer, but horrible algorithmist
by irahul on Friday February 10, 2012 @01:02PM
(#3576744)
In case someone runs into this comment and is interested in checking out the book, the book is called AIMA(Artificial Intelligence: A modern approach), and here is the relevant code.
http://aima-python.googlecode.com/svn/trunk/search.py
It's a long file though.
Re:I am a great programmer, but horrible algorithmist
by abecedarius on Friday February 10, 2012 @02:43PM
(#3577192)
Also, justinh meant this other code instead: http://norvig.com/paip/search.lisp
(from Norvig's other book).
Re:I am a great programmer, but horrible algorithmist
by irahul on Friday February 10, 2012 @03:47PM
(#3577411)
Oh. I should have guessed "practical ai programming" was actually PAIP(Paradigms...). I haven't read PAIP, but have read AIMA, and the topic under discussion occurs in AIMA; so I assumed OP meant AIMA.
Re:I am a great programmer, but horrible algorithmist
by abecedarius on Friday February 10, 2012 @04:18PM
(#3577512)
Perfectly reasonable! The treatment is similar but less formal/complete in PAIP.
Re:I am a great programmer, but horrible algorithmist
by justinhj on Friday February 10, 2012 @04:47PM
(#3577614)
My bad for getting the name of the book wrong. I thought of it as PAIP for so long I forget what the actual name is :) Great book though, even for those not especially interested in AI or Lisp
Re:I am a great programmer, but horrible algorithmist
by abecedarius on Friday February 10, 2012 @07:14PM
(#3578092)
I agree, and relevantly to this post it's a deep book on programming where algorithms and algorithm design do appear but aren't really central. They're an essential part of the toolbox but not the focus.
Re:I am a great programmer, but horrible algorithmist
by abecedarius on Friday February 10, 2012 @02:41PM
(#3577184)
When I overhauled that code for the third edition, I messed up the A* search. I don't remember what the bug was offhand -- just saying, the OP is not the only one who has trouble sometimes.
Re:I am a great programmer, but horrible algorithmist
by irahul on Friday February 10, 2012 @12:58PM
(#3576728)
> DFS and BFS can be expressed by a single algorithm that differs only in the behavior of the "queue."
Correct me if I am wrong, but the naive non-recursive DFS and BFS differ only in the implementation of queue.
Re:I am a great programmer, but horrible algorithmist
by haberman on Friday February 10, 2012 @02:57PM
(#3577249)
Isn't that what I said?
This formulation of DFS (which tracks a stack of nodes to visit) is less efficient than one that tracks a stack of iterators, because the size of your stack is O(vertices) instead of O(graph depth). On the other hand, it's simpler in some ways, so I can see why it would be preferable in some situations.