Notes - AI Fundamentals
Lord Rama, was doing BFS search until he met Jatayu, then he started DFS.
Note - This document was created on notion. It looks more readable there.
Search Methods for Problem Solving.
State space search
- should be precise
- be able to analyse
S = { S, A, Action(s), Result(s,a), Cost(s,a) }
Search Types: Uninformed (blind, brute force) and Informed (heuristic)
| Uninformed | Informed |
| search without information | search with information |
| no knowledge | use knowledge to find steps to solution |
| time consuming | quicker solution |
| more complexity (time, space) | less complexity (time, space) |
| DFS, BFS | A*, Heuristic DFS, Best first search |
BFS - uninformed - breadth first search
- uninformed search technique
- FIFO (queue)
- Shallowest node
- complete (means it will provide the answer)
- optimal (shortest result/cost)
- time complexity = O(V + E) in Data Structures; in
AI → O(b^d)where b: branch factor and d: depth (of tree) - example: tree
DFS - uninformed - depth first search
- uninformed search technique
- stack (LIFO)
- deepest node
- incomplete (possible that dfs doesn’t give a solution gets stuck in a loop or infinite search space)
- non-optimal ()
- time complexity = O(V+E); in
AI → O (b^d); b: branching factor, d: depth - space complexity = O(b*d)
- example: tree
DFS family - Depth Bounded, Iterative Deepening
| Depth-Limited Search (DLS) | Iterative Deepening Depth-First Search (IDDFS) |
| Depth is fixed — search is restricted to a certain depth so that it doesn’t encounter a loop or go into infinitely deep space. | Iteratively first checks for depth 1, then 2, then 3, and so on... till the goal is found. |
| Completeness: NO (if the solution is beyond the depth limit) | Completeness: YES (if the branching factor 'b' is finite) |
| Optimality: NO (it might find a non-optimal solution if a solution exists at a shallower depth but is not explored due to the limit) | Optimality: YES (it is guaranteed to find the shallowest goal) |
| Time Complexity: $O(b^l)$ where 'l' is the depth limit. | Time Complexity: $O(b^d)$ where 'd' is the depth of the shallowest solution. (This is asymptotically equivalent to BFS and DFS for large d) |
| Space Complexity: $O(bl)$ where 'l' is the depth limit. (Same as DFS) | Space Complexity: $O(bd)$ where 'd' is the depth of the shallowest solution. (Same as DFS) |
Bidirectional search (extension of BFS, DFS)
- Two simultaneous searches - from initial to goal & from goal to initial, stops when two meets.
- time complexity = O(2* b^d/2)
- complete in BFS, not complete in DFS
Heuristics - Informed search
- Used to solve a problem quickly
- For solving non-polynomial problem (i.e. the ones having exponential complexity) in polynomial times.
- a good enough solution will be reached (may not be the optimal)
- Technique:
- eucledian distance
- manhatten distance or no. of misplaced tiles (8 puzzle problem - complexity O(3^20))
Greedy best first search
- Combines BFS and DFS to form best first search
- use of heuristic
- admissibility: h(n) ≤ h*(n) i.e. h(n) should always be less than or equal to actual cost. (heuristic function should not over estimate.)
- if f(n) = h(n) → optimal solution. (i.e. actual cost = heuristic function); sometimes the solution can be optimal even if actual cost is greater. [but actual cost cant be less]
- completeness - NO, optimality - NO
- time and space complexity = O(b^m)
A* - informed search
f(n) = g(n) + h(n)where g(n) is actual cost from start node to n; h(n) is estimation cost from n to goal node.- Example - directed graph
- optimal
- time and space complexity = O(b^d)
A* admissibility - underestimate, overestimate
- h(n) ≤ h*(n) → underestimation [ optimal solution ]
- h(n) is heuristic value and h*(n) is the actual/optimal value
- we always get optimal solution in case of underestimation
- h(n) ≥ h*(n) → overestimation (may not be the optimal)
- example
Hill climbing - Local search algorithm
- Local search algorithm, no backtracking
- Algorithm:
- Evaluate initial state
- Loop until a solution is found or there are no operators left
- select and apply a new operator
- evaluate the new state
- if goal then quit
- if better than current state then it is new current state
- Problems: local maxima, plateau/flat maxima, ridge
- Good for a few problems.
- Better space complexity
tbd:
- Simulated annealing
- Local Beam Search
- Genetic Algorithm
- Ant Colony Optimization (ACO)
- Particle Swarm Optimization (PSO)
- Intro & Intelligent agents
References
YT playlists - GATE smasher - NPTEL - CS50