!
4
Artificial)Intelligence)MID)SEM)Some)important)Questions:)
!
!
SHORT!QUESTIONs!
!
1. Rationality!depends!on!the!following!things:!Choose!the!incorrect!answer.!
i. The!agent’s!percept!sequence!to!date.!
ii. The!agent’s!prior!knowledge!of!the!environment.!
iii. The!actions!that!the!agent!can!perform.!
iv. Inference!Engine!
!
Correct!Answer!:!!(iv)!
!
2.!PEAS!stands!for!!_______!
à!Performance measure, Environment, Actuator, Sensor
!
3. What!are!four!basic!kinds!of!agent!programs!that!embody!the!principles!underlying!
almost!all!intelligent!systems!?!
!
Answer:!
!
I. Simple!reflflex!agents;!!
II. Model–based!reflflex!agents;!!
III. Goal–based!agents;!and!!
IV. Utility–based!agents.!
!
!
4. What!are!the!different!ways!we!can!evaluate!an!algorithm’s!performance?!
!
Answer:!
!
Completeness!
Optimality!
Time!Complexity!
Space!Complexity!
5. Identify!the!Local!Search!Method!:!
!
I. A*!Search!
II. Hill-Climbing!
III. Greedy!Best!First!Search!
IV. Iterative!Deepening!Depth!Limited!Search!(IDS)!
!
Correct!Answer!:!!(ii)!Hill-Climbing!
!
!
!
!
!
6. What! is! Heuristic! Search! and! Heuristic! Function?! Why! choosing! an! appropriate!
heuristic!function!important?!
!
4
à!Heuristic! search! is! otherwise! called! as! Informed! search.! It! uses! problem-specific!
knowledge!
beyond!the!definition!of!the!problem!itself!and!can!find!solutions!more!efficiently!than!
an!uninformed!strategy.!
A!heuristic!function!takes!a!state!as!input!and!returns!a!numeric!value!(path!cost!from!
a! goal)! as! the! output,! which! is! the! composite! assessment! of! the! state.! It! helps! in!
comparison!between!two!non-goal!state!and!so!that!the!most!promising!state!can!be!
chosen!or!it!can!judge!how!close!the!current!state!is!to!the!goal!state.!!
Choosing! an! appropriate! heuristic! function! is! important,! because! the! next! state! we!
choose!depends!on!the!score!returned!by!heuristic!function,!and!if!we!chose!a!wrong!
next!state,!it!may!mis-lead!us!from!the!goal!state.!
!
!
7. Differentiate! between! Admissible! heuristics! and! Inadmissible! heuristics.! Which! one!
breaks!the!optimality!and!why?!
à! A! heuristic! h(n)! is! admissible! if! for! every! node! n,! the! below! given! condition! is!
satisfied-!
h(n)!≤!h*(n),!where!h*(n)!is!the!true!cost!to!reach!the!goal!state!from!n.!
An!admissible!heuristic!never!overestimates!the!cost!to!reach!the!goal!and!hence!it!is!
optimistic.!!
Whereas,! an! inadmissible! heuristic! does! not! satisfy! the! above! condition! and! always!
overestimates!the!cost!and!hence!is!pessimistic.!
Inadmissible! heuristics! always! breaks! the! optimality! as! they! overestimates! the! cost!
which!is! not!at! par!to! the!real! cost,!hence!misleads!the!path!and!may!not!return!the!
optimal!solution.!
!
!
8. “Consistency! applies! Admissibility”-Justify! the! statement.! Under! which! condition! A*!
algorithm!is!optimal?!
—>!Consistent heuristics are very restricted heuristics, so they never overestimates the cost and
hence every consistent heuristic is an admissible heuristic. Hence, “consistency applies
admissibility” is justified. A* algorithm, if uses a tree search and follows an admissible heuristic,
then it is optimal.
!
9. What!is!a!“Relaxed!Problem”?!Why!is!it!needed!in!case!of!some!problems?!Explain!with!
an!example.!
—>!A!problem!with!fewer!restrictions!on!the!actions!is!called!a!relaxed!problem.!It!is!
needed! in! case! of! those! problems,! where! a! proper! heuristic! function! cannot! be!
designed!due!to!restricted!actions.!For!example-!In!8-puzzle!problem,!a!H(n)=!number!
of!misplaced!tiles,!can!only!be!devised,!because!the!restriction!on!the!actions!has!been!
relaxed!and!freedom!has!been!granted!to!directly!replace!one!tile!at!its!proper!location!
according!to!the!goal!state.!
10.!What!is! Local!search!?! Explain!disadvantages!of! local!search.! Suggest! some! solutions!to!
tackle!with!such!problems.!
à!Local search techniques only search in its immediate neighborhood for the solution. So there is a
chance of getting trapped in local optimum. Some solutions to local optimum are-
– Move in some arbitrary direction
– Back track to an ancestor and try some other alternatives.
!
!
4
11.!The figure below shows the 8 puzzle problem with start state and goal state. Assuming that the
heuristic function h(n) sums the Manhattan distances of tiles out of place, the heuristic value of the
start state is________
4
8
6
1
7
3
2
5
Start state
1
2
3
4
5
6
8
7
Goal state
à 1+3+1+1+1+1+1+3 = 12
12. Mark the algorithm(s) for which space requirements grow linearly with depth.
(i) DFS (ii) BFS (iii) DFID (iv) All of these
ài. DFS & ii. DFID
13. Mark the algorithm(s) that always find(s) the shortest path from start state to goal state in
any search space.
(i) DFS (ii) BFS (iii) DFID (iv) None of these
–> ii. BFS & ii. DFID
14. Suppose, you are designing a machine to pass the Turing Test. What are the capabilities
such a machine must have?
à NLP, Knowledge representation, Automated reasoning, Machine learning, Computer
vision, Robotics
15. What is the branching factor in 24 puzzle problem?
è 8
16. What!is!the!advantage!of!Depth!First!Search!over!Breadth!First!?!
!!!!
(a) DFS!is!Complete!whereas!BFS!is!not!complete!in!infinite!search!space.!
(b) DFS!provide!optimal!solution!for!Finite!Search!Space.!
(c) Breadth!First!can!be!implemented!in!recursive!way!while!DFS!can!not!be!implemented.!
(d) DFS!given!a!finite!search!space!provides!a!better!memory!space!requirements.!
!
(d)!
!
16. The!main!disadvantage!of!Depth!Limited!Search!(DLS)!over!Breadth!First!(BFS)!is!?!
(a) For!a!solution!sequence!produced!,!time!complexity!of!DLS!is!not!comparable!to!BFS.!
(b) For!a!solution!sequence!produced!,!space!complexity!of!DLS!is!not!comparable!to!BFS.!
(c) The!DLS!is!not!complete.!
(d) None!of!these.!
(c)!
!
17. !Which!search!does!not!implements!stack!operation!for!searching!the!states?!
(a)!Depth–limited!search!
(b)!Depth–first!search!
(c)!Breadth–first!search!
(d)!None!of!These.!
!
!
4
(c)!
!
18. Which!searching!strategy!explores!the!deepest!state!in!the!search!tree?!
(a) Greedy!Best!First.!
(b) Depth!First!Search.!
(c) Breadth!First.!
(d) A*!Algorithm.!
!
(d)!
!
19. Given!a!problem!in!hand!which!strategy!is!preferred!when!a!solution!is!required!with!best!possible!
space!and!time!complexity.!
!
(a) Depth!First.!
(b) Breadth!First.!
(c) Iterative!Deepening!Search.!
(d) Depth!Limited!Search.!
!
(c)!
!
20.! !Define an Omniscient agent.
Answer: An omniscient agent knows the actual outcome of its action and can act
accordingly; but omniscience is impossible in reality.