DS161 Introduction to Data Science & Artificial Intelligence

Lecture 2

Problem Solving using State-Space Search I

Krishnendu Ghosh

Problem Formulation

• Problem formulation is the process of deciding what actions and states to consider, given a goal.

​

• The process of looking for a sequence of actions that reaches the goal is called search.

​

• A search algorithm takes a problem as input and returns a solution in the form of an action sequence.

Problem Formulation

A problem can be defined formally by five components:

• The initial state that the agent starts in.
• A description of the possible actions available to the agent. Given a particular states, ACTIONS(s) returns the set of actions that can be executed in s.
• A description of what each action does; the formal name for this is the transition model, specified by a function RESULT(s,a) that returns the state that results from doing action a in state s. We also use the term successor to refer to any state reachable from a given state by a single action.
• Together, the initial state, actions, and transition model implicitly define the state space of the problem—the set of all states reachable from the initial state by any sequence of actions. A path in the state space is a sequence of states connected by a sequence of actions.
• The goal test, which determines whether a given state is a goal state

Toy Problem: Vacuum World

Toy Problem: Vacuum World

• States: The state is determined by both the agent location and the dirt locations. The agent is in one of two locations, each of which might or might not contain dirt. Thus, there are 2 × 2 2 = 8 possible world states. A larger environment with n locations has n · 2 n states.
• Initial state: Any state can be designated as the initial state.
• Actions: In this simple environment, each state has just three actions: Left, Right, and Suck. Larger environments might also include Up and Down.
• Transition model: The actions have their expected effects, except that moving Left in the leftmost square, moving Right in the rightmost square, and Sucking in a clean square have no effect.
• Goal test: This checks whether all the squares are clean.
• Path cost: Each step costs 1, so the path cost is the number of steps in the path.

Uninformed Search

The term uninformed/blind search means that the strategies have no additional information about states beyond that provided in the problem definition.

​

​

​

Uninformed Search

Breadth-First Search

Breadth-first search is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. In general, all the nodes are expanded at a given depth in the search tree before any nodes at the next level are expanded.

​

​

​

​

​

Breadth-First Search

Breadth-first search is an instance of the general graph-search algorithm in which the shallowest unexpanded node is chosen for expansion. This is achieved very simply by using a FIFO queue for the frontier. Thus, new nodes go to the back of the queue, and old nodes, which are shallower than the new nodes, get expanded first.

​

​

​

​

Breadth-First Search

Breadth-First Search

Advantages:

1. BFS will provide a solution if any solution exists.
2. If there are more than one solutions for a given problem, then BFS will provide the minimal solution which requires the least number of steps.
3. It also helps in finding the shortest path in goal state, since it needs all nodes at the same hierarchical level before making a move to nodes at lower levels.
4. It is also very easy to comprehend with the help of this we can assign the higher rank among path types.

​

​

​

​

​

Breadth-First Search

Disadvantages:

• It requires lots of memory since each level of the tree must be saved into memory to expand the next level.
• BFS needs lots of time if the solution is far away from the root node.
• It can be very inefficient approach for searching through deeply layered spaces, as it needs to thoroughly explore all nodes at each level before moving on to the next

​

​

​

​

​

Breadth-First Search

Completeness: Yes

We can easily see that it is complete—if the shallowest goal node is at some finite depth d, breadth-first search will eventually find it after generating all shallower nodes (provided the branching factor b is finite).

​

​

​

​

​

Breadth-First Search

Optimality: No

As soon as a goal node is generated, we know it is the shallowest goal node because all shallower nodes must have been generated already and failed the goal test. Now, the shallowest goal node is not necessarily the optimal one; technically, breadth-first search is optimal if the path cost is a nondecreasing function of the depth of the node. The most common such scenario is that all actions have the same cost.

Breadth-First Search

Time complexity: O(b^d)

Imagine searching a uniform tree where every state has b successors.

The root of the search tree generates b nodes at the first level, each of which generates b more nodes, for a total of b^2 at the second level. Each of these generates b more nodes, yielding b^3 nodes at the third level, and so on. Now suppose that the solution is at depth d. In the worst case, it is the last node generated at that level. Then the total number of nodes generated is

