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.

9 questions
Filter by
Sorted by
Tagged with
300 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{...
• 123
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 ...
• 39.1k
1k 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 ...
• 361
3k 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?
4k 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 ...
• 321
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 ...
• 165
12k 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?
• 323
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?
• 566