Cis 561 Unit 1 Assignment 2

CIS 561 Homework #2

Hussain ul Abideen 01617974

Question#1:
Solution:
State: (a,b) for liters in jugs 1 and 2 Integer 0 to 4 (a,b) : 0<= 7,

Initial state:- (Black1,Black2,Black3) : (1,2,3) or (1,3,2) or (2,1,3) or (2,3,1) or (3,2,1) or (3,1,2) (white1,white2,white3) : (5,6,7) or (5,7,6) or (6,5,7) or (6,7,5) or (7,6,5) or (7,5,6) (Blank): (4)

Goal state:- (Black 1, Black 2, Black 3) : (5,6,7) or (5,7,6) or (6,5,7) or (6,7,5) or (7,6,5) or (7,5,6) (white1,white2,white3) : (1,2,3) or (1,3,2) or (2,1,3) or (2,3,1) or (3,2,1) or (3,1,2) (Blank): (4)

Operations:- (part1)
Shift black tile with blank tile which is next left to black tile,
Shift black tile with blank tile which is next right to black tile,
Shift white tile with blank tile …show more content…
g(n) is just a multiple of depth n. Thus, breadth-first search and uniform-cost search would behave the same in this case f(n) = g(n) = 1*(depth of n)

b) Greedy search is a special case of best-first search  TRUE
Because loop is start again to validating greedy search as a special case of Breadth First Search, if we have a successor and its parent node it have to be in the front line which clamps the open list.
c) Uniform-cost search is a special case of A∗ search.  TRUE
Heuristic is a constant function or h (n) =0 uniform cost search will produce the same result as A*Search.

d) Breadth-first search always expands at least as many nodes as A * search with an admissible heuristic.  FALSE Because A* search uses the optimal path with very fewer stretched nodes and Breadth First Search expands more nodes.
e) Depth-first search may expand less number of nodes than A * search with an admissible heuristic. 