SEARCH TECHNIQUES.pdf

SEARCH TECHNIQUES Uninformed Search Algorithms ⚫ Uninformed search is a class of general-purpose search algorithms which operates in brute force-way. ⚫ They do not have additional information about state or search space other than how to traverse the tree, so it is also called blind search...

SEARCH TECHNIQUES Uninformed Search Algorithms ⚫ Uninformed search is a class of general-purpose search algorithms which operates in brute force-way. ⚫ They do not have additional information about state or search space other than how to traverse the tree, so it is also called blind search. ⚫ Important types of uninformed search algorithms: 1. Breadth-first Search 2. Depth-first Search 3. Bidirectional Search  Breadth-first search A Search strategy, in which the highest layer of a decision tree is searched completely before proceeding to the next layer is called Breadth-first search (BFS). No viable solutions are omitted and therefore it is guaranteed that an optimal solution is found. This strategy is often not feasible when the search space is large. Key Terms in BFS ⚫ Node: ⚫ A fundamental unit in the data structure (graph or tree) being searched. Each node represents a state or position in the search space. ⚫ State: ⚫ The specific configuration or situation represented by a node. For example, in a maze-solving problem, a state might represent a specific location in the maze. ⚫ Initial Node/State: ⚫ The starting point of the search. It is the node from which BFS begins its exploration. ⚫ Goal Node/State: ⚫ The target or destination node that BFS aims to reach. The search terminates when this node is found. ⚫ Frontier: ⚫ Also known as the open list, the frontier is a data structure (usually a FIFO queue) that stores nodes that have been discovered but not yet explored. BFS expands nodes from the frontier one at a time. ⚫ Queue: ⚫ A data structure used to implement the frontier in BFS. Specifically, a First-In-First-Out (FIFO) queue ensures that nodes are expanded in the order they were discovered. ⚫ Explored Set/Revisited Check: ⚫ Also known as the closed list or reached set, this is a collection of nodes that have already been expanded and explored to avoid redundant work and infinite loops. ⚫ Expand: ⚫ The process of generating the child nodes of a node. In BFS, expanding a node involves discovering all its neighboring nodes and adding them to the frontier if they haven't been visited before. ⚫ Child Node: ⚫ A node that is directly reachable from another node (the parent node) by following an edge or connection in the graph or tree. ⚫ Breadth: ⚫ Refers to the level or depth of nodes being explored. BFS explores nodes level by level, starting from the initial node and moving outward. ⚫ Depth: ⚫ The distance (in terms of number of edges) from the initial node to a given node. BFS ensures that all nodes at depth ddd are explored before any nodes at depth d+1d+1d+1. ⚫ Complete: ⚫ A property of the BFS algorithm indicating that it will find a solution if one exists within the finite search space. ⚫ Optimal: ⚫ A property indicating that BFS will find the shortest path to the goal node if all edge costs are equal. ⚫ Branching Factor (b): ⚫ The average number of child nodes for each node in the graph or tree. It significantly affects the time and space complexity of BFS. ⚫ Shallowest Node: ⚫ The node at the smallest depth that satisfies the goal condition. BFS is designed to find the shallowest goal node first.  Algorithm 1. Create a variable called LIST and set it to be the starting state. 2. Loop until a goal state is found or LIST is empty, Do a. Remove the first element from the LIST and call it E. If the LIST is empty, quit. b. For every path each rule can match the state E, Do (i) Apply the rule to generate a new state. (ii) If the new state is a goal state, quit and return this state. (iii) Otherwise, add the new state to the end of LIST. ⚫ Initialization: ⚫ Start with the initial node. ⚫ Initialize the frontier with the initial node using a FIFO queue. ⚫ Initialize the explored set to keep track of visited states. ⚫ Main Loop: ⚫ While the frontier is not empty: ⚫ Dequeue a node from the frontier (node to be expanded). ⚫ Check if this node is the goal node (goal state). ⚫ If not, expand the node to generate its child nodes. ⚫ For each child node: ⚫ Check if it has already been visited (in the explored set). ⚫ If not, add it to the frontier and the explored set. ⚫ Termination: ⚫ If the goal node is found, return it as the solution. ⚫ If the frontier is empty and no solution is found, return failure. Detailed Explanation ⚫ node ← NODE(problem.INITIAL): Create the initial node from the initial state of the problem. ⚫ if problem.IS-GOAL(node.STATE) then return node: Check if the initial state is the goal state. If it is, return the initial node as the solution. ⚫ frontier ← a FIFO queue, with node as an element: Initialize the frontier as a FIFO queue and add the initial node to it. The frontier represents the set of nodes to be explored. ⚫ reached ← {problem.INITIAL}: Initialize the reached set with the initial state to keep track of visited states and avoid revisiting them. ⚫ while not IS-EMPTY(frontier) do: Continue the loop as long as there are nodes in the frontier to explore. ⚫ node ← POP(frontier): Remove the node at the front of the queue (FIFO behavior) to expand it. ⚫ for each child in EXPAND(problem, node) do: Generate all the child nodes of the current node by expanding it. ⚫ s ← child.STATE: Get the state of the child node. ⚫ if problem.IS-GOAL(s) then return child: Check if the child's state is the goal state. If it is, return the child node as the solution. ⚫ if s is not in reached then: If the child's state has not been visited yet (not in the reached set): ⚫ add s to reached: Mark the state as reached by adding it to the reached set. ⚫ add child to frontier: Add the child node to the frontier queue for further exploration. ⚫ return failure: If the frontier is empty and no solution has been found, return failure to indicate that the goal state cannot be reached from the initial state.  Advantages 1. Guaranteed to find an optimal solution (in terms of shortest number of steps to reach the goal). 2. Can always find a goal node if one exists (complete). Disadvantages 1. High storage requirement: exponential with tree depth. Example: ⚫ the traversing of the tree using BFS algorithm from the root node S to goal node K. ⚫ BFS search algorithm traverse in layers, so it will follow the path which is shown by the dotted arrow, and the traversed path will be: ⚫ S---> A--->B---->C--->D---->G--->H--->E---->F---->I----> K Summary ⚫ The Breadth-First Search algorithm works by exploring all nodes at the present depth level before moving on to nodes at the next depth level. Here's a step-by-step summary: ⚫ Start: Initialize the search with the initial node. ⚫ Goal Test: Immediately check if the initial state is the goal state. ⚫ Frontier Management: Use a FIFO queue to manage nodes to be explored. ⚫ Expansion: Expand nodes level by level, checking each child node's state. ⚫ Reaching States: Track reached states to avoid revisiting. ⚫ Return: Return the solution if found, or failure if the search completes without finding the goal. ⚫ Time Complexity: Time Complexity of BFS algorithm can be obtained by the number of nodes traversed in BFS until the shallowest Node. Where the d= depth of shallowest solution and b is a node at every state. T (b) = 1+b2+b3+.......+ bd= O (bd) ⚫ Space Complexity: Space complexity of BFS algorithm is given by the Memory size of frontier which is O(bd). ⚫ Completeness: BFS is complete, which means if the shallowest goal node is at some finite depth, then BFS will find a solution. ⚫ Optimality: BFS is optimal if path cost is a non-decreasing function of the depth of the node. Time Complexity ⚫ Tree Representation: BFS explores nodes level by level. For a tree of branching factor b (i.e., each node has b children) and depth d, the number of nodes at each level increases exponentially. ⚫ Number of Nodes: ⚫ Level 0: 1 node (the root) ⚫ Level 1: b nodes ⚫ Level 2: b2 nodes ⚫ Level 3: b3 nodes ⚫... ⚫ Level d: bd nodes ⚫ Total Nodes: The total number of nodes traversed until the shallowest goal node at depth d is: ⚫ T(b)=1+b+b2+b3+…+bd ⚫ T(b) = 1 + b + b2 + b3 +……. + bd.This sum represents a geometric series. The closed-form of this series is approximately O(bd) for large d. ⚫ Hence, the time complexity of BFS is: ⚫ O(bd)  Depth-first search A search strategy that extends the current path as far as possible before backtracking to the last choice point and trying the next alternative path is called Depth-first search (DFS). This strategy does not guarantee that the optimal solution has been found. The search reaches a satisfactory solution more rapidly than breadth first, an advantage when the search space is large. Algorithm Depth-first search applies operators to each newly generated state, trying to drive directly toward the goal. 1. If the starting state is a goal state, quit and return success. 2. Otherwise, do the following until success or failure is signaled: a. Generate a successor E to the starting state. If there are no more successors, then signal failure. b. Call Depth-first Search with E as the starting state. c. If success is returned signal success; otherwise, continue in the loop.  Example ⚫ Root node--->Left node ----> right node. ⚫ It will start searching from root node S, and traverse A, then B, then D and E, after traversing E, it will backtrack the tree as E has no other successor and still goal node is not found. After backtracking it will traverse node C and then G, and here it will terminate as it found goal node. How does Backtracking work? ⚫ The terms related to the backtracking are: ⚫ Live node: The nodes that can be further generated are known as live nodes. ⚫ E node: The nodes whose children are being generated and become a success node. ⚫ Success node: The node is said to be a success node if it provides a feasible solution. ⚫ Dead node: The node which cannot be further generated and also does not provide a feasible solution is known as a dead  Advantages 1. Low storage requirement: linear with tree depth. 2. Easily programmed: function call stack does most of the work of maintaining state of the search. Disadvantages 1. May find a sub-optimal solution (one that is deeper or more costly than the best solution). 2. Incomplete: without a depth bound, may not find a solution even if one exists. Completeness: DFS search algorithm is complete within finite state space as it will expand every node within a limited search tree. Time Complexity: Time complexity of DFS will be equivalent to the node traversed by the algorithm. It is given by: T(n)= 1+ n2+ n3 +.........+ nm=O(nm) Where, m= maximum depth of any node and this can be much larger than d (Shallowest solution depth) Space Complexity: DFS algorithm needs to store only single path from the root node, hence space complexity of DFS is equivalent to the size of the fringe set, which is O(bm). Depth-Limited Search Algorithm ⚫ A depth-limited search algorithm is similar to depth-first search with a predetermined limit. Depth-limited search can solve the drawback of the infinite path in the Depth-first search. Uniform-cost Search Algorithm: ⚫ Uniform-cost search is a searching algorithm used for traversing a weighted tree or graph. ⚫ This algorithm comes into play when a different cost is available for each edge. The primary goal of the uniform-cost search is to find a path to the goal node which has the lowest cumulative cost. ⚫ Uniform-cost search expands nodes according to their path costs form the root node.  Bidirectional Search Algorithm: ⚫ Bidirectional search algorithm runs two simultaneous searches, one from initial state called as forward-search and other from goal node called as backward-search. ⚫ It replaces one single search graph with two small subgraphs in which one starts the search from an initial vertex and other starts from goal vertex. The search stops when these two graphs intersect each other. ⚫ Bidirectional search can use search techniques such as BFS, DFS, etc. ⚫ Advantages: Bidirectional search is fast. requires less memory ⚫ Disadvantages: Implementation of the bidirectional search tree is difficult. one should know the goal state in advance. Example: ⚫ This algorithm divides one graph/tree into two sub-graphs. It starts traversing from node 1 in the forward direction and starts from goal node 16 in the backward direction. ⚫ The algorithm terminates at node 9 where two searches meet. ⚫ Completeness: Bidirectional Search is complete if we use BFS in both searches. ⚫ Time Complexity: Time complexity of bidirectional search using BFS is O(bd). ⚫ Space Complexity: Space complexity of bidirectional search is O(bd). ⚫ Optimal: Bidirectional search is Optimal. ⚫ Advantages: ⚫ Bidirectional search is fast. ⚫ Bidirectional search requires less memory ⚫ Disadvantages: ⚫ Implementation of the bidirectional search tree is difficult. ⚫ In bidirectional search, one should know the goal state in advance. Apply BFS and DFS to trace the goal node U from initial node A. Informed Search Algorithms HEURISTIC SEARCH TECHNIQUES The algorithms that use heuristic functions are called heuristic algorithms. Heuristic algorithms are more efficient because they take advantage of feedback from the data to direct the search path. Uninformed search algorithms or Brute-force algorithms, search through the search space all possible candidates for the solution checking whether each candidate satisfies the problem’s statement. Informed search algorithms use heuristic functions that are specific to the problem, apply them to guide the search through the search space to reduce the amount of time spent in searching.  A good heuristic will make an informed search dramatically outperform any uninformed search: Ex: Traveling Salesman Problem (TSP), where the goal is to find is a good solution instead of finding the best solution.