4. [2+4+4+4]Consider the search space below, where S is the start node and G1 an

Question

4. [2+4+4+4]Consider the search space below, where S is the start node and G1 and G2 satisfy the goal test. Arcs are labeled with the cost of traversing them and the estimated cost to a goal is reported inside nodes (so lower scores are better) G2 GI a) Would it be a good idea to use the Depth-First Search in this example or not? Why? Write the contents of the frontier, putting the path that will be selected as the first element, for four iterations using b) lowest-cost first c) best-first d) A*

Explanation / Answer

If you acknowledge the answer, please upvote it. Otherwise leave a comment, I would be happy to rectify any doubts/errors.

a) DFS would resort to finding out all the paths and backtracking whenever the solution isn't reached. In this directed cyclic graph, it possible to enter into an infinite loop where a cyclic path is followed endlessly.

Thus it is not a good idea to use DFS

b) S -> A -> B -> C

Lowest cost search: chooses the element of the frontier with the lowest path cost. It treats the frontier like a priority queue, ordered by g(n), where g(n) is the path cost to reach to the next node from the current node.

c) S -> B -> G1

Best first search: chooses the element of the frontier with the lowest value of h(n), heuristic function.

d) S -> D -> C -> F -> G2

A*: for each path on the frontier, this search uses an estimate, f(n) = g(n) + h(n), and tries to minimise it

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.