Problem 2: Consider the following search problem as represented in the below tree. The start state is given as A and the goal state is represented as G (all of the nodes represented as G1, G2, G3, G4 are actually the same goal G but they are numbered to ease your work in solution)

In the below tree, number on the edges which are black represents the actual cost between the nodes and the red values on the nodes represent the heuristic value.

Please answer the following questions by using the above tree. Some of the rules you should follow in your solutions as follow.

Do not use colors in your solution.

In order to write numbers next to G do not use G1 but either use subscript and write G1.

Any cost information written like B2 will not be accepted you should use superscript and it should be written B2

In the questions you should use the queueing techniques as it is done in the lectures even it is possible to solve it in another way, the solutions with different methods wont be accepted.

While using the letters in the queue use font-14 (Arial) ex: A

For queuing techniques please use the reserved places for you. To show the expanded nodes please use the word (insert-shapes-line) so that it can be easily detected as an example A

Follow the line numbers in an order when your write your queue which is top to down.

Do not change the font or the format of the below reserved spaces for the questions

If you need to draw, please use (insert-shapes)

In the queue if you have a node with the same cost of the new expanded one, add the new expanded one after the one available in the queue.

Problem 2: Consider the following search problem as represented in the below tree. The start state is given as A and the goal state is represented as G (all of the nodes represented as G1, G2, G3, G4 are actually the same goal G but they are numbered to ease your work in solution)

In the below tree, number on the edges which are black represents the actual cost between the nodes and the red values on the nodes represent the heuristic value.

Please answer the following questions by using the above tree. Some of the rules you should follow in your solutions as follow.

Do not use colors in your solution.

In order to write numbers next to G do not use G1 but either use subscript and write G1.

Any cost information written like B2 will not be accepted you should use superscript and it should be written B2

In the questions you should use the queueing techniques as it is done in the lectures even it is possible to solve it in another way, the solutions with different methods wont be accepted.

While using the letters in the queue use font-14 (Arial) ex: A

For queuing techniques please use the reserved places for you. To show the expanded nodes please use the word (insert-shapes-line) so that it can be easily detected as an example A

Follow the line numbers in an order when your write your queue which is top to down.

Do not change the font or the format of the below reserved spaces for the questions

If you need to draw, please use (insert-shapes)

In the queue if you have a node with the same cost of the new expanded one, add the new expanded one after the one available in the queue.

a) What solution path will Breadth First Search returns? Write the path and show how you reach the goal by using queuing technique (10 pts )

20 2 6 17 16 B 4 2 3 10 18 0 E H G 4 3 0 0 M G4 2 17 G N