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
2
votes
2
answers
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
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 ...
- 39.1k
4
votes
1
answer
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
3
votes
2
answers
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?
user42125
3
votes
1
answer
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
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 ...
- 165
5
votes
1
answer
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
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?
- 566
6
votes
1
answer
7k
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?
- 315