Unit 1 AI

In a finite state-space, if a path to goal exists then which of the following search algorithms always find the path?

• DFS

• BFS

• BOTH A & B

• NONE OF THE ABOVE

In a infinite state-space, if a path to goal exists then which of the following search algorithms always find the path?

• DFS

• BFS

• BOTH A & B

• NONE OF THE ABOVE

MoveGen(state) function returns

• Returns input state

• Returns states that are reachable in one step

• Returns if state matches goal

• NONE OF THE ABOVE

Best First Search depends upon 

• Heuristic function 

• Time Complexity

• Space Complexity 

• Both B & C

Refer the figure

• 10

• 11

• 12

• 14

Refer the figure

• ABFEKJDICGM

• ABFEKCGM

• ABCGM

• ABDEFIJKCGM

Refer the figure

• -1

• -4

• 6

• 4

Refer the figure

• -10

• 10

• 4

• -4

Refer the figure

• TRUE

• FALSE

Consider a SAT problem where formula F is given by
F = (b ∨ ~c)  ∧ (c ∨ ¬d) ∧ ~b ∧ (~a ∨  ~e) ∧ (e ∨ ~c) ∧ (~c ∨ ~d)
Heuristic function h(F) returns the number of satisfied clauses in the formula F. Observe that one has to maximize the heuristic value. A candidate assignment, or state, is of the form (abcde). If the state is 0000, then the assignment is a=0, b=0, c=0 and d=0. What is the value returned by h(F) for the assignments 11111.

• 2

• 3

• 4

• 5