b + b^2 + b^3 + · · · + b^d = O(b^d) .

​

Breadth-First Search

Space complexity: O(b^d)

As for space complexity: for any kind of graph search, which stores every expanded node in the explored set, the space complexity is always within a factor of b of the time complexity. For breadth-first graph search in particular, every node generated remains in memory. There will be O(b^(d−1)) nodes in the explored set and O(b^d) nodes in the frontier, so the space complexity is O(b^d), i.e., it is dominated by the size of the frontier. Switching to a tree search would not save much space, and in a state space with many redundant paths, switching could cost a great deal of time.

​

​

​

​

​

​

Breadth-First Search

An exponential complexity bound such as O(b^d) is scary.

​

​

​

​

​

​

Breadth-First Search

Memory requirement is a bigger problem for breadth-first search than is the execution time. One might wait 13 days for the solution to an important problem with search depth 12, but no personal computer has the petabyte of memory it would take. Fortunately, other strategies require less memory.

Time is a major factor. If your problem has a solution at depth 16, then it will take about 350 years for breadth-first search to find it. In general, exponential-complexity search problems cannot be solved by uninformed methods for any but the smallest instances.

​

​

​

​

​

​

​

Depth-First Search

Depth-first search always expands the deepest node in the current frontier of the search tree. The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. As those nodes are expanded, they are dropped from the frontier, so then the search “backs up” to the next deepest node that still has unexplored successors.

Depth-First Search

The depth-first search algorithm is an instance of the graph-search algorithm. Whereas breadth-first search uses a FIFO queue, depth-first search uses a LIFO queue. A LIFO queue means that the most recently generated node is chosen for expansion. This must be the deepest unexpanded node because it is one deeper than its parent—which, in turn, was the deepest unexpanded node when it was selected.

As an alternative to the GRAPH-SEARCH style implementation, it is common to implement depth-first search with a recursive function that calls itself on each of its children in turn.

​

​

​

​

​

​

​

​

Depth-First Search

​

​

​

​

​

​

​

​

Depth-First Search

The properties of depth-first search depend on: the graph-search or tree-search version.

The graph-search version, which avoids repeated states and redundant paths, is complete in finite state spaces because it will eventually expand every node.

The tree-search version, on the other hand, is not complete.

Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node; this avoids infinite loops in finite state spaces but does not avoid the proliferation of redundant paths. In infinite state spaces, both versions fail if an infinite non-goal path is encountered.

​

​

​

​

​

​

​

​

Depth-First Search: What is Tree Search?

​

Tree search treats the state space as a tree, even if the underlying problem is actually a graph.

• Does NOT remember visited states
• Same state can appear multiple times
• Assumes no cycles or ignores them

How it works

• Start from the initial state
• Expand a node by generating all its children
• Add children to the frontier
• Goal test is applied to newly generated nodes

Depth-First Search: What is Graph Search?

​

Graph search treats the state space as a graph, explicitly handling repeated states and cycles.

• Maintains an explored (closed) set
• Avoids revisiting the same state
• Guarantees termination (if solution exists)

How it works

• Start from initial state
• Maintain:
• Frontier (open list)
• Explored set (visited states)
• Before adding a node:
• Check if state is already explored or in frontier
• Goal test is applied when a node is selected for expansion

Depth-First Search

Advantage:

1. DFS requires very less memory as it only needs to store a stack of the nodes on the path from root node to the current node.
2. It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right path).
3. With the help of this we can stores the route which is being tracked in memory to save time as it only needs to keep one at a particular time.

​

Depth-First Search

Disadvantage:

• There is the possibility that many states keep reoccurring, and there is no guarantee of finding the solution.
• DFS algorithm goes for deep down searching and sometime it may go to the infinite loop.
• The depth-first search (DFS) algorithm does not always find the shortest path to a solution.

​

Depth-First Search

Optimality:

For similar reasons, both versions are nonoptimal.

