Problem Solving and Uninformed

Search Strategies
By Prithiviraj N
Problem Solving Agents
● Intelligent agents are supposed to maximize their performance measure.
● Goals help organize behavior by limiting the objectives that the agent is trying to achieve. Goal formulation,
based on the current situation and the agent's performance measure, is the first step in problem solving.
● The agent's task is to find out which sequence of actions will get it to a goal state. Before it can do this, it
needs to decide what sorts of actions and states to consider.Problem formulation is the process of deciding
what actions and states to consider, given a goal.
● the agent will not know which of its possible actions is best, because it does not know enough about the
state that results from taking each action. If the agent has no additional knowledge, then it is stuck. The best
it can do is choose one of the actions at random.
● an agent with several immediate options of unknown value can decide what to do by jrst examining different
possible sequences of actions that lead to states of known value, and then choosing the best sequence.
● This process of looking for such a sequence is called search. A search algorithm takes a problem as input
and returns a solution in the form of an action sequence. Once a solution is found, the actions it recommends
can be carried out. This is called the execution phase.
a “problem-solving agent” works in simple environments, using some key assumptions to make things easier. Let’s break
it down:

1. Static Environment:
The agent assumes the world doesn’t change while it is thinking or solving the problem. This makes planning simpler
because it doesn’t have to keep checking for updates in the environment.

2. Known Initial State:

3. Discrete Choices:
The agent assumes that actions and outcomes can be listed as distinct options. For example, it can move left, right, up,
or down, with no confusion about what those actions mean.

4. Deterministic World:
The agent assumes its actions have predictable results. For instance, if it decides to move forward, it expects to end up
exactly where it planned, with no surprises.

5. Open-Loop System:
The agent doesn’t “watch” or adjust while executing its plan—it follows the plan blindly, trusting that everything will go as
expected. This is like driving with your eyes closed, assuming nothing will change on the road!
Why are these assumptions useful?
These assumptions simplify the environment, making it easier for the agent to plan and act. It works for simple problems,
but it may not handle unexpected changes or uncertainties in the environment.
Well defined problems and solutions
A problem can be defined formally by four components:

1. The initial state that the agent starts in

2. A description of the possible actions available to the agent. The most common for- mulation3 uses a successor
function. Given a particular state x, SUCCESSOR-FN(x) returns a set of (action, successor) ordered pairs, where each
action is one of the legal actions in state x and each successor is a state that can be reached from x by applying
the action

3. The initial state and successor function implicitly define the state space of the problem-the set of all states reachable
from the initial state. The state space forms a graph in which the nodes are states and the arcs between nodes are
actions.A path in the state space is a sequence of states connected by a sequence of actions.

4. The goal test, which determines whether a given state is a goal state

5. A path cost function that assigns a numeric cost to each path. The problem-solving agent chooses a cost function that
reflects its own performance measure. The step cost of taking action a to go from state x to state y is denoted by c(x,
a , y).

A solution to a problem is a path from the initial state to a goal state. Solution quality is measured by the path cost function,
and an optimal solution has the lowest path cost among all solutions.
● The process of removing detail from a representation is called abstraction.
● The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem;
in this case they are easy enough that they can be carried out without further search or planning by an
average driving agent. The choice of a good abstraction thus involves removing as much detail as possible
while retaining validity and ensuring that the abstract actions are easy to carry out.
● The abstraction is valid if we can expand any abstract solution into a solution in the more detailed world
Uninformed Search Strategies
● Uninformed search is also called as blind search

● The term means that they have no additional information about states beyond that provided in the
problem definition. All they can do is generate successors and distinguish a goal state from a nongoal
state.

● Strategies that know whether one non-goal state is "more promising" than another are called
informed search or heuristic search strategies
Breadth First Search
What is Breadth-First Search?
BFS is a method used to explore or search through data structures like trees or graphs. It works by visiting all the nodes at
one level (or depth) before moving to the next level. Imagine exploring layers of a tree starting from the root, moving across
all branches at the same level, then going down to the next layer.
Key Characteristics of BFS:

1. How it Works:

• Start at the root (or initial state).

• Explore all its immediate successors (level 1).

• Then explore all the successors of those nodes (level 2), and so on.

2. Queue-Based Implementation:

• BFS uses a First-In-First-Out (FIFO) queue.

• New nodes (successors) are added to the end of the queue, ensuring that nodes closest to the start are processed
first.
 3. Complete Search:

• BFS will find a solution if one exists, as it systematically checks all possible paths starting from the shallowest (nearest)
level.

4. Optimality:

• BFS is optimal only when all steps (or transitions) have the same cost. For example, if moving from one point to
another always costs the same, BFS guarantees the shortest path.

Downsides of BFS:

1. Memory Requirements:

• BFS needs to store all nodes it generates, which can grow exponentially. For a tree where each node has b children
(branching factor) and the goal is at depth d:

• Total nodes = b^0 + b^1 + b^2 + \dots + b^d = O(b^d)

• Example: If b = 10 and d = 8, BFS might need 1 terabyte of memory, which is impractical for many computers.

2. Time Requirements:

• BFS explores every possibility at a given level before moving deeper. This means it can take a very long time for deep
solutions.

• Example: For d = 12, BFS might take 35 years to finish, even with a fast computer.
Depth First Search
What is Depth-First Search?
DFS is a search strategy that explores as deep as possible in one branch of a tree (or graph) before backtracking to explore
other branches. It’s like going down one path until it ends, then returning to try the next path.
How DFS Works:

