Problem 1 [20 points]. Use the generic graph search method covered in class, car

Question

Problem 1 [20 points]. Use the generic graph search method covered in class, carry out BFS DFS, uniform-cost, and A" over the graph and the B heuristic function given in the figure. The start state is xA and the goal state is xG-F. 6 5 For a given state, its neighbors appear in the ad- jacency list in an alphabetical order. For example C's neighbors are ordered as A, B, D, E, F. To make it simpler to write down the solution, du- plicate nodes may be removed from the queue (without changing the behavior of the algorithm) Your answer should start with the initial queue followed by the status of the search after each while loop. Search status should be given as the node that gets expanded followed by the current queue. For each search, you and A*, the entries in the queue should be accompanied by the value of the evaluation function; use alphabetical order for breaking ties. As an example, the first two entries of the answer for uniform-cost search should be: 6 4 4 0 3 i only need to provide the complete list of statuses. For uniform-cost 1, q= [A(0)] 2. A, q= [B(3), D(4),E(5)]

Explanation / Answer

BFS -it is breadth first traversal algorithm and uses queue.

resultant be array R

so pop(Queue) results in A. so R = [A]

so pop (Queue) gives B . so R =[A,B]

(the adjacent nodes A,C are not pushed into queue because it is already traversed.)

So pop(queue) gives C . so R=[A,B,C]

pop(Queue) gives D. so R=[A,B,C,D]

pop (queue) gives F . so R=[A,B,C,D,F]

pop(queue)= E .so R=[A,B,C,D,F,E] and hence the traversal.

We have F as destination so Output path = [A,B,C,D,F]

DFS

let satck be S(where nth element of array is stack top) and output be R which stores the result.

1.S=[A] ,move the traversded node to output

R=[A] (then push neighbour of deleted element )

2.S=[A,B] R=[A,B]

3.S=[A,B,C] R=[A,B,C]

4.S=[A,B,C,F] R=[A,B,C,F,]

5.S=[A,B,C,F,E] R=[A,B,C,F,E]

6.S=[A,B,C,F,E,D] R=[A,B,C,F,E,D]

remove elemenets one by one since all nodes are traversed no more nodes are added.

since path is from A-F Output path is [A,B,C,F]

7.S=[ ] R=[A,B,C,F,E,D]

UNIFORM COST

Initialization :{[A,0]}

1.{[A->B,3],[A->C,5],[A->D,4]}

2.{[A->B->C,1],[A->B->F,6],[A->C,5],[A->D,4]}

3.{[A->B->C->E,2],[A->B->C->F,5],[A->B->F,6],[A->C,5],[A->D,4]}

so shortest path is [A->B->C->F]

A*

1.intialization ; [A(6)]

2.[B(9),C(11),D(10)] So Output is =[A->B]

3.[C(11),D(10),C(10),F(15)] So Output is =[A->B->C]

4.[D(10),F(15),F(15),D(15)] So output is [A->B->C->F]

A

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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