In what sense is “Uniform-cost search” uniform?
The article "Artificial Intelligence - Uniform Cost Search (UCS)" by Siddharth Agrawal (http://algorithmicthoughts.wordpress.com/2012/12/15/artificial-intelligence-uniform-cost-searchucs/) claims that the reason why it is called uniform cost search is because at any given point in time, the priority queue is filled with path costs that are mostly uniform. From the article:
"The elements in the priority queue have almost the same costs at a given time, and thus the name Uniform Cost Search. It may seem as if the elements don’t have almost the same costs ... but when applied on a much larger graph it is certainly so."
This may be a feasible explanation. The costs in the priority queue for DFS will range from nothing all the way to the cost of reaching the deepest node. If we consider BFS on a weighted graph, it is certainly possible to have paths of greatly varying costs, even though we only have two levels of depth OPEN at a time.
Cost and heuristic are two separate measurements (a heuristic is supposed to be an estimate of the cost), so it doesn't seem that it would make sense to call it "uniform cost" if the word uniform was referring to the heuristic.