Artificial Intelligence: Chapter 3.3 Search Algorithms PDF

Section 3.3 Search Algorithms 71 3.3 Search Algorithms A search algorithm takes a search problem as input and returns a solution, or an indication of Search algo...

Section 3.3 Search Algorithms 71 3.3 Search Algorithms A search algorithm takes a search problem as input and returns a solution, or an indication of Search algorithm failure. In this chapter we consider algorithms that superimpose a search tree over the state- space graph, forming various paths from the initial state, trying to find a path that reaches a goal state. Each node in the search tree corresponds to a state in the state space and the edges Node in the search tree correspond to actions. The root of the tree corresponds to the initial state of the problem. It is important to understand the distinction between the state space and the search tree. The state space describes the (possibly infinite) set of states in the world, and the actions that allow transitions from one state to another. The search tree describes paths between these states, reaching towards the goal. The search tree may have multiple paths to (and thus multiple nodes for) any given state, but each node in the tree has a unique path back to the root (as in all trees). Figure 3.4 shows the first few steps in finding a path from Arad to Bucharest. The root node of the search tree is at the initial state, Arad. We can expand the node, by considering Expand Arad Sibiu Timisoara Zerind Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea Arad Sibiu Timisoara Zerind Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea Arad Sibiu Timisoara Zerind Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea Figure 3.4 Three partial search trees for finding a route from Arad to Bucharest. Nodes that have been expanded are lavender with bold letters; nodes on the frontier that have been generated but not yet expanded are in green; the set of states corresponding to these two types of nodes are said to have been reached. Nodes that could be generated next are shown in faint dashed lines. Notice in the bottom tree there is a cycle from Arad to Sibiu to Arad; that can’t be an optimal path, so search should not continue from there. 72 Chapter 3 Solving Problems by Searching Figure 3.5 A sequence of search trees generated by a graph search on the Romania problem of Figure 3.1. At each stage, we have expanded every node on the frontier, extending every path with all applicable actions that don’t result in a state that has already been reached. Notice that at the third stage, the topmost city (Oradea) has two successors, both of which have already been reached by other paths, so no paths are extended from Oradea. (a) (b) (c) Figure 3.6 The separation property of graph search, illustrated on a rectangular-grid prob- lem. The frontier (green) separates the interior (lavender) from the exterior (faint dashed). The frontier is the set of nodes (and corresponding states) that have been reached but not yet expanded; the interior is the set of nodes (and corresponding states) that have been expanded; and the exterior is the set of states that have not been reached. In (a), just the root has been expanded. In (b), the top frontier node is expanded. In (c), the remaining successors of the root are expanded in clockwise order. the available ACTIONS for that state, using the R ESULT function to see where those actions Generating lead to, and generating a new node (called a child node or successor node) for each of the Child node resulting states. Each child node has Arad as its parent node. Successor node Now we must choose which of these three child nodes to consider next. This is the Parent node essence of search—following up one option now and putting the others aside for later. Sup- pose we choose to expand Sibiu first. Figure 3.4 (bottom) shows the result: a set of 6 unex- Frontier panded nodes (outlined in bold). We call this the frontier of the search tree. We say that any Reached state that has had a node generated for it has been reached (whether or not that node has been expanded).5 Figure 3.5 shows the search tree superimposed on the state-space graph. Separator Note that the frontier separates two regions of the state-space graph: an interior region where every state has been expanded, and an exterior region of states that have not yet been reached. This property is illustrated in Figure 3.6. 5 Some authors call the frontier the open list, which is both geographically less evocative and computationally less appropriate, because a queue is more efficient than a list here. Those authors use the term closed list to refer to the set of previously expanded nodes, which in our terminology would be the reached nodes minus the frontier.  Section 3.3 Search Algorithms 73 function B EST-F IRST-S EARCH (problem, f ) returns a solution node or failure node← N ODE(S TATE=problem.INITIAL) frontier ← a priority queue ordered by f , with node as an element reached ← a lookup table, with one entry with key problem.I NITIAL and value node while not I S -E MPTY(frontier) do node← P OP(frontier) if problem.I S -G OAL(node.S TATE) then return node for each child in E XPAND(problem, node) do s ← child.S TATE if s is not in reached or child.PATH -C OST < reached[s].PATH -C OST then reached[s] ← child add child to frontier return failure function E XPAND( problem, node) yields nodes s ← node.S TATE for each action in problem.ACTIONS(s) do s′ ← problem.R ESULT(s, action) cost ← node.PATH -C OST + problem.ACTION -C OST(s, action, s′ ) yield N ODE(S TATE=s′ , PARENT=node, ACTION=action, PATH -C OST=cost) Figure 3.7 The best-first search algorithm, and the function for expanding a node. The data structures used here are described in Section 3.3.2. See Appendix B for yield. 3.3.1 Best-first search How do we decide which node from the frontier to expand next? A very general approach is called best-first search, in which we choose a node, n, with minimum value of some Best-first search evaluation function, f (n). Figure 3.7 shows the algorithm. On each iteration we choose Evaluation function a node on the frontier with minimum f (n) value, return it if its state is a goal state, and otherwise apply E XPAND to generate child nodes. Each child node is added to the frontier if it has not been reached before, or is re-added if it is now being reached with a path that has a lower path cost than any previous path. The algorithm returns either an indication of failure, or a node that represents a path to a goal. By employing different f (n) functions, we get different specific algorithms, which this chapter will cover. 3.3.2 Search data structures Search algorithms require a data structure to keep track of the search tree. A node in the tree is represented by a data structure with four components: node.S TATE : the state to which the node corresponds; node.PARENT: the node in the tree that generated this node; node.ACTION : the action that was applied to the parent’s state to generate this node; node.PATH -C OST : the total cost of the path from the initial state to this node. In math- ematical formulas, we use g(node) as a synonym for PATH -C OST. Following the PARENT pointers back from a node allows us to recover the states and actions along the path to that node. Doing this from a goal node gives us the solution. 74 Chapter 3 Solving Problems by Searching Queue We need a data structure to store the frontier. The appropriate choice is a queue of some kind, because the operations on a frontier are: I S -E MPTY (frontier) returns true only if there are no nodes in the frontier. P OP(frontier) removes the top node from the frontier and returns it. T OP(frontier) returns (but does not remove) the top node of the frontier. A DD(node, frontier) inserts node into its proper place in the queue. Three kinds of queues are used in search algorithms: Priority queue A priority queue first pops the node with the minimum cost according to some evalu- ation function, f. It is used in best-first search. FIFO queue A FIFO queue or first-in-first-out queue first pops the node that was added to the queue first; we shall see it is used in breadth-first search. LIFO queue A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most Stack recently added node; we shall see it is used in depth-first search. The reached states can be stored as a lookup table (e.g. a hash table) where each key is a state and each value is the node for that state. 3.3.3 Redundant paths The search tree shown in Figure 3.4 (bottom) includes a path from Arad to Sibiu and back to Repeated state Arad again. We say that Arad is a repeated state in the search tree, generated in this case by Cycle a cycle (also known as a loopy path). So even though the state space has only 20 states, the Loopy path complete search tree is infinite because there is no limit to how often one can traverse a loop. Redundant path A cycle is a special case of a redundant path. For example, we can get to Sibiu via the path Arad–Sibiu (140 miles long) or the path Arad–Zerind–Oradea–Sibiu (297 miles long). This second path is redundant—it’s just a worse way to get to the same state—and need not be considered in our quest for optimal paths. Consider an agent in a 10 × 10 grid world, with the ability to move to any of 8 adjacent squares. If there are no obstacles, the agent can reach any of the 100 squares in 9 moves or fewer. But the number of paths of length 9 is almost 89 (a bit less because of the edges of the grid), or more than 100 million. In other words, the average cell can be reached by over a million redundant paths of length 9, and if we eliminate redundant paths, we can complete a ◮ search roughly a million times faster. As the saying goes, algorithms that cannot remember the past are doomed to repeat it. There are three approaches to this issue. First, we can remember all previously reached states (as best-first search does), allowing us to detect all redundant paths, and keep only the best path to each state. This is appropriate for state spaces where there are many redundant paths, and is the preferred choice when the table of reached states will fit in memory. Second, we can not worry about repeating the past. There are some problem formulations where it is rare or impossible for two paths to reach the same state. An example would be an assembly problem where each action adds a part to an evolving assemblage, and there is an ordering of parts so that it is possible to add A and then B, but not B and then A. For those problems, we could save memory space if we don’t track reached states and we don’t check Graph search for redundant paths. We call a search algorithm a graph search if it checks for redundant Tree-like search paths and a tree-like search6 if it does not check. The B EST-F IRST-S EARCH algorithm in  Section 3.3 Search Algorithms 75 Figure 3.7 is a graph search algorithm; if we remove all references to reached we get a tree- like search that uses less memory but will examine redundant paths to the same state, and thus will run slower. Third, we can compromise and check for cycles, but not for redundant paths in general. Since each node has a chain of parent pointers, we can check for cycles with no need for additional memory by following up the chain of parents to see if the state at the end of the path has appeared earlier in the path. Some implementations follow this chain all the way up, and thus eliminate all cycles; other implementations follow only a few links (e.g., to the parent, grandparent, and great-grandparent), and thus take only a constant amount of time, while eliminating all short cycles (and relying on other mechanisms to deal with long cycles). 3.3.4 Measuring problem-solving performance Before we get into the design of various search algorithms, we will consider the criteria used to choose among them. We can evaluate an algorithm’s performance in four ways: Completeness: Is the algorithm guaranteed to find a solution when there is one, and to Completeness correctly report failure when there is not? Cost optimality: Does it find a solution with the lowest path cost of all solutions?7 Cost optimality Time complexity: How long does it take to find a solution? This can be measured in Time complexity seconds, or more abstractly by the number of states and actions considered. Space complexity: How much memory is needed to perform the search? Space complexity To understand completeness, consider a search problem with a single goal. That goal could be anywhere in the state space; therefore a complete algorithm must be capable of systematically exploring every state that is reachable from the initial state. In finite state spaces that is straightforward to achieve: as long as we keep track of paths and cut off ones that are cycles (e.g. Arad to Sibiu to Arad), eventually we will reach every reachable state. In infinite state spaces, more care is necessary. For example, an algorithm that repeatedly applied the “factorial” operator in Knuth’s “4” problem would follow an infinite path from 4 to 4! to (4!)!, and so on. Similarly, on an infinite grid with no obstacles, repeatedly moving forward in a straight line also follows an infinite path of new states. In both cases the algo- rithm never returns to a state it has reached before, but is incomplete because wide expanses of the state space are never reached. To be complete, a search algorithm must be systematic in the way it explores an infinite Systematic state space, making sure it can eventually reach any state that is connected to the initial state. For example, on the infinite grid, one kind of systematic search is a spiral path that covers all the cells that are s steps from the origin before moving out to cells that are s + 1 steps away. Unfortunately, in an infinite state space with no solution, a sound algorithm needs to keep searching forever; it can’t terminate because it can’t know if the next state will be a goal. Time and space complexity are considered with respect to some measure of the problem difficulty. In theoretical computer science, the typical measure is the size of the state-space graph, |V | + |E|, where |V | is the number of vertices (state nodes) of the graph and |E| is 6 We say “tree-like search” because the state space is still the same graph no matter how we search it; we are just choosing to treat it as if it were a tree, with only one path from each node back to the root. 7 Some authors use the term “admissibility” for the property of finding the lowest-cost solution, and some use just “optimality,” but that can be confused with other types of optimality. 76 Chapter 3 Solving Problems by Searching the number of edges (distinct state/action pairs). This is appropriate when the graph is an explicit data structure, such as the map of Romania. But in many AI problems, the graph is represented only implicitly by the initial state, actions, and transition model. For an implicit Depth state space, complexity can be measured in terms of d, the depth or number of actions in an optimal solution; m, the maximum number of actions in any path; and b, the branching Branching factor factor or number of successors of a node that need to be considered. 3.4 Uninformed Search Strategies An uninformed search algorithm is given no clue about how close a state is to the goal(s). For example, consider our agent in Arad with the goal of reaching Bucharest. An uninformed agent with no knowledge of Romanian geography has no clue whether going to Zerind or Sibiu is a better first step. In contrast, an informed agent (Section 3.5) who knows the location of each city knows that Sibiu is much closer to Bucharest and thus more likely to be on the shortest path. 3.4.1 Breadth-first search Breadth-first search When all actions have the same cost, an appropriate strategy is breadth-first search, 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. This is a systematic search strategy that is therefore com- plete even on infinite state spaces. We could implement breadth-first search as a call to B EST-F IRST-S EARCH where the evaluation function f (n) is the depth of the node—that is, the number of actions it takes to reach the node. However, we can get additional efficiency with a couple of tricks. A first-in-first-out queue will be faster than a priority queue, and will give us the correct order of nodes: new nodes (which are always deeper than their parents) go to the back of the queue, and old nodes, which are shallower than the new nodes, get expanded first. In addition, reached can be a set of states rather than a mapping from states to nodes, because once we’ve reached a state, Early goal test we can never find a better path to the state. That also means we can do an early goal test, Late goal test checking whether a node is a solution as soon as it is generated, rather than the late goal test that best-first search uses, waiting until a node is popped off the queue. Figure 3.8 shows the progress of a breadth-first search on a binary tree, and Figure 3.9 shows the algorithm with the early-goal efficiency enhancements. Breadth-first search always finds a solution with a minimal number of actions, because when it is generating nodes at depth d, it has already generated all the nodes at depth d − 1, so if one of them were a solution, it would have been found. That means it is cost-optimal A A A A B C B C B C B C D E F G D E F G D E F G D E F G Figure 3.8 Breadth-first search on a simple binary tree. At each stage, the node to be ex- panded next is indicated by the triangular marker.  Section 3.4 Uninformed Search Strategies 77 function B READTH -F IRST-S EARCH ( problem) returns a solution node or failure node← N ODE(problem.INITIAL) if problem.I S -G OAL(node.S TATE) then return node frontier ← a FIFO queue, with node as an element reached ← {problem.INITIAL} while not I S -E MPTY(frontier) do node← P OP(frontier) for each child in E XPAND(problem, node) do s ← child.S TATE if problem.I S -G OAL(s) then return child if s is not in reached then add s to reached add child to frontier return failure function U NIFORM -C OST-S EARCH ( problem) returns a solution node, or failure return B EST-F IRST-S EARCH (problem, PATH -C OST) Figure 3.9 Breadth-first search and uniform-cost search algorithms. for problems where all actions have the same cost, but not for problems that don’t have that property. It is complete in either case. In terms of time and space, imagine searching a uniform tree where every state has b successors. The root of the search tree generates b nodes, each of which generates b more nodes, for a total of b2 at the second level. Each of these generates b more nodes, yielding b3 nodes at the third level, and so on. Now suppose that the solution is at depth d. Then the total number of nodes generated is 1 + b + b2 + b3 + · · · + bd = O(bd ) All the nodes remain in memory, so both time and space complexity are O(bd ). Exponential bounds like that are scary. As a typical real-world example, consider a problem with branch- ing factor b = 10, processing speed 1 million nodes/second, and memory requirements of 1 Kbyte/node. A search to depth d = 10 would take less than 3 hours, but would require 10 terabytes of memory. The memory requirements are a bigger problem for breadth-first search than the execution time. But time is still an important factor. At depth d = 14, even with ◭ infinite memory, the search would take 3.5 years. In general, exponential-complexity search problems cannot be solved by uninformed search for any but the smallest instances. ◭ 3.4.2 Dijkstra’s algorithm or uniform-cost search When actions have different costs, an obvious choice is to use best-first search where the evaluation function is the cost of the path from the root to the current node. This is called Di- jkstra’s algorithm by the theoretical computer science community, and uniform-cost search Uniform-cost search by the AI community. The idea is that while breadth-first search spreads out in waves of uni- form depth—first depth 1, then depth 2, and so on—uniform-cost search spreads out in waves of uniform path-cost. The algorithm can be implemented as a call to B EST-F IRST-S EARCH with PATH -C OST as the evaluation function, as shown in Figure 3.9. 78 Chapter 3 Solving Problems by Searching Sibiu Fagaras 99 80 Rimnicu Vilcea Pitesti 211 97 101 Bucharest Figure 3.10 Part of the Romania state space, selected to illustrate uniform-cost search. Consider Figure 3.10, where the problem is to get from Sibiu to Bucharest. The succes- sors of Sibiu are Rimnicu Vilcea and Fagaras, with costs 80 and 99, respectively. The least- cost node, Rimnicu Vilcea, is expanded next, adding Pitesti with cost 80 + 97 = 177. The least-cost node is now Fagaras, so it is expanded, adding Bucharest with cost 99 + 211 = 310. Bucharest is the goal, but the algorithm tests for goals only when it expands a node, not when it generates a node, so it has not yet detected that this is a path to the goal. The algorithm continues on, choosing Pitesti for expansion next and adding a second path to Bucharest with cost 80 + 97 + 101 = 278. It has a lower cost, so it replaces the previous path in reached and is added to the frontier. It turns out this node now has the lowest cost, so it is considered next, found to be a goal, and returned. Note that if we had checked for a goal upon generating a node rather than when expanding the lowest-cost node, then we would have returned a higher-cost path (the one through Fagaras). The complexity of uniform-cost search is characterized in terms of C∗ , the cost of the optimal solution,8 and ǫ, a lower bound on the cost of each action, with ǫ > 0. Then the ∗ algorithm’s worst-case time and space complexity is O(b1+⌊C /ǫ⌋ ), which can be much greater than bd. This is because uniform-cost search can explore large trees of actions with low costs before exploring paths involving a high-cost and perhaps useful action. When all action costs ∗ are equal, b1+⌊C /ǫ⌋ is just bd+1 , and uniform-cost search is similar to breadth-first search. Uniform-cost search is complete and is cost-optimal, because the first solution it finds will have a cost that is at least as low as the cost of any other node in the frontier. Uniform- cost search considers all paths systematically in order of increasing cost, never getting caught going down a single infinite path (assuming that all action costs are > ǫ > 0). 3.4.3 Depth-first search and the problem of memory Depth-first search Depth-first search always expands the deepest node in the frontier first. It could be imple- mented as a call to B EST-F IRST-S EARCH where the evaluation function f is the negative of the depth. However, it is usually implemented not as a graph search but as a tree-like search that does not keep a table of reached states. The progress of the search is illustrated in Figure 3.11; search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. The search then “backs up” to the next deepest node that still has 8 Here, and throughout the book, the “star” in C∗ means an optimal value for C.  Section 3.4 Uninformed Search Strategies 79 A A A B C B C B C D E F G D E F G D E F G H I J K L M N O H I J K L M N O H I J K L M N O A A A B C B C B C ✕ ✕ ✕ ✕ D E F G D E F G D E F G ✕✕ ✕✕ ✕✕ ✕✕ ✕✕ ✕ ✕ ✕ H I J K L M N O H I J K L M N O H I J K L M N O ✕ ✕ ✕ A A ✕ A ✕ ✕ ✕ ✕ ✕ B C B C B ✕ C ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ D E F G D E F G D E F G ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ H I J K L M N O H I J K L M N O H I J K L M N O ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ A ✕ ✕ A ✕ ✕ ✕ A ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ B ✕ C B ✕ C B ✕ C ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ D E F G D E F G D E F G ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ H I J K L M N O H I J K L M N O H I J K L M N O ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ Figure 3.11 A dozen steps (left to right, top to bottom) in the progress of a depth-first search on a binary tree from start state A to goal M. The frontier is in green, with a triangle marking the node to be expanded next. Previously expanded nodes are lavender, and potential future nodes have faint dashed lines. Expanded nodes with no descendants in the frontier (very faint lines) can be discarded. unexpanded successors. Depth-first search is not cost-optimal; it returns the first solution it finds, even if it is not cheapest. For finite state spaces that are trees it is efficient and complete; for acyclic state spaces it may end up expanding the same state many times via different paths, but will (eventually) systematically explore the entire space. In cyclic state spaces it can get stuck in an infinite loop; therefore some implementations of depth-first search check each new node for cycles. Finally, in infinite state spaces, depth- first search is not systematic: it can get stuck going down an infinite path, even if there are no cycles. Thus, depth-first search is incomplete. With all this bad news, why would anyone consider using depth-first search rather than breadth-first or best-first? The answer is that for problems where a tree-like search is feasible, depth-first search has much smaller needs for memory. We don’t keep a reached table at all, and the frontier is very small: think of the frontier in breadth-first search as the surface of an ever-expanding sphere, while the frontier in depth-first search is just a radius of the sphere. 80 Chapter 3 Solving Problems by Searching For a finite tree-shaped state-space like the one in Figure 3.11, a depth-first tree-like search takes time proportional to the number of states, and has memory complexity of only O(bm), where b is the branching factor and m is the maximum depth of the tree. Some problems that would require exabytes of memory with breadth-first search can be handled with only kilobytes using depth-first search. Because of its parsimonious use of memory, depth-first tree-like search has been adopted as the basic workhorse of many areas of AI, including constraint satisfaction (Chapter 6), propositional satisfiability (Chapter 7), and logic programming (Chapter 9). Backtracking search A variant of depth-first search called backtracking search uses even less memory. (See Chapter 6 for more details.) 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 addition, successors are generated by modifying the current state description directly rather than allocating memory for a brand-new state. This reduces the memory requirements to just one state description and a path of O(m) actions; a significant savings over O(bm) states for depth-first search. With backtracking we also have the option of maintaining an efficient set data structure for the states on the current path, allowing us to check for a cyclic path in O(1) time rather than O(m). For backtracking to work, we must be able to undo each action when we backtrack. Backtracking is critical to the success of many problems with large state descriptions, such as robotic assembly. 3.4.4 Depth-limited and iterative deepening search To keep depth-first search from wandering down an infinite path, we can use depth-limited Depth-limited search search, a version of depth-first search in which we supply a depth limit, ℓ, and treat all nodes at depth ℓ as if they had no successors (see Figure 3.12). The time complexity is O(bℓ ) and the space complexity is O(bℓ). Unfortunately, if we make a poor choice for ℓ the algorithm will fail to reach the solution, making it incomplete again. Since depth-first search is a tree-like search, we can’t keep it from wasting time on re- dundant paths in general, but we can eliminate cycles at the cost of some computation time. If we look only a few links up in the parent chain we can catch most cycles; longer cycles are handled by the depth limit. Sometimes a good depth limit can be chosen based on knowledge of the problem. For example, on the map of Romania there are 20 cities. Therefore, ℓ = 19 is a valid limit. But if we studied the map carefully, we would discover that any city can be reached from any other Diameter city in at most 9 actions. This number, known as the diameter of the state-space graph, gives us a better depth limit, which leads to a more efficient depth-limited search. However, for most problems we will not know a good depth limit until we have solved the problem. Iterative deepening Iterative deepening search solves the problem of picking a good value for ℓ by trying search all values: first 0, then 1, then 2, and so on—until either a solution is found, or the depth- limited search returns the failure value rather than the cutoff value. The algorithm is shown in Figure 3.12. Iterative deepening combines many of the benefits of depth-first and breadth-first search. Like depth-first search, its memory requirements are modest: O(bd) when there is a solution, or O(bm) on finite state spaces with no solution. Like breadth-first search, iterative deepening is optimal for problems where all actions have the same cost, and is complete on finite acyclic state spaces, or on any finite state space when we check nodes for cycles all the way up the path.  Section 3.4 Uninformed Search Strategies 81 function I TERATIVE -D EEPENING -S EARCH( problem) returns a solution node or failure for depth = 0 to ∞ do result ← D EPTH -L IMITED -S EARCH( problem, depth) if result 6= cutoff then return result function D EPTH -L IMITED -S EARCH( problem, ℓ) returns a node or failure or cutoff frontier ← a LIFO queue (stack) with N ODE(problem.I NITIAL) as an element result ← failure while not I S -E MPTY(frontier) do node← P OP(frontier) if problem.I S -G OAL(node.S TATE) then return node if D EPTH(node) > ℓ then result ← cutoff else if not I S -C YCLE(node) do for each child in E XPAND(problem, node) do add child to frontier return result Figure 3.12 Iterative deepening and depth-limited tree-like search. Iterative deepening re- peatedly applies depth-limited search with increasing limits. It returns one of three different types of values: either a solution node; or failure, when it has exhausted all nodes and proved there is no solution at any depth; or cutoff , to mean there might be a solution at a deeper depth than ℓ. This is a tree-like search algorithm that does not keep track of reached states, and thus uses much less memory than best-first search, but runs the risk of visiting the same state mul- tiple times on different paths. Also, if the I S -C YCLE check does not check all cycles, then the algorithm may get caught in a loop. The time complexity is O(bd ) when there is a solution, or O(bm ) when there is none. Each iteration of iterative deepening search generates a new level, in the same way that breadth- first search does, but breadth-first does this by storing all nodes in memory, while iterative- deepening does it by repeating the previous levels, thereby saving memory at the cost of more time. Figure 3.13 shows four iterations of iterative-deepening search on a binary search tree, where the solution is found on the fourth iteration. Iterative deepening search may seem wasteful because states near the top of the search tree are re-generated multiple times. But for many state spaces, most of the nodes are in the bottom level, so it does not matter much that the upper levels are repeated. In an iterative deepening search, the nodes on the bottom level (depth d) 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. So the total number of nodes generated in the worst case is N(IDS) = (d)b1 + (d − 1)b2 + (d − 2)b3 · · · + bd , which gives a time complexity of O(bd )—asymptotically the same as breadth-first search. 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. If you are really concerned about the repetition, you can use a hybrid approach that runs 82 Chapter 3 Solving Problems by Searching limit: 0 ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ A A A A limit: 1 ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ B C B C B C B C ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ A A A A limit: 2 B C B C B C B C ✕ ✕ ✕ D E F G D E F G D E F G D E F G ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ A ✕ A ✕ A A ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ B C B C B C B C ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕ ✕