Informed search

Question 1

Another name of informed search

Answer 1

Heuristic search

Question 2

Informed search definition

Answer 2

Search strategy that uses problem specific knowledge to find solutions more efficiently

Question 3

Types of informed search

Answer 3

Best first search algorithm
A* search algo

Question 4

Functions in AI (only names and denotes by)

Answer 4

Evaluation function f(n)
Path cost / Cumulative cost g(n)
Heuristic function h(n)

Question 5

Evaluation function

Answer 5

f(n)
Determines the priority of a node n for exploration in the search algo

Question 6

Path cost

Answer 6

g(n)
Cumulative cost
It represents the actual cost incurred to reach the node n from the start node
It accumulates cost based on the chosen path

Question 7

Heuristic function
range also
Heuristic function is zero when

Answer 7

h(n)
It provides an estimate of the remaining cost to reach the goal from the current node n
It must be admissible (never overestimates) and consistent (entrees triangle inequality) for algos like A* to guarantee optimality
non negative and state dependent
Heuristic function is zero when node is goal node

Question 8

Best first search
* Another name
* Evaluation function
* Definition
* Optimality
* Completeness
* TC
* SC
* Remember in approach
* To check the solution if it is optimal or not, what to do

Answer 8

Best first search
* Another name: greedy search

• Evaluation function : f(n)=h(n), ignoring g(n)
  here h(n) can be staright line distance or manhattan distance or given in the question
  manhattan distance = |x2-x1|+|y2-y1|
• Definition : Search algo that expnds the node that is closest to goal node. It select the node for expansion based on an evaluation function f(n) with the lowest evaluation being expanded first.
• Optimality: Not optimal and may not always find the shortest path as it priortizes nodes that seem closest to the goal
• Completeness: Best first search is not guaranteed to be complete. It may get stuck in loops or explore paths that lead to death ends, especially if heuristic is not admmisible
• TC: The time complexity depends on the quality of the heuristic fumction. In the worst case, it can be exponential if the heuristic is not admissible. However with a good heuristic, it can be very efficient
• SC: The space complexity depends on the size of the frontier, which can vary. In the worst case, it can be exponential, but with a good heuristic, it can be smaller.
• Remember in appraoch: Doesn’t matter if the frontier is empty or not if you reached the goal node then stop in best first search unlike UCS.
• To check the solution if it is optimal or not, compare the solution with A* solution.

Question 9

A*
* Another name
* Evaluation function
* Definition
* Optimality
* Completeness
* TC
* SC
* Remember in approach

Answer 9

A*

• Another name: Informed search
• Evaluation function : f(n) = g(n) + h(n)
  f(n) reperesents the estimated cost of the cheapest solution passing through node n
• Definition : A* search aims to find the cheapest solution by prioritizing nodes with the lowest f(n) values
• Optimality and completeness: A* search is both complete and optimal under certain conditions for the heuristic functions
• TC: The time complexity depends on the quality of the heuristic fumction. In the worst case, it can be exponential if the heuristic is not admissible. However with a good heuristic, it can be very efficient
• SC: The space complexity depends on the size of the frontier, which can vary. In the worst case, it can be exponential, but with a good heuristic, it can be smaller.
• Remember in approach: In A*, we stop when we found the goal node whether the frontier list is empty or not.

Question 10

Important node for A* search

Answer 10

The triangle inequality conceptually resembles ‘consistency monotonicity property’ :- The direct path from n to the goal is no longer than the sum of two shorter paths from n to n’ to the goal.