Another name of informed search
Heuristic search
Informed search definition
Search strategy that uses problem specific knowledge to find solutions more efficiently
Types of informed search
Best first search algorithm
A* search algo
Functions in AI (only names and denotes by)
Evaluation function f(n)
Path cost / Cumulative cost g(n)
Heuristic function h(n)
Evaluation function
f(n)
Determines the priority of a node n for exploration in the search algo
Path cost
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
Heuristic function
range also
Heuristic function is zero when
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
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
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.
A*
* Another name
* Evaluation function
* Definition
* Optimality
* Completeness
* TC
* SC
* Remember in approach
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.
Important node for A* search
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.
