Question

Other Searches. For each question, answer the prompt and provide at least one full sentence of reasoning and justification. More than one sentence may be necessary.

Q1) In what situation(s) is Breadth First Search identical to Uniform Cost Search?

Answer 1

BFS : Best First Search is an informed search algorithm. It uses a heuristic function for deciding the expanding node. The function used in BFS is of the type f(n)=g(n)+h(n)f(n)=g(n)+h(n), where, h(n)h(n) is the heuristic function and g(n)g(n) is the actual cost from starting node to node n.

UCS : Uniform Cost Search is an uninformed search algorithm. It cannot deal with a heuristic function. It expands the least cost node i.e. node with the lowest g(n).g(n). So, the function that UCS uses can be represented as f(n)=g(n).

The special case when breadth first search is identical to uniform cost search,

When all step costs are equal (and let’s assume equal to 1), g(n) is just a multiple of depth n. Thus, breadth-first search and uniform-cost search would behave the same in this case f(n) = g(n) = 1*(depth of n).

------------------------------------------------Please Upvote----------------------------------------------------------------