AI Assignment: Uninformed Search Strategies PDF

KFUEIT **Assignment No 01** **Submitted by:** **Zainab Latif** **Submitted to:** **Prof. Usama** **Course code:** COSC-2112 **Course title:** **Artificial Intelligence** **Department:** **ADP(CS)** ***TOPIC:*** ***Comprehensive Comparison of Uninformed Search Strategies :*** *Uniformed...

KFUEIT **Assignment No 01** **Submitted by:** **Zainab Latif** **Submitted to:** **Prof. Usama** **Course code:** COSC-2112 **Course title:** **Artificial Intelligence** **Department:** **ADP(CS)** ***TOPIC:*** ***Comprehensive Comparison of Uninformed Search Strategies :*** *Uniformed search strategies are basic algorithms used in AI and problem-solving tasks where no specific* *domain knowledge (heuristics) about the search space is used. They explore paths in a systematic way to* *find the optimal solution. Here's a comprehensive comparison of the main uniformed search strategies:* ***Breadth-First Search (BFS)**, **Uniform Cost Search (UCS)**, **Depth-First Search (DFS)**, and **Depth-Limited*** ***Search (DLS)**.* ***Breadth-First Search (BFS)*** ***Principle**: BFS is based on exploring the search space level by level, ensuring that nodes* *are expanded in order of their depth from the root. It prioritizes nodes with the fewest* *steps taken from the start, effectively minimizing the \"distance\" traveled from the starting* *point.* ***How it operates**:* *1. BFS uses a **queue** data structure, which operates on a First-In-First-Out (FIFO)* *basis.* *2. Starting with the root (initial state), BFS adds all its immediate neighbors to the* *queue.* *3. Nodes are dequeued and expanded one level at a time; after expanding a node, all* *unvisited successors are enqueued.* *4. This process continues until a goal node is found or the queue is empty.* ***Optimality and Completeness**: BFS is both complete (if a solution exists, it will be found)* *and optimal when each action has the same cost, as it finds the shortest path in terms of* *the number of steps from the root.* ***Complexity**:* o ***Time Complexity**: O(b\^d), where b is the branching factor and dd is the depth of* *the shallowest solution.* o ***Space Complexity**: O(b\^d) as BFS needs to store all nodes at each level, which* *can be memory-intensive for large trees.* ***2. Depth-First Search (DFS)*** ***Principle**: DFS explores each branch of the search tree as deeply as possible before* *backtracking. It is useful for searches where memory is a constraint, as it only keeps* *track of nodes on the current path.* ***How it operates**:1. DFS uses a **stack** (or recursion) to explore the search space, operating on a Last* *In-First-Out (LIFO) basis.* *2. It starts at the root, adding all unexplored neighbors to the stack.* *3. Nodes are popped from the stack and expanded, pushing each successor onto t* *stack until reaching a goal node or encountering a dead end.* *4. When a dead end is encountered, DFS backtracks to the most recent unvisited* *node on the path.* ***Optimality and Completeness**: DFS is neither complete (it may get stuck in an infinite* *branch) nor optimal (it does not guarantee the shortest or least-cost path).* ***Complexity**:* o ***Time Complexity**: O(b\^m) where mmm is the maximum depth of the search space.* o ***Space Complexity**: O(b×m), as DFS only stores nodes along the current path,* *making it more space-efficient than BFS.* ***3. Uniform Cost Search (UCS)*** ***Principle**: UCS generalizes BFS by considering the path cost associated with each node,* *ensuring that nodes are expanded in increasing order of path cost. It's optimal for* *finding the least-cost path when costs vary.* ***How it operates**:* *1. UCS uses a **priority queue** to keep track of nodes, ordered by their path cost from* *the start node.* *2. Starting from the root, UCS expands the least-cost node, updating the queue with* *new nodes and their cumulative path costs.* ***Optimality and Completeness**: UCS is both complete (if the branching factor is finite and* *all path costs are positive) and optimal, as it guarantees finding the least-cost solution.* ***Complexity**:* o ***Time Complexity**: O(bC∗/ε) where C\^\*is the cost of the optimal solution and ε is* *the minimum action cost.* o ***Space Complexity**: Similar to time complexity, as UCS stores all frontier nodes,* *which can be large for high-cost solutions.* ***Depth-Limited Search (DLS)*** ***Principle**: DLS is a variant of DFS that limits the depth of the search. It is useful in cases* *where infinite paths or excessively deep paths could cause DFS to loop indefinitely.* ***How it operates**:* *1. DLS uses a depth limit lll and applies DFS up to that limit, stopping expansion of* *nodes that exceed this depth.* *2. It operates similarly to DFS but with a condition that nodes beyond depth lll are* *not expanded.* ***Optimality and Completeness**: DLS is complete if the goal exists within the depth limit* *lll, but it is not optimal as it may not return the shortest path.* ***Complexity**:* o ***Time Complexity**: O(b\^l) where lll is the depth limit.* o ***Space Complexity**: O(b×l), similar to DFS, as it only stores nodes up to the depth* *limit.* ***5. Iterative Deepening Search (IDS)*** ***Principle**: IDS combines the advantages of BFS's completeness with DFS's space* *efficiency by incrementally deepening the depth limit until a solution is found. It* *effectively performs multiple depth-limited searches with increasing limits.* ***How it operates**:* *1. IDS begins with a depth limit of 0, conducting a depth-limited search.* *2. This continues until a goal node is found within a given depth.* ***Optimality and Completeness**: IDS is both complete and optimal if each action cost is* *uniform. It finds the shallowest solution without requiring extensive memory.* ***Complexity**:* o ***Time Complexity**: O(b\^d) similar to BFS, as it examines each depth level* *incrementally.* o ***Space Complexity**: O(b×d), more memory-efficient than BFS.* ***6. Bidirectional Search*** ***Principle**: Bidirectional search attempts to reduce search time by simultaneously* *searching forward from the start node and backward from the goal, aiming to meet in the* *middle.* ***How it operates**:* *1. Two searches are conducted: one forward from the start and one backward from* *the goal.* *2. The two search frontiers can use either BFS, UCS, or other suitable methods* *depending on path cost considerations.* ***Optimality and Completeness**: Bidirectional search is complete and optimal if BFS or* *UCS is used in both directions with consistent costs.* ***Complexity**:* o ***Time Complexity**: O(bd/2), as it effectively halves the search depth, reducing the* *number of nodes expanded.* o ***Space Complexity**: O(bd/2) for both frontiers, which can still be memory* *intensive but is generally more efficient than BFS alone.* ***comparison Criteria for Uninformed Search Strategies**ompare each uninformed search strategy in terms of **completeness**, **optimality**, **time complexity**,* *and **space complexity**.* ***1. Breadth-First Search (BFS)*** ***Completeness**: BFS is complete if the branching factor is finite, as it will eventually* *explore all nodes at each level.* ***Optimality**: BFS is optimal if each step has an equal cost because it finds the shallowest* *solution first.* ***Time Complexity**: O(b\^d) where bbb is the branching factor and ddd is the depth of the* *shallowest solution. As ddd increases, BFS becomes more time-intensive.* ***Space Complexity**: O(b\^d)OBFS stores all nodes at each depth level in memory, which is* *space-intensive and limits its practicality for deeper search trees or large graphs.* ***2. Depth-First Search (DFS)*** ***Completeness**: DFS is not complete for infinite or cyclic search spaces, as it may get* *stuck in an endless path. It is complete for finite spaces or if a depth limit is applied.* ***Optimality**: DFS is not optimal because it does not necessarily find the shortest or least* *cost solution.* ***Time Complexity**: O(b\^m) where mmm is the maximum depth of the search space. DFS* *explores as deep as possible, potentially expanding all nodes.* ***Space Complexity**: O(b×m), since DFS only needs to store the current path and some* *backtracking information. This space efficiency is an advantage for deep search spaces* ***3. Uniform Cost Search (UCS)*** ***Completeness**: UCS is complete if the branching factor is finite and all step costs are* *positive, ensuring it eventually finds a goal.* ***Optimality**: UCS is optimal, as it expands nodes in increasing order of path cost,* *ensuring the least-cost path to a solution.* ***Time Complexity**: O(bC∗/ε), where C\^\* is the cost of the optimal solution and ε is the* *minimum step cost. UCS may explore many nodes with costs lower than C\^\* but not* *leading to the goal, making it slower than BFS in some cases.* ***Space Complexity**: Similar to time complexity; UCS must store all frontier nodes in* *memory.**4. Depth-Limited Search (DLS)*** ***Completeness**: DLS is complete if the solution exists within the specified depth limit lll.* ***Optimality**: DLS is not optimal, as it may return a solution that is not the shortest or least* *costly.* ***Time Complexity**: O(b\^l)Owhere lll is the depth limit. This time complexity depends on* *the depth limit rather than the depth of the solution.* ***Space Complexity**: O(b×l), similar to DFS, as it only stores nodes along the current path* *up to depth lll.* ***5. Iterative Deepening Depth-First Search (IDDFS)*** ***Completeness**: IDDFS is complete for finite branching factors and finite solution depths,* *as it incrementally deepens the search.* ***Optimality**: IDDFS is optimal if all steps have equal costs, as it explores shallow* *solutions first.* ***Time Complexity**: O(b\^d), where d is the depth of the shallowest solution. Although* *IDDFS re-explores nodes, the exponential nature of the tree means the repeated work is* *limited.* ***Space Complexity**: O(b×d), as it only stores nodes along the current path up to depth* *ddd. This makes it more memory-efficient than BFS.* ***6. Bidirectional Search*** ***Completeness**: Bidirectional search is complete if the branching factor is finite and both* *forward and backward searches have a solution in their reachable space.* ***Optimality**: Bidirectional search is optimal if BFS or UCS is used in both directions and* *action costs are uniform or non-negative.* ***Time Complexity**: O(bd/2), where d is the depth of the solution. By halving the search* *depth, bidirectional search is often faster than BFS.* ***Space Complexity**: O(bd/2) for each frontier, as it requires two searches with half the* *depth, effectively reducing memory usage compared to BFS.* ***Case Study Example: Finding the Shortest Path in a Graph*** *Consider a problem where we need to find the shortest path in an unweighted grid from a* *starting node SSS to a goal node GGG. Nodes represent locations, and edges represent possible* *moves (up, down, left, right) with equal costs.* ***Applying Each Algorithm**1. **BFS**: BFS will explore nodes level-by-level, ensuring the shortest path in terms of steps* *from SSS to GGG. It will expand all neighbors of each node in the queue until it reaches* *GGG, resulting in the shortest path due to equal costs.* *2. **DFS**: DFS will go deep along one path until it hits a dead end or reaches GGG. If the* *solution is deep, DFS may be efficient, but it risks exploring irrelevant paths that do not* *lead to GGG.* *3. **UCS**: Since the grid is unweighted, UCS behaves similarly to BFS in this example, as* *each edge cost is the same. It will explore the path with the fewest steps and return the* *shortest path if all edge costs are equal.* *4. **DLS**: DLS would apply DFS up to a depth limit. If we set the depth limit too low, it may* *miss the solution; if too high, it may unnecessarily explore deep, irrelevant paths, making* *it less efficient.* *5. **IDDFS**: IDDFS would incrementally explore the grid by gradually increasing the depth* *limit. It combines the completeness of BFS* *with DFS's memory efficiency, eventually* *finding the shortest path if it exists.* *6. **Bidirectional Search**: Bidirectional search would initiate a search from SSS and GGG* *simultaneously, aiming to meet in the middle. This strategy significantly reduces the* *nodes explored, leading to faster pathfinding in large graphs.* *Each algorithm brings a unique approach, and the choice depends on the problem constraints,* *such as memory limits and the need for an optimal solution.* ***Strengths and Weaknesses Summary*** ***Breadth-First Search (BFS)*** ***Strengths**: Guarantees finding the shortest path in unweighted graphs.* ***Weaknesses**: Uses a lot of memory and can be slow for deep searches.* ***When to Use**: Choose BFS if the solution is close to the start, or you need the shortest* *path in a shallow or unweighted search space.* ***2. Depth-First Search (DFS)*** ***Strengths**: Uses little memory, good for deep searches.* ***Weaknesses**: Doesn't guarantee the shortest path and can get stuck in loops.* ***When to Use**: Use DFS if memory is limited, the solution is deep, and the shortest path* *isn't needed.* ***3. Uniform Cost Search (UCS)*** ***Strengths**: Guarantees finding the lowest-cost path if costs vary.* ***Weaknesses**: Can be slow and memory-heavy, especially if the costs are similar to each* *other.* ***When to Use**: Choose UCS if you need the lowest-cost path and can handle high memory* *use.* ***4. Depth-Limited Search (DLS)*** ***Strengths**: Similar to DFS but avoids looping forever by setting a depth limit.* ***Weaknesses**: May miss the solution if the depth limit is set too low; doesn't guarantee the* *shortest path.* ***When to Use**: Use DLS in deep search spaces if you have an idea of the solution's depth* *but don't need the shortest path.* ***5. Iterative Deepening Depth-First Search (IDDFS)*** ***Strengths**: Uses less memory than BFS but still finds the shortest path if costs are equal.* ***Weaknesses**: Slightly slower than BFS due to repeated searching, but this is manageable.* ***When to Use**: Best for deep search spaces when memory is limited, and the shortest path* *is required in unweighted graphs.* ***6. Bidirectional Search*** ***Strengths**: Cuts search time by searching from both the start and goal.* - ***Weaknesses**: Uses a lot of memory for two search frontiers; needs a defined goal.* ***When to Use**: Choose bidirectional search for large search spaces when you know the* *goal and can store both search paths.*