Scribd
Upload
265 views5 pages

Mid-Sem - Examination CS 411, Artificial Intelligence

The document summarizes problems related to artificial intelligence topics like search algorithms, heuristics, constraint satisfaction problems, and game trees. It contains multiple questions asking to define concepts, calculate heuristics, draw search trees and graphs, formulate constraint satisfaction problems, and apply minimax and alpha-beta search algorithms to game trees.

Uploaded by

Delta Mike
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
265 views5 pages

Mid-Sem - Examination CS 411, Artificial Intelligence

The document summarizes problems related to artificial intelligence topics like search algorithms, heuristics, constraint satisfaction problems, and game trees. It contains multiple questions asking to define concepts, calculate heuristics, draw search trees and graphs, formulate constraint satisfaction problems, and apply minimax and alpha-beta search algorithms to game trees.

Uploaded by

Delta Mike
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Mid-Sem.Examination CS 411, Articial Intelligence.

Max Time 1:00 hour 1. Short answer type a. Dene a search problem. Max Marks 30 10 2

b. Calculate the replacement heuristic and Manhattan heuristic for the following 8 puzzle problem.

1 Solution. Both are 5. d. Find the search space tree for the following search problem

1 Solution.

e. Give the evaluation function for best rst search, greedy best rst search, and A search. 2 f. Find the constraint graph for the following crossword problem. Also write the domain of the crossword. 1

2 g. Let following is the graph Recursive best rst search.

What will be the backup f value? Draw the graph after substituting the backup value f . 2 2. Consider the following graph, in which A is the start node and F is the goal node. Assume that nodes are visited at most once. Let the heuristic function h(u) be the minimum number of arcs between node n and the goal node.

(a) Find the fringe for uniform cost search for each level. level fringe 1 A 2 B,E,C Solution. 3 E,C 4 F,D,C 5 D,F 2

(b) Find the fringe for best rst search for each level. level fringe 1 A 2 B,E,C Solution. 3 E,C 4 F,D,C (c) Is this heuristic is admissible or not? Solution. Yes, it is an conservative estimate of distance. (d) Find the fringe for greedy search for level. level fringe 1 A Solution. 2 B,E,C 3 B,C,F,D (e) In what order does A search visit the nodes? level fringe 1 A 2 B,E,C Node visited in A is A,B,E,F. Solution. 3 E,C 4 F,D,C

2 2

3. Consider the following classroom scheduling problem: There are 4 classes, C1, C2, C3, and C4, and 3 class rooms, R1, R2, and R3. The following table shows the class Class Time C1 8:00am-9:30am schedule: C2 9:00am-11:30am C3 11:00am-12:30pm C4 12:00am-1:30pm In addition, there are the following restrictions: (a) Each class must use one of the 3 rooms, R1, R2, R3. (b) R3 is too small for C3. (c) R2 and R3 are too small for C4. One way of formulating this problem as a constraint satisfaction problem is to let each class, C1, . . . , C4, be a variable, and each room, R1, R2, R3, be the possible values for these variables. (a) Show the initial possible values for each variable,C1, . . . , C4, given the restrictions above. 1 (b) Construct a constraint graph for above problem. (c) Give an assignment of rooms such that all constraints satised. Solution. Constraint graph 3 2 2

Room allocation is {C1 : R1 }, {C2 : R3 }, {C3 : R2 } and {C4 : R1 }. 4. Consider the following game tree in which the static score (in parentheses at the tip nodes) are all from the rst players point of view. Assume that the rst player is maximizing player (a) .Show Mini-max search graph. 2

(b) What node would not need to be examined using the alpha-beta algorithmassuming that nodes are examined in according to breadth rst search order. . 3

Solution Minmax search graph

Alpha-beta pruning

Bhupendra Gupta

You might also like