2-3 tree search.docx

A strategy is defined by picking the order of node expansion Strategies are evaluated along the following dimensions: completeness—does it always find a solution if one exists? time complexity—number of nodes generated/expanded space complexity—maximum number of nodes in memory optimality—does it al...

A strategy is defined by picking the order of node expansion Strategies are evaluated along the following dimensions: completeness—does it always find a solution if one exists? time complexity—number of nodes generated/expanded space complexity—maximum number of nodes in memory optimality—does it always find a least-cost solution? Time and space complexity are measured in terms of b—maximum branching factor of the search tree d—depth of the least-cost solution m—maximum depth of the state space (may be ∞) Uninformed strategies use only the information available in the problem definition without any additional Breadth-first search Breadth-first search is a tree traversal algorithm that explores nodes level by level. Using a queue to store frontier nodes supports the behaviour of this search. Depth-first search is another tree traversal algorithm that goes deep into a tree exploring for nodes branch by branch. Description: BFS explores all neighbor nodes at the present depth level before moving to the nodes at the next level. It systematically expands outward from the initial state until it finds the goal state. Strategy: BFS uses a FIFO (First-In-First-Out) queue to store the frontier nodes. Advantages: Guarantees the shortest path to the goal in terms of number of edges. Disadvantages: Requires significant memory space to store the frontier nodes, especially for large search spaces. Uniform-cost search Uniform Cost Search (UCS) is a type of uninformed search that performs a search based on the lowest path cost. UCS helps us find the path from the starting node to the goal node with the minimum path cost. Description: UCS expands the node with the lowest path cost (i.e., cumulative cost from the initial state) rather than just the shallowest node. Strategy: UCS uses a priority queue ordered by the cumulative path cost to store the frontier nodes. Advantages: Finds the optimal solution in terms of the least total cost. Disadvantages: May expand many nodes with low costs before finding the optimal solution, leading to high time complexity. Depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph. Description: DFS explores as far as possible along each branch before backtracking. Strategy: DFS uses a LIFO (Last-In-First-Out) stack to store the frontier nodes. Advantages: Requires less memory compared to BFS as it only needs to store nodes along the current path. Disadvantages: Not guaranteed to find the shortest path, can get stuck in infinite loops if the search space contains cycles. Depth-limited search DLS begins at the base node and recursively examines every node at its current level before heading to the next level. If the goal state is not found at the current depth level, the algorithm moves to the next level until the depth limit is reached or the goal state is found. Description: DLS is a variant of DFS that limits the maximum depth of exploration. Strategy: DLS terminates the search when it reaches a specified depth limit, preventing infinite loops. Advantages: Prevents DFS from getting stuck in infinite loops in cyclic search spaces. Disadvantages: May miss the solution if the depth limit is too shallow. Iterative deepening search In computer science, iterative deepening search or more specifically iterative deepening depth-first search is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found. Description: IDS is a combination of DFS and DLS. It repeatedly performs DFS with increasing depth limits until the goal state is found. Strategy: IDS systematically increases the depth limit with each iteration. Advantages: Retains the memory efficiency of DFS while guaranteeing the completeness of BFS. Disadvantages: Redundant exploration of nodes at lower levels can increase time complexity, especially in large search spaces. Best-first search Greedy search – looks for the fastest/slowest growth/descent towards the goal node before the expansion Description: Greedy search is a heuristic-based search algorithm that selects the node that appears to be the most promising at each step. It prioritizes nodes that are closest to the goal state according to a heuristic function, without considering the entire path or the cost incurred to reach that node. Strategy: At each step, greedy search expands the node that is estimated to be the closest to the goal state based on a heuristic evaluation function. Heuristic Function: Greedy search relies heavily on the heuristic function, which provides an estimate of the cost or distance from a given state to the goal state. This heuristic guides the search by biasing it towards nodes that appear to be more promising based on the heuristic evaluation. Advantages: Greedy search is often memory-efficient and can be computationally fast, especially when the search space is relatively small. Disadvantages: Greedy search does not guarantee optimality or completeness. It may get stuck in local optima or fail to find the optimal solution if the heuristic function is not admissible or if it leads the search down the wrong path. Completeness: Greedy search is not guaranteed to find a solution, especially if it encounters a dead end or if the heuristic function leads it astray. Optimality: Greedy search is not guaranteed to find the optimal solution, as it makes decisions based solely on local information without considering the entire search space or the cost of reaching the goal. A∗ search – uses heuristic function which calculates an estimation of the cost for expansion at each node of the search space Description: A* search is an informed search algorithm that efficiently finds the shortest path from a start state to a goal state in a weighted graph or tree. It intelligently combines information about the cost to reach a node from the start state (known as g-value) and an estimate of the cost to reach the goal state from that node (known as h-value). Strategy: A* search selects the node with the lowest combination of the cost-so-far (g-value) and the estimated cost-to-go (h-value) at each step. It prioritizes nodes that have a lower total estimated cost (f-value = g-value + h-value), aiming to minimize the total cost to reach the goal state. Heuristic Function: A* search relies on a heuristic function (h-value) that provides an estimate of the cost or distance from a given state to the goal state. This heuristic guides the search by biasing it towards nodes that appear to be more promising based on the estimated total cost. Advantages: A* search is both complete (guaranteed to find a solution if one exists) and optimal (guaranteed to find the optimal solution with the minimum total cost). It combines the efficiency of greedy search with the optimality of uniform-cost search, making it highly effective in finding optimal solutions in many problem domains. Disadvantages: A* search may encounter performance issues or become inefficient if the heuristic function is not admissible (underestimates the true cost) or not consistent (satisfies the triangle inequality). It may require significant memory and computation resources, especially in large search spaces with complex heuristic functions. Completeness: A* search is complete, meaning it will always find a solution if one exists. Optimality: A* search is optimal, meaning it will always find the optimal solution with the minimum total cost if the heuristic function is admissible (never overestimates the true cost) and consistent (satisfies the triangle inequality). Admissible heuristic Role of Heuristic Function: a. Purpose: A heuristic function estimates the cost or utility of reaching a goal state from a given state in a search problem. It guides the search process by providing a measure of "closeness" to the goal’s. Effect on Search: Heuristic functions influence the search process by biasing it towards states that appear more promising based on the heuristic evaluation. This can significantly reduce the search space and improve efficiencies. Use in Different Search Methods: Heuristic functions are commonly used in informed search algorithms such as A* search, where they guide the search towards the most promising paths based on the estimated cost to reach the goal. A heuristic function, also simply called a heuristic, is a function that ranks alternatives in search algorithms at each branching step based on available information to decide which branch to follow. For example, it may approximate the exact solution. The objective of a heuristic is to produce a solution in a reasonable time frame that is good enough for solving the problem at hand. This solution may not be the best of all the solutions to this problem, or it may simply approximate the exact solution. But it is still valuable because finding it does not require a prohibitively long time. Heuristics may produce results by themselves, or they may be used in conjunction with optimization algorithms to improve their efficiency Relaxed Problem Admissible heuristics can be derived from the exact solution cost of a relaxed version of the problem If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h1(n) gives the shortest solution If the rules are relaxed so that a tile can move to any adjacent square, then h2(n) gives the shortest solution Key point: the optimal solution cost of a relaxed problem is no greater than the optimal solution cost of the real problem This could be an useful advice how to formulate suitable heuristics