For example, in the figure, depth-first search will explore the entire left subtree even if node C is a goal node. If node J were also a goal node, then depth-first search would return it as a solution instead of C, which would be a better solution; hence, depth-first search is not optimal.

Depth-First Search

Time Complexity:

Time complexity of depth-first graph search is bounded by the size of the state space (which may be infinite, of course).

A depth-first tree search, on the other hand, may generate all of the O(b^m) nodes in the search tree, where m is the maximum depth of any node; this can be much greater than the size of the state space.

Note that m itself can be much larger than d (the depth of the shallowest solution) and is infinite if the tree is unbounded.

​

​

​

​

​

​

​

​

Depth-First Search

Space Complexity:

For a graph search, there is no advantage, but a depth-first tree search needs to store only a single path from the root to a leaf node, along with the remaining unexpanded sibling nodes for each node on the path. Once a node has been expanded, it can be removed from memory as soon as all its descendants have been fully explored.

For a state space with branching factor b and maximum depth m, depth-first search requires storage of only O(bm) nodes. This has led to the adoption of depth-first tree search as the basic workhorse of many areas of AI.

​

​

​

​

​

​

​

​

Depth-First Search

BFS requires O(bᵈ) space because it stores all nodes at the deepest frontier, whereas DFS requires only O(bd) space since it stores a single path from root to leaf along with unexpanded siblings.

BFS expands the search level by level.

• At depth 0 → 1 node
• At depth 1 → b nodes
• At depth 2 → b² nodes
• At depth d → bᵈ nodes

At any moment, DFS stores:

• The current path from root to leaf → at most d nodes
• The unexplored siblings at each level → at most (b − 1) per level

Depth-First Search

A variant of depth-first search called backtracking search uses still less memory.

In backtracking, only one successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next. In this way, only O(m) memory is needed rather than O(bm).

Backtracking search facilitates yet another memory and time-saving trick: the idea of generating a successor by modifying the current state description directly rather than copying it first. This reduces the memory requirements to just one state description and O(m) actions. For this to work, we must be able to undo each modification when we go back to generate the next successor. For problems with large state descriptions, such as robotic assembly, these techniques are critical to success.

​

​

​

​

​

​

​

​

Depth-Limited Search

The embarrassing failure of depth-first search in infinite state spaces can be alleviated by supplying depth-first search with a predetermined depth limit l. That is, nodes at depth l are treated as if they have no successors. This approach is called depth-limited search.

​

Depth-first search can be viewed as a special case of depth-limited search with l = ∞.

​

​

​

​

Depth-Limited Search

Depth-limited search can be implemented as a simple modification to the general tree or graph-search algorithm.

Alternatively, it can be implemented as a simple recursive algorithm.

Note: Depth-limited search can terminate with two kinds of failure: the standard failure value indicates no solution; the cutoff value indicates no solution within the depth limit.

​

​

​

Depth-Limited Search

​

​

​

​

Depth-Limited Search

Advantages:

1. Depth-Limited Search will restrict the search depth of the tree, thus, the algorithm will require fewer memory resources than the straight BFS (Breadth-First Search) and IDDFS (Iterative Deepening Depth-First Search). After all, this implies automatic selection of more segments of the search space and the consequent why consumption of the resources. Due to the depth restriction, DLS omits a predicament of holding the entire search tree within memory which contemplatively leaves room for a more memory-efficient vice for solving a particular kind of problems.
2. When there is a leaf node depth which is as large as the highest level allowed, do not describe its children, and then discard it from the stack.
3. Depth-Limited Search does not explain the infinite loops which can arise in classical when there are cycles in graph of cities.

​

​

​

​

​

Depth-Limited Search

Disadvantages:

• Depth-limited search also has a disadvantage of incompleteness.
• It may not be optimal if the problem has more than one solution.
• The effectiveness of the Depth-Limited Search (DLS) algorithm is largely dependent on the depth limit specified. If the depth limit is set too low, the algorithm may fail to find the solution altogether.

​

​

​

​

​

Depth-Limited Search

Completeness:

It introduces an additional source of incompleteness if we choose l < d, that is, the shallowest goal is beyond the depth limit.

