function GRAPH-SEARCH(problem, fringe) closed ? empty set fringe ? INSERT(MAKE-N
ID: 3700381 • Letter: F
Question
function GRAPH-SEARCH(problem, fringe) closed ? empty set fringe ? INSERT(MAKE-NODE(INITIAL-STATE[problem]), fringe) loop if fringe is empty then return failure end if nodeR IF GOAL-TEST(problem,STATE[node]) THEN REMOVE-FRONT(fringe) RETURN node END IF ADD STATE[node] TO closed fringe ? INSERTALL(EXPAND(node, problem), fringe) END LOOP END FUNCTION Circle all that apply: (a) Nodes may be expanded twice. b) The algorithm is not complete. (c) The algorithm could return an incorrect solution (d) None of the above.Explanation / Answer
This algorithm is used for planning and searching. Imagine two players playing tic-tac-toe. After every move of playing an X or an O, the state of the game changes. This state-space of the game, which includes a 9x9 grid in this case, can be represented in the form of a tree or a graph. To figure out the outcome of a game, we perform tree or graph traversal. There are two algorithms for that, tree search and graph search. Each node in a tree/graph represents a game state.The algorithm given in the problem is that of graph search.
Now, graph traversal keeps a track of the nodes that have been visited (or the states that have been seen). So nodes are not expanded twice in graph search but may be visited infinitely many times in tree search.
An algorithm is termed as complete if it always returns a solution, if the solution exists. Otherwise, it returns a failure. Graph search shows completeness. If there is a path between nodes A and B in a graph, then this algorithm will return it.
An algorithm is termed as correct if the solution returned by the algorithm is correct. We can prove by example (DFS, BFS, A*) that the solutions returned by graph search is correct.
Hence, none of the options apply and the answer is option (d) None of the above.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.