Informed Search (Week 4)

Question 1

What are two types of models of the world?

Answer 1

• Simulation: It takes a real world environment and copies it into program
• Emulation: It connects program with real world environment

Question 2

Types of Informed Search

Answer 2

• Heuristics
• Greedy Search
• A* Search

Question 3

Properties of Informed Search Algorithm

Answer 3

• Useful in large space
• Time efficient
• It operates on heuristics function

Question 4

What is a heuristic function

Answer 4

• A heuristic function estimates how close an agent is to the goal state
• It finds most promising path
• Input : Current State Output: Estimation of how close agent is to goal
• It value is always positive
• Represented by h(n)

Question 5

What is Greedy Search properties?

Answer 5

• Node to node search
• Expands the node that seems closest to the goal in each step (i.e. Forward Search)
• It takes node cost in consideration
• Not time consuming

Question 6

How does A* Search work?

Answer 6

• It combines UCS and Greedy Search
• Maximises efficiency/accuracy and chances of success

Question 7

What are costs of UCS, Greedy search and A* Search?

Answer 7

• UCS: It orders by path cost i.e. backward cost g(n)
• Greedy Search: It orders by goal proximity i.e. forward cost h(n)
• A* Search: It orders by sum of both costs i.e. f(n)= g(n)+h(n)
  .: g=edge cost
  h=node cost

Question 8

Is A* optimal or complete?

Answer 8

• Its both because it searches for shorter paths first.
• If estimated cost by heuristic is more than actual cost than it will not be optimal.