Question

and the arrows represent possible action transitions. S is the start state and there are two goal states: G1 and G1. The cost of each action is given by the number next to the arrow. Each state is labelled by an identifying name (S, A-F, G1, G2, H) and also a number. The number is the value of a heuristic function, which gives an estimate of the cost of getting to the nearest goal from that node. (a) Consider the following graph diagram of a search space. Each circle represents a state 15 10 20 12 10 50 G2 G1 40 30 100 i) Write down the optimal path from S to one of the goals (ii) Write down the sequence in which nodesw be expanded until one of the goal states is reached, while performing a best first search (also known as greedy search)

Answer 1

i) S->C->G2 IS THE OPTIMAL PATH TO REACH GOAL G2

f(n) = g(n) + h(n)

f(S) = f(15) = 15

f(C) = f(10) = 6 + 10 = 15

f(G2) = g(G2)+h(G2) = 12 + 0 = 12

ii)

Using best first search algorithm.

we will traverse the edge with minimum cost

S->B

Now will traverse the minimum cost child

S->B->E

since it does not reach the goal state it backtracks

S->B->F

since again not reaches the goal state backtrack to s

S->C

Now again traverse the minimum cost child

S->C->G2

ANswer.

PLEASE UPVOTE (THANK YOU IN ADVANCE) IF YOU SATISFY WITH THE ANSWER IF ANY QUERY ASK ME IN COMMENT SECTION I WILL RESOLVE THE QUESTION FOR YOU */