Question

1) Consider the directed graph below. “S” is the start state and “G1,G2,G3” are 3 goal states. In traversing the graph one can move only in the direction indicated by the arrows. The numbers on the edges indicate the step-cost for traversing that edge. The numbers in the nodes represent the estimated cost to the nearest goal state. In the following you will be asked to search this graph using various search strategies. When you work out your answer, please provide a list of nodes that have been checked (removed from the fringe) in the order that they were visited. If there is a tie in the ordering of the fringe nodes one should break the tie by checking the tied nodes in alphabetical order. Use the following notation: [Node,Parent,Path-cost]. For example [A,S,3]. a) Draw the first 3 levels of the search tree, where the start state is not counted as a level. For the following search strategies answer all of the following questions: -Trace out the steps of ....... search. -Provide the solution path from the start state to the goal state. -What is the total cost to the goal? -Is this guaranteed to be the optimal solution? -What is the time and space complexity of ...... search? b) A* search. c) “greedy best first search”. d) depth-first search. e) uniform cost search.

Answer 1

In Tree or graph search there are two types of searching algorithm. Uninformed Search /Blind search and Informed Search / Heuristic Search. A* search and " greedy best-first search" belong to  Informed Search category. Uninformed Search contains depth fir search and uniform cost search.

G2 ا ) فيا

To reach the goal cost calculation.

G1=3+7+2=12, [A,S,3],[E,A,7],[G1,E,2]

G2= 1+2+1+5=9, [B,S,1],[F,B,2],[D,F,1],[G1,D,5]

G3=1+2+11=14.[B,S,1],[C,B,2],[G3,C,11]

that means to reach goals we have to traverse those paths.

1.A* Search Explore A node first because of h(B)=1, that means the least heuristic expand first. where h(A)=9 and h(C)=3. It is an optimal algorithm.

2. Greedy best-first search also not optimal Search. Not always give an optimal solution. It is not also complete.

3. DFS is not optimal as well as not complete. It Works on LIFO, expand [A, S,3] then [G1, A 10] to reach G1.

4. Uniform cost search expands B first because it works with the lowest cost   [B, S,1]. That leads to the lowest cost goal, It is an optimal search algorithm.

A* Search

Expand node based on an estimate of total path cost through node
Evaluation function f(n) = g(n) + h(n)
– g(n) = cost so far to reach n
– h(n) = estimated cost from n to goal
– f(n) = estimated total cost of the path through n to goal
The efficiency of the search will depend on the quality of heuristic h(n)

Yes , A* search is optimal in nature
– Also optimally efficient:
No other optimal algorithm will expand fewer nodes, for a given heuristic

The time complexity of A* depends on the heuristic. In the worst case of an unbounded search space, the number of nodes expanded is exponential in the depth of the solution (the shortest path) d.: Time Complexity is: O(b^d), where b is the branching factor

Greedy Best first search

A special case of best-first search
– Uses h(n) = heuristic function as its evaluation function
– Expand the node that appears closest to goal

It is not Optimal search Algorithm

Time Complexity :
– O(b^m ), can generate all nodes at depth m before finding a solution
– m = maximum depth of search space, b branching factor

DFS (Depth-first search)

Expand the deepest unexpanded node
• Implementation:
– For DFS, fringe is a Last-in-first-out (LIFO) stack
– new successors go at the top of the stack

Time Complexity
– maximum tree depth = m
– assume (worst case) that there is
1 goal leaf at the RHS at depth d
– so DFS will generate O (b^m )

DFS is not optimal Search.

Uniform cost search

Uniform cost search always expands the node on the fringe with minimum cost g(n). If costs are equal (or almost equal) will behave similarly to BFS.

Time Complexity: In uniform cost search time complexity O( b ^ [1 + floor(C*/e)]) . "read as b to the power[1 + floor(C*/e)]".  C* be the cost of the optimal solution and b is the branching factor.

Uniform cost search​​​​​​​ also is optimal in nature.