# In what sense is “Uniform-cost search” uniform?

The name of Uniform-cost search in computer science is not instinctive since what part of it being "uniform" is not clear to me. Apparently uniformity is not about the cost of each edge - most of the examples handle edges with various costs. Can someone explain? Thank you.

(Hope this question is appropriate here. FAQ page at Theoretical Computer Science - Stack Exchange, a research level CS community, indicates that theoretical CS question can be asked here.)

-
RE cstheory FAQ: Well, ComputerScience.SE has gone beta! You can join and post your question there! –  user2468 Mar 7 '12 at 19:28
@J.D. thanks, I just got a notification too. For this particular question I've already made myself satisfied. –  IsaacS Mar 8 '12 at 1:17

Trying to answer to my own question. Correct me if wrong.

I think I need to think about 2 types of concept in search so-called un-informed and informed search, and (here I'm skipping much explanation about fundamentals though) Uniformed Search (don't get confused) can be considered as "uninformed" version of A* search, i.e. return of heuristic function is equal to zero. This zero informed cost might have us call it as uniformed.

This naming is not really intuitive, because the reason it's called as uninformed is based on the heuristic function's cost, not on the path-cost which is the main comparison criteria when you talk about un-informed search.

-
@templatetypedef That's the OP answering his/her own question! –  user2468 Mar 7 '12 at 19:29
Great question! Possibly the correct answer! Does this mean that uniform cost search is called "uniform" as it has a "uniform heuristic" ? By that notion, all un-informed searches like BFS, DFS, etc are also uniform searches ? Is it correct to say that ? –  Garfield Oct 14 '12 at 19:35

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.

-