10 marks consider the maze shown below where the successors of a cell
(10 marks) Consider the maze shown below, where the successors of a cell are the cells directly to the
east, west, north and south of the cell, except that you are not allowed to pass through the thick wall
indicated by the double line. For example, the successors of cell I are H and N (and not D or J).
Trace the operation of A* search applied to the problem of getting from cell R to cell G. The heuristic
function is just the Manhattan distance, ignoring the existence of the wall. The heuristic values for each
node are summarized for you in the table to the right.
• Draw the search tree, starting from cell R. Beside each node in your tree, indicate the f, g and h scores
for the node (in the format g(n)th(n) = f(n)). Assume that the cost of each move is 1.
• To the side of your search tree, provide a list of the order in which paths are expanded. Show the
contents of the frontier after each node is expanded. To make it easier to keep track of what you are
doing, include both the f value and h value as subscripts when you write a path in your priority queue. For
example, WXY Z11,7 would indicate that WXY Z is a path such that f(WXYZ) = 11 and h(Z) = 7.
•If two or more paths are tied for the lowest f value, give priority to the one with minimum h value. Use
alphabetical order if there is still a tie.
• For this question, you can avoid generating states that have already been expanded.
For example, you should not consider going west from cell I to cell H if you had already expanded cell H in
an earlier step.
• Also, when inserting a path onto the priority queue, if a path to the same state is already on the queue,
just keep the copy with the lower f value.
A B с DE
KIL M N 0
P Q R
What is the solution path returned by the algorithm, and what is its path cost?
*The amount will be in form of wallet points that you can redeem to pay upto 10% of the price for any assignment. **Use of solution provided by us for unfair practice like cheating will result in action from our end which may include permanent termination of the defaulter’s account.Disclaimer:The website contains certain images which are not owned by the company/ website. Such images are used for indicative purposes only and is a third-party content. All credits go to its rightful owner including its copyright owner. It is also clarified that the use of any photograph on the website including the use of any photograph of any educational institute/ university is not intended to suggest any association, relationship, or sponsorship whatsoever between the company and the said educational institute/ university. Any such use is for representative purposes only and all intellectual property rights belong to the respective owners.