1. Deep Exploration First:

• Start at the root node.

• Explore the deepest node you can reach.

• If you hit a dead end (no more successors), backtrack to the previous level and explore the next unexplored branch.

2. Uses a Stack:

• DFS can be implemented using a Last-In-First-Out (LIFO) queue (a stack).

• Alternatively, it can be implemented with recursion, where the function calls itself for each child node.

3. Memory Requirements:

• DFS stores only the current path and a small amount of information about unexplored branches.

• For a tree with branching factor b and maximum depth m , DFS requires storing at most b \times m + 1 nodes, which
is much smaller than BFS.
Advantages of DFS:

1. Low Memory Usage:

• DFS is efficient in terms of memory. For example, at depth d = 12 , DFS might use just 118 KB of memory compared to 10
petabytes for BFS.

2. Variants Save Even More Memory:

• Backtracking Search: Generates one successor at a time instead of all at once, requiring memory proportional to the depth
of the tree ( O(m) ).

• State Modification: Modifies the current state directly, needing memory for only one state and the actions to undo changes.
Disadvantages of DFS:

1. Can Get Stuck in Infinite Paths:

• If a tree has a branch of infinite depth, DFS may keep exploring it and never find a solution, making it incomplete.

2. Not Always Optimal:

• DFS doesn’t guarantee the shortest path. If a shallow solution exists but DFS starts exploring a deep branch, it might miss
the shallow solution.

3. Worst-Case Time Complexity:

• DFS may explore all O(b^m) nodes, where b is the branching factor and m is the maximum depth.

• Since m can be much larger than d (depth of the shallowest solution), this can be very inefficient.
Depth Limited Search
What is Depth-Limited Search?
Depth-Limited Search (DLS) is a variation of Depth-First Search (DFS) where a maximum depth l is set. Nodes beyond
this depth are treated as if they have no successors. This prevents the search from getting stuck in infinite paths.
Key Features of Depth-Limited Search:

1. Prevents Infinite Loops:

• By stopping exploration beyond a specified depth l , DLS avoids the infinite-path problem inherent in standard
DFS.

2. Depth Limit l :

• Nodes at a depth greater than l are ignored, even if they might lead to a solution.

3. Two Possible Failures:

• Standard Failure: No solution exists in the tree.

• Cutoff Failure: The solution exists but is deeper than the depth limit l .

4. Complexities:

• Time Complexity: O(b^l) , where b is the branching factor, and l is the depth limit.

• Space Complexity: O(b \cdot l) , since only one path is stored at a time.
Challenges of DLS:

1. Incompleteness for l < d :

• If the depth limit l is set too low and the solution is deeper than l , DLS will fail to find it.

2. Non-optimal for l > d :

• If the depth limit l is too high, DLS may find a deeper, non-optimal solution.

3. Choosing the Right l :

• Often, the correct depth d (the depth of the shallowest solution) is unknown, making it hard to set an appropriate limit.
Example:
Imagine searching for a city on a map:

• There are 20 cities, so the longest path between two cities could be 19 steps ( l = 19 ).

• By analyzing the map, you might notice that any city can be reached in at most 9 steps ( l = 9 ), called the diameter of the map.
Setting l = 9 will make the search more efficient.

When to Use DLS:

1. When the Problem has a Known Limit:

• If you know the maximum depth of the solution (or can estimate it), DLS is a practical option.

2. When Dealing with Infinite Trees:

• DLS is useful for problems with potentially infinite search spaces, like mazes or recursive structures.
Iterative Deepening Search
What is Iterative Deepening Search?
Iterative Deepening Search (IDS) is a combination of Depth-First Search (DFS) and Breadth-First Search (BFS). It solves the problem of choosing the
right depth limit by repeatedly performing DFS with increasing depth limits, starting from 0 and incrementing by 1 until the goal is found.
How IDS Works:

1. Start with a depth limit l = 0 .

2. Perform a depth-limited DFS.

3. If the goal is not found, increase l by 1 and repeat.

4. Continue until the goal is found or all possibilities are exhausted.

1. Complete and Optimal:

• IDS is complete for finite branching factors, meaning it will find a solution if one exists.

• It is optimal if the path cost increases with depth, like BFS.

2. Low Memory Usage:

• Like DFS, IDS requires storing only the current path and a small amount of information, making its space complexity O(b \cdot d) , where b is
the branching factor and d is the depth of the shallowest solution.

3. Efficient Despite Repetition:

• Although nodes are re-explored multiple times, this is not very costly. In a tree with branching factor b , most nodes are at the deepest level d
, and upper levels are small in comparison.
Why IDS is Efficient:

1. In a tree with branching factor b , most nodes are at the deepest level d .

2. IDS only re-explores a small number of upper-level nodes.

• Nodes at depth d : Generated once.

• Nodes at depth d-1 : Generated twice.

• Nodes at depth 0 : Generated d times.

3. Total nodes generated:

1. Large Search Space:

• Suitable for problems with large or infinite search spaces where memory is a constraint.

2. Unknown Depth of Solution:

• If the depth d of the solution is unknown, IDS is a safer choice as it incrementally explores deeper levels.
Example Problem:
Suppose you are searching for a goal node in a tree with a branching factor b = 10 and depth d = 5 :

• IDS generates approximately 111,110 nodes.

• BFS generates slightly more because it explores nodes at depth d+1 , resulting in 111,120 nodes.
Even though IDS repeats work, it avoids exploring unnecessary levels beyond d , making it more efficient.