Optimality:

Depth-limited search is nonoptimal if we choose l > d.

Time-Complexity:

Its time complexity is O(b^l)

Space-Complexity:

Its space complexity is O(bl).

​

​

​

​

Depth-Limited Search

How to choose Depth Limit?

Depth limits can be based on knowledge of the problem.

For example, on the map of Romania there are 20 cities. Therefore, we know that if there is a solution, it must be of length 19 at the longest, so l = 19 is a possible choice.

But in fact if we studied the map carefully, we would discover that any city can be reached from any other city in at most 9 steps. This number, known as the diameter of the state space, gives us a better depth limit, which leads to a more efficient depth-limited search.

For most problems, however, we will not know a good depth limit until we have solved the problem.

​

​

​

​

Iterative Deepening Depth-First Search

Iterative deepening depth-first search is a strategy that finds the best depth limit. It does this by gradually increasing the limit—first 0, then 1, then 2, and so on—until a goal is found. This will occur when the depth limit reaches d, the depth of the shallowest goal node.

​

​

​

​

​

Iterative Deepening Depth-First Search

Iterative Deepening Depth-First Search

Iterative deepening combines the benefits of depth-first and breadth-first search. Like depth-first search, its memory requirements are modest: O(bd) to be precise. Like breadth-first search, it is complete when the branching factor is finite and optimal when the path cost is a nondecreasing function of the depth of the node.

​

​

​

​

Iterative Deepening Depth-First Search

Advantages:

1. It combines the benefits of BFS and DFS search algorithm in terms of fast search and memory efficiency.
2. It is a type of straightforward which is used to put into practice since it builds upon the conventional depth-first search algorithm.
3. It is a type ofsearch algorithm which provides guarantees to find the optimal solution, as long as the cost of each edge in the search space is the same.
4. It is a type ofcomplete algorithm, and the meaning of this is it will always find a solution if one exists.
5. The Iterative Deepening Depth-First Search (IDDFS) algorithm uses less memory compared to Breadth-First Search (BFS) because it only stores the current path in memory, rather than the entire search tree.

Iterative Deepening Depth-First Search

Disadvantages:

• The main drawback of IDDFS is that it repeats all the work of the previous phase.

Iterative Deepening Depth-First Search

Iterative deepening search may seem wasteful because states are generated multiple times.

It turns out this is not too costly. The reason is that in a search tree with the same branching factor at each level, most of the nodes are in the bottom level, so it does not matter much that the upper levels are generated multiple times. In an iterative deepening search, the nodes on the bottom level are generated once, those on the next-to-bottom level are generated twice, and so on, up to the children of the root, which are generated d times.

Iterative Deepening Depth-First Search

So the total number of nodes generated in the worst case is:

N(IDS) = (d)b + (d−1)b^2 + · · · + (1)b^d = O(b^d), asymptotically same as breadth-first search

There is some extra cost for generating the upper levels multiple times, but it is not large.

For example, if b = 10 and d = 5, the numbers are

N (IDS) = 50 + 400 + 3, 000 + 20, 000 + 100, 000 = 123, 450

N (BFS) = 10 + 100 + 1, 000 + 10, 000 + 100, 000 = 111, 110 .

​

​

Iterative Deepening Depth-First Search

If you are really concerned about repeating the repetition, you can use a hybrid approach that runs breadth-first search until almost all the available memory is consumed, and then runs iterative deepening from all the nodes in the frontier.

In general, iterative deepening is the preferred uninformed search method when the search space is large and the depth of the solution is not known.

​

​

​

​

Iterative Deepening Depth-First Search

Iterative deepening search is analogous to breadth-first search in that it explores a complete layer of new nodes at each iteration before going on to the next layer.

​

It would seem worthwhile to develop an iterative analog to uniform-cost search, inheriting the latter algorithm’s optimality guarantees while avoiding its memory requirements. The idea is to use increasing path-cost limits instead of increasing depth limits.

​

The resulting algorithm, called iterative lengthening search. It turns out, unfortunately, that iterative lengthening incurs substantial overhead compared to uniform-cost search.