CSC 411 1st Edition Lecture 8 Outline of Last Lecture I. Uninformed Search Methods - Continueda. Limited Depth-First Searchb. State Repeatsi. Cyclicii. Non-cycliciii. Eliminating cyclesOutline of Current Lecture I. Iterative Deepening AlgorithmII. Bi-Directional SearchIII. Uniform Cost SearchCurrent LectureIterative Deepening Algorithm (IDA)- Based on limited-depth search, but resolves the difficulty of knowing the depth ahead oftime- Idea: Try all depth limits in an increasing order- Combines advantages of the depth-first and breadth-first search with only moderate computational overheadProperties of IDA- Completeness: Yes- Optimality: Yes- Time Complexity: O(bd)- Memory Complexity: O(bd)Bi-Directional Search- In some search problems we want to find the path from the initial state to the unique goal state (e.g. traveler problem)- Search both from the initial state and the goal state- Use inverse-operators for the goal-initiated searchThese notes represent a detailed interpretation of the professor’s lecture. GradeBuddy is best used as a supplement to your own notes, not as a substitute.- What is the benefit? Assume BFSo Cuts the depth of the search space in half- How do we merge the solutions?o The hash structure remembers the side of the tree where the state was expanded the first time. If the state is reached from the other side, we have a solutionSearching for the minimum cost path- General minimum cost path-search problem:o Adds weights or costs to operators (links)- Search strategy:o “intelligent” expansion of the search tree should be driven by the cost of the current (partially) built path- Implementationo Path cost function for node n: g(n) Length of the path represented by the search tree branch starting at the root of the tree (initial state) to no Search strategy: Expand the leaf node with the minimum g(n) first Can be implemented by the priority queueUniform Cost Search- Note: When operator costs are all equal to 1, the uniform cost search is equivalent to the breadth first search- Expand the node with the minimum path cost firstProperties of Uniform Cost Search- Completeness: Yes- Optimality: Yes- Time and Memory Complexity: O(bd)Elimination of state repeats- Assuming positive costs: If the state has already been expanded, is there a shorter path to that node? No!o Implementation: Marking with a hash