Uninformed SearchBreadth-FirstDepth-FirstDepth-limited Depth FirstIterative DeepeningBidirectionalHeuristic SearchGreedy SearchUniform Cost SearchA* SearchContinuous and Social SearchHill ClimbingSimulated AnnealingSimplex Search (Amoeba Search)Ant OptimizationParticle Swarm OptimizationGenetic AlgorithmsMachine Learning is SearchSearchChris MonsonAugust 12, 2004Contents1 Uninformed Search 11.1 Breadth-First . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Depth-First . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Depth-limited Depth First . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 Iterative Deepening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.5 Bidirectional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Heuristic Search 42.1 Greedy Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Uniform Cost Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 A∗Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Continuous and Social Search 53.1 Hill Climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.2 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.3 Simplex Search (Amoeba Search) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.4 Ant Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.5 Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.6 Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 Machine Learning is Search 101 Uninformed SearchQuestions to answer in the presentations:• Complete?• Optimal?• Time complexity?• Space complexity?• Give example of running algorithm1Algorithm 1 BFSearch(node, goal, queue)while node 6= goal dofor all child ∈ node.children doqueue.push(child)end forif queue.isempty () thenbreakend ifnode = queue.pop()end whileFigure 1: Breadth-first search1.1 Breadth-FirstThe basic idea is that each level is expanded at the same time. Thus, we focus on breadth before depth.Starting at the root node, we expand all of its children. Then we expand all of the children of those children,and so on. Algorithm 1 shows pseudo code for this search. See Figure 1 for an example of how this works,more or less.The space complexity is very high to make this work, since an exponential number of nodes is expandedat each level.What guarantees do we have with this? If there is a solution, we will definitely find it (provided thatwe don’t run out of resources). We will also be sure to find the shortest possible path to it (in steps, not incost).1.2 Depth-FirstThe basic idea here is that we dig as deep as we possibly can before testing anyone’s siblings. Thus, weexpand the first child of the root node, then that child’s first child, and so on. Algorithm 2 outlines the2Figure 2: Depth-first searchsearch without using the call stack. A depiction of the progress of this search is shown in Figure 2.Algorithm 2 DFSearch(node, goal , queue)while node 6= goal dofor all child ∈ node.children dostack.push(child )end forif stack.isempty() thenbreakend ifnode = stack .pop()end whileUnlike with breadth-first search, we do not have any guarantees as to whether the solution will ever befound. The space we are searching could very well be infinite, and therefore we will get stuck going deeperand deeper, and never once branch out. This is a major problem with depth-first search.The space complexity is great, however, and is linear in depth.1.3 Depth-limited Depth FirstThis is essentially a depth-first search where a limit is set on the depth. This means that the search will getcut off before running off into infinity. It also means that for finite spaces, we are no longer guaranteed tofind the goal, since we may cut things off too early.31.4 Iterative DeepeningThis is a depth-limited search where the depth is gradually incremented. Once a small depth is exhausted,a larger depth is tried. Once that is exhausted, the depth is increased again, and so on forever.The time complexity of this algorithm is higher than that of depth-first, since we duplicate work. It issurprising to note, however, that it isn’t as bad as it seems. The actual complexity will be something thatis discussed in class.1.5 BidirectionalHere we start at the starting point and at the goal simultaneously, looking for a common midpoint. This isgenerally done in a breadth-first fashion, though it can be done in other ways. Think hard about it. It’s apain to deal with.2 Heuristic SearchUninformed search has several problems. First, there is no concept of distance or cost between the nodes.This means that we can only find that a path exists to get to the node, not that we can necessarily find theshortest path. Additionally, the searches aren’t smart about what they are doing at all. …