Skip to main content

Questions tagged [uniform-cost-search]

For questions related to the uniform-cost search (UCS) algorithm, also known as the cheapest-first search, which is the uninformative version of the A* algorithm. The UCS is very similar to Dijkstra's algorithm (originally introduced by Edsger W. Dijkstra in 1956 and published in the 1959 paper "A note on two problems in connexion with graphs"), which originated UCS, according to Norvig and Russell's book.

Filter by
Sorted by
Tagged with
2 votes
2 answers
571 views

Why is there a 1 in complexity formula of uniform-cost search?

I am reading the book titled Artificial Intelligence: A Modern Approach 4th ed by Stuart Russell and Peter Norvig. According to the book, the complexity of uniform-cost search is as $$ O(b^{1+\lfloor{...
user153245's user avatar
2 votes
2 answers
2k views

What is the difference between the uniform-cost search and Dijkstra's algorithm?

Every computer science student (including myself, when I was doing my bachelor's in CS) probably encountered the famous single-source shortest path Dijkstra's algorithm (DA). If you also took an ...
nbro's user avatar
  • 40.9k
4 votes
1 answer
2k views

Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?

I was reading Artificial Intelligence: A Modern Approach 3rd Edition, and I have reached to the UCS algorithm. I was reading the proof that UCS is complete. The book state that: Completeness is ...
Kais Hasan's user avatar
3 votes
2 answers
4k views

If uniform cost search is used for bidirectional search, is it guaranteed the solution is optimal?

If uniform cost search is used for both the forward and backward search in bidirectional search, is it guaranteed the solution is optimal?
user avatar
3 votes
1 answer
5k views

Understanding the pseudocode of uniform-cost search from the book "Artificial Intelligence: A Modern Approach"

On page 84 of Russell & Norvig's book "Artificial Intelligence: A Modern Approach Book" (3rd edition), the pseudocode for uniform cost search is given. I provided a screenshot of it here for your ...
anonuser01's user avatar
3 votes
1 answer
1k views

A* and uniform-cost search are apparently incomplete

Consider the following diagram of a graph representing a search space. If we start at $B$ and try to reach goal state $E$, the lowest-cost first search (LCFS) (aka uniform-cost search) algorithm ...
KGhatak's user avatar
  • 165
5 votes
1 answer
13k views

How do I show that uniform-cost search is a special case of A*?

How do I show that uniform-cost search is a special case of A*? How do I prove this?
dua fatima's user avatar
5 votes
1 answer
5k views

What are the differences between uniform-cost search and greedy best-first search?

What are the differences between the uniform-cost search (UCS) and greedy best-first search (GBFS) algorithms? How would you convert a UCS into a GBFS?
Abbas Ali's user avatar
  • 566
6 votes
1 answer
8k views

How does the uniform-cost search algorithm work?

What is the uniform-cost search (UCS) algorithm? How does it work? I would appreciate seeing a graphical execution of the algorithm. How does the frontier evolve in the case of UCS?
Iram Shah's user avatar
  • 315