UNIVERSITY OF THE PEOPLE
CS4408
ARTIFICIAL INTELLIGENCE
ALEJANDRO LARA (INSTRUCTOR)
DISCUSSION ASSIGNMENT 3
Depth-First Search (DFS) Implementation
Depth-First Search (DFS) is an uninformed search algorithm that explores as deep as possible
along a branch before backtracking (Russell & Norvig, 2020). In this case, starting from node
S, DFS explores one child completely before moving to the next.
DFS Traversal (assuming left-to-right order where possible):
1. Start at S
2. Move to A
3. Move to B
4. Move to E
5. Move to G (Goal reached)
DFS Path: S → A → B → E → G
DFS can be visualized in a tree structure as follows:
S
/
A
/
B
/\
E F
\
G
DFS operates in O(V + E) time complexity, where V is the number of vertices and E is the
number of edges (Korf, 1985). However, it is not guaranteed to find the shortest path in an
unweighted graph.
Breadth-First Search (BFS) Implementation
Breadth-First Search (BFS) explores all neighbors of a node before moving deeper. It uses a
queue to process nodes in layers, ensuring that the shortest path is always found in an
unweighted graph (Cormen et al., 2009).
BFS Traversal:
1. Start at S
2. Visit neighbors A, C
3. Visit neighbors B, D
4. Visit neighbors E, F
5. Visit G (Goal reached)
BFS Path: S → B → E → G (Shortest path)
BFS search tree:
S
/ \
A C
\ /\
BD F
/\
E F
\
G
BFS has the same O(V + E) time complexity as DFS but requires more memory since it
stores entire levels of nodes at once.
Comparison of DFS vs. BFS
Criteria DFS BFS
Time Complexity O(V + E) O(V + E)
Space O(V) (due to recursion
O(V) (due to queue)
Complexity stack)
No (may get stuck in infinite
Completeness Yes (always finds a solution)
depth)
No (may not find the Yes (always finds the shortest path in
Optimality
shortest path) unweighted graphs)
BFS is the preferred approach in this case because it guarantees the shortest path (S → B →
E → G), while DFS might find a longer path depending on the exploration order.
A Algorithm Solution*
The A* algorithm is an informed search technique that uses a heuristic function h(n)h(n)h(n)
and the actual cost g(n)g(n)g(n) to determine the best path (Hart, Nilsson, & Raphael, 1968).
The function is defined as:
f(n)=g(n)+h(n)f(n) = g(n) + h(n)f(n)=g(n)+h(n)
Where:
g(n)g(n)g(n) is the cost from the start node to node n.
h(n)h(n)h(n) is the estimated cost from n to the goal G.
Steps for A* search:
1. Start from S with an initial cost of 0.
2. Expand the node with the lowest f(n)f(n)f(n) value.
3. Continue expanding nodes until G is reached.
If accurate heuristic values are provided, A* is the most efficient choice as it balances path
cost and computational efficiency.
Choosing the Right Search Algorithm in AI
When selecting a search strategy for Artificial Intelligence (AI), several factors must be
considered:
Graph Structure: If the solution is deep in the search space, DFS may be inefficient
due to potential infinite loops.
Memory Constraints: BFS requires more memory than DFS since it stores an entire
level of nodes before moving deeper.
Path Optimality: If finding the shortest path is essential, BFS or A* is preferred.
Heuristic Availability: If a heuristic function can be used, A* provides the best
performance in most scenarios.
For real-world AI applications such as robotics or navigation, A is often the best choice*
because it efficiently finds the optimal path while considering dynamic costs (Hart et al.,
1968).
References:
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms
(3rd ed.). The MIT Press.
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic
determination of minimum-cost paths. IEEE Transactions on Systems Science and
Cybernetics, 4(2), 100–107.
Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search.
Artificial Intelligence, 27(1), 97–109.
Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.).
Pearson.