search algorithms

• Search Algorithms


  Step-by-step procedure used to locate specific data among a collection of data
• Search algorithms are one of the most essential areas of artificial intelligence
• Problem-solving agents in AI

  • They mostly use search strategies or algorithms to solve a specific problem and provide the best result
  • They are goal-based agents and use atomic representation
• Uninformed (Blind) search algorithms


  • Do not contain any domain knowledge such as closeness, the location of the goal
  • Operate in a brute-force way as they only include information about how to traverse the tree and how to identify leaf and goal nodes

  
• Informed (Heuristic) search algorithms


  Contain domain knowledge to guide the search

  
• Breadth-First Search (BFS)


  1. Starts searching from the root node of the tree and expands all successor nodes at the current level before moving to nodes of next level

  2. Implemented using FIFO queue data structure
• Breadth-First Search (BFS)


  • Provides a solution if any solution exists
  • If there are more than one solutions, it will provide the minimal solution which requires the least number of steps
  • Requires lots of memory since each level of the tree must be saved into memory to expand the next level
  • Needs lots of time if the solution is far away from the root node
• Depth-First Search (DFS)


  1. Starts from the root node and follows each path to its greatest depth node before moving to the next path

  2. Uses a stack data structure for its implementation
• Depth-First Search (DFS)


  • Requires very less memory as it only needs to store a stack of the nodes on the path from root node to the current node
  • Takes less time to reach the goal node than BFS algorithm (if it traverses in the right path)
  • Possibility that many states keep re-occurring, and there is no guarantee of finding the solution
  • May go into an infinite loop
• Uninformed search algorithms are also called blind search
• Uninformed search algorithms only include information about how to traverse the tree and how to identify leaf and goal nodes

  
• Uninformed search algorithms examine each node of the tree until it achieves the goal node
• Breadth-First Search (BFS) is an example of a general-graph search algorithm

  
• Depth-First Search (DFS) is a recursive algorithm for traversing a tree or graph data structure

  
• Depth-First Search (DFS) uses a stack data structure for its implementation
• Depth-First Search (DFS) is similar to the Breadth-First Search (BFS) algorithm in its process

  
• Depth-First Search (DFS) has the possibility that many states keep re-occurring, and there is no guarantee of finding the solution
• Depth-First Search (DFS) may go into an infinite loop
• Breadth-First Search (BFS) is complete, which means if the shallowest goal node is at some finite depth, then BFS will find a solution
• Breadth-First Search (BFS) is optimal if path cost is a non-decreasing function of the depth of the node
• Depth-First Search (DFS) is complete within finite state space as it will expand every node within a limited search tree
• Depth-First Search (DFS)


  • It only needs to store a stack of the nodes on the path from root node to the current node
  • It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right path)
• Depth-First Search (DFS)


  • There is the possibility that many states keep re-occurring, and there is no guarantee of finding the solution
  • DFS algorithm goes for deep down searching and sometime it may go to the infinite loop

  
• Depth-First Search (DFS)


  • Root node--->node --->node
• DFS search algorithm is complete within finite state space as it will expand every node within a limited search tree
• Time Complexity of DFS

  Equivalent to the node traversed by the algorithm, given by m= maximum depth of any node which can be much larger than d (Shallowest solution depth)
• Space Complexity of DFS

  Equivalent to the size of the fringe set, which is O(bm)
• DFS search algorithm is non-optimal, as it may generate a large number of steps or high cost to reach to the goal node

  
• Uniform Cost Search


  • Searching algorithm used for traversing a weighted tree or graph
  • Expands nodes according to their path costs form the root node
  • Can be used to solve any graph/tree where the optimal cost is in demand
  • Implemented by the priority queue, gives maximum priority to the lowest cumulative cost
• Uniform cost search is equivalent to BFS algorithm if the path cost of all edges is the same
• Uniform Cost Search


  • Optimal because at every state the path with the least cost is chosen
  • Does not care about the number of steps involve in searching and only concerned about path cost, due to which this algorithm may be stuck in an infinite loop
• Uniform Cost Search


  • Root node--->node (with the least cost) --->node (with the least cost)
• Uniform-cost search is complete, such as if there is a solution, UCS will find it
• Time Complexity of Uniform Cost Search


  Worst-case is O(b1 + [C*/ε]), where C* is Cost of the optimal solution, and ε is each step to get closer to the goal node
• Space Complexity of Uniform Cost Search


  Worst-case is O(b1 + [C*/ε])
• Uniform-cost search is always optimal as it only selects a path with the lowest path cost
• Informed Search


  • Uses domain knowledge to guide the search and find a solution more efficiently than uninformed ones
  • Also called Heuristic search, which might not always be guaranteed for best solutions but guaranteed to find a suitable solution in a reasonable time

  
• Informed Search Algorithms


  • Greedy Search
  • A* Search
  • Genetic Algorithm
• Heuristic Function


  • Takes the agent's current state as input and estimates how close the agent is to the goal
  • May only give the best solution, but it guarantees to find a suitable solution in a reasonable time
  • Represented by h(n) and calculates the cost of an optimal path between the pair of states
  • Value is always positive
• Admissibility of the heuristic function: h(n) <= h*(n), where h(n) is heuristic cost, and h*(n) is the estimated cost