CSC 411 1st Edition Lecture 7Outline of Last Lecture I. Uninformed Search Methodsa. Properties of search methodsb. Measuring Complexityc. Breadth-First Searchd. Depth-First SearchOutline of Current Lecture II. Uninformed Search Methods - Continueda. Limited Depth-First Searchb. State Repeatsi. Cyclicii. Non-cycliciii. Eliminating cyclesCurrent LectureLimited Depth Depth-First Search- Avoid pitfalls of depth-first search- Use cutoff on the maximum depth of the tree- Problem: How to pick the maximum depth?Properties of Limited Depth DFS- Assume: We have a traveler problem with 20 citieso We only need to consider paths of length < 20- Time complexity: O(bl)o l – the limit-Memory complexity: O(bl)Elimination of State Repeats- While searching the state space for the solution we can encounter the same state many times- Question: Is it necessary to keep and expand all copies of a state in a search tree?These 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.o Two possible cases: Cyclic state repeats Non-cyclic state repeatsElimination of Cycles- Question: Can the branch (path) in which the same state is visited twice ever be part of the optimal (shortest) path between the initial state and the goal state?- How to check for cyclic state repeats:o Check ancestors in the tree structureo Caveat: we need to keep the treeo Do not expand the node with the same state as one of its ancestorsElimination of Non-cyclic state repeats- Problem: Nodes can be encountered in different order during different search strategies- BFSo Well behaved with regard to non-cyclic state repeatso Order of expansion determines the correct elimination strategyo We can safely eliminate the node that is associated with the state that has been expanded beforeo Implementation of all state repeat elimination through marking All expanded states are marked and stored in a hash table- DFSo The order of node expansion does not imply correct elimination strategyo We need to remember the length of the path between nodes to safely eliminate themElimination of All State Redundancies- General strategy: a node is redundant if there is another node with exactly the same state and a shorter path from the initial stateo Works for any search methodo Uses additional path length information- Implementation: hash table with the minimum path value- New node is redundant and can be eliminated if:o It is in the hash tableo Its path is longer than or equal to the path stored- Otherwise overwrite with new