Task 1: Search Algorithms
1. Do some background research on the search algorithms and methods we have
looked at today and produce a scenario where each one might be used and a set of
pros and cons for each of them.
Search algorithms are crucial components in Artificial Intelligence. This post will delve into
various AI search algorithms, detailing their importance in solving problems. In AI, rational or
problem-solving agents often employ these search techniques or algorithms to find the best
solution. These agents, aiming to achieve goals using atomic representation, are known as goal-
based agents. We will explore different search methods for problem-solving in this topic.
Terminologies in Search Algorithms:
Search: A systematic process to solve a search problem within a given search space. A
search problem typically involves three main elements:
Search Tree: A tree structure representing a search problem, with the root node
corresponding to the initial state.
Actions: Describes all possible actions available to the agent.
Transition Model: Details what each action accomplishes, represented as a transition
model.
Path Cost: A function assigning a numerical cost to each path.
Solution: An action sequence leading from the start node to the goal node.
Optimal Solution: A solution with the lowest cost among all possible solutions.
Properties of Search Algorithms:
The effectiveness of search algorithms can be evaluated based on four key properties:
Completeness: A search algorithm is complete if it guarantees finding a solution for any
given input.
Optimality: An algorithm is considered optimal if it guarantees the best (lowest cost)
solution among all possible solutions.
Time Complexity: The time required for an algorithm to complete a task.
Space Complexity: The maximum storage capacity required at any point during the
search, as dictated by the problem's complexity.
Uninformed/Blind Search
Uninformed search, also known as blind search, operates without any prior knowledge of the
search space, such as the location of the goal or proximity to it. It only includes basic instructions
on how to traverse the search tree and identify leaf and goal nodes, often using a brute-force
approach. This type of search methodically explores every node in the tree until it reaches the
goal node. Uninformed search methods can be classified into five main types:
Breadth-First Search (BFS)
Uniform Cost Search (UCS)
Depth-First Search (DFS)
Iterative Deepening Depth-First Search (IDDFS)
Bidirectional Search
Example of Search Algorithm
A Tree Search:* A* Tree Search, commonly known as A* Search, merges the strengths of
uniform-cost search and greedy search. In this algorithm, the heuristic is the sum of the cost used
in UCS, represented by g(x)g(x)g(x), and the cost used in greedy search, represented by
h(x)h(x)h(x). The total cost is denoted as f(x)f(x)f(x).
Heuristic: Key points regarding heuristics in A* Search:
h(x)h(x)h(x) represents the estimated cost to reach the goal from the current node, also
known as the forward cost.
g(x)g(x)g(x) represents the cumulative cost from the root node to the current node,
known as the backward cost.
A* Search is optimal if, for all nodes, the forward cost h(x)h(x)h(x) underestimates the
actual cost h∗(x)h^*(x)h∗(x) to reach the goal. This characteristic is known as
admissibility.
Admissibility: For A* Search to be admissible, the heuristic h(x)h(x)h(x) must always be less
than or equal to the true cost h∗(x)h^*(x)h∗(x) from the current node to the goal.
Strategy: Select the node with the lowest f(x)f(x)f(x) value for expansion.
Example:
Question. Find the path to reach from S to G using A* search.
Solution. Starting from S, the algorithm computes g(x) + h(x) for all nodes in the fringe at
each step, choosing the node with the lowest sum. The entire work is shown in the table
below.
Note that in the fourth set of iteration, we get two paths with equal summed cost f(x), so we
expand them both in the next set. The path with a lower cost on further expansion is the chosen
path.
Path h(x) g(x) f(x)
S 7 0 7
S -> A 9 3 12
S -> D 5 2 7
S -> D -> B 4 2+1=3 7
S -> D -> E 3 2+4=6 9
S -> D -> B -> C 2 3+2=5 7
S -> D -> B -> E 3 3+1=4 7
S -> D -> B -> C -> G 0 5+4=9 9
S -> D -> B -> E -> G 0 4+3=7 7
Path: S->D->B->E->G
Cost: 7
Greedy Search: In greedy search, we expand the node closest to the goal node. The
“closeness” is estimated by a heuristic h(x).
Heuristic: A heuristic h is defined as h(x) = Estimate of distance of node x from the goal node.
Lower the value of h(x), closer is the node from the goal.
Strategy: Expand the node closest to the goal state, i.e. expand the node with a lower h value.
Example:
Question. Find the path from S to G using greedy search. The heuristic values h of each node
below the name of the node.
Solution. Starting from S, we can traverse to A (h=9) or D (h=5). We choose D, as it has the
lower heuristic cost. Now from D, we can move to B (h=4) or E (h=3). We choose E with a
lower heuristic cost. Finally, from E, we go to G (h=0). This entire traversal is shown in the
search tree below, in blue.
Path: S -> D -> E -> G
Breadth-First Search (BFS)
Advantages of BFS:
1. BFS is guaranteed to find a solution if one exists.
2. It avoids getting stuck in dead ends, meaning it doesn't waste time on unproductive
nodes.
3. When multiple solutions exist, BFS will find the one with the fewest steps.
Disadvantages of BFS:
1. It requires significant memory as it stores all nodes at the current depth level before
moving to the next level.
2. It can be time-consuming if the solution is located deep within the graph.
Applications of BFS:
1. Determining the shortest path.
2. Checking graph for bipartiteness.
3. Implementing Cheney's Algorithm for copying garbage collection.
Depth-First Search (DFS)
Advantages of DFS:
1. It has a linear memory requirement relative to the number of nodes.
2. It generally has lower time and space complexity compared to BFS.
3. It can find a solution without extensive searching.
Disadvantages of DFS:
1. It does not guarantee a solution will be found.
2. The limited cutoff depth can increase time complexity.
3. Determining the depth limit can be challenging until the search has advanced.
Applications of DFS:
1. Identifying connected components in a graph.
2. Performing topological sorting.
3. Finding bridges within a graph.
