CS486 Lecture Notes - Lecture 1: Dspace, Branching Factor, Priority Queue
17 Oct 2018
School
Department
Course
Professor
Document Summary
The frontier contains the set of all leaf nodes available for expansion: evaluating an algorithm"s performance . If a solution exists, a complete algo is guaranteed to find a solution within finite time. If a solution exists, the first solution found by an optimal algo has the lowest cost. The time complexity of a search algo is the worst-case time it will take to run, expressed in terms of b/d/m. Informed search treats the frontier as a priority queue. O(bm) worst-case we generate all the nodes in the tree. O(bm) track b children for each level of the longest path: dfs can change if visited states are stored in hash tables and pruned. This eliminates the problem of cycles ruining completeness but increases space complexity to o(bm): bfs is complete in more scenarios then dfs. They are both exponential time-complexity: bfs is complete but requires a lot of space, while dfs requires little space but is not complete.
