# Shared Flashcard Set

## Details

Comp2039 - Flashcard Set 1 - Search algorithms
Comp2039 - Alejandro Saucedo - Flashcard Set 1 - Search algorithms
16
Computer Science
05/25/2013

Term
 What is the Anatomy of a Search Problem?
Definition
 An initial state A goal state A set of possible actions in each state The transition model  (result[in(arad), goto(zerind)] -> in(Zerind) Path cost for each state; a summation of step costs
Term
 What is a solution for a search problem?
Definition
 Sequence of actions that start at an initial state and arrive at a goal state. Solution quality is measured by path cost Solutions may be optimal with respect to the path cost or merely "acceptable" or "legal" Optimal solution has the lowest cost Set of open nodes is called frontier
Term
 What is blind and informed search?
Definition
 In blind search, we have no information beyond initial state, goal state, set of actions, transition model and path/step costs In informed search we are able to select among frontier nodes based on some heuristic information
Term
 How does breadth first search operate?
Definition
 All nodes at a given depth are expanded before moving deeper into the search tree  Does not guarantee to find optimal solution http://www.youtube.com/watch?v=zLZhSSXAwxI Select root node as current node Expand current node - For each successor Remove duplicate successor states already found at lower cost. (Requires that we keep a visited list with associated path/costs) Apply goal test to each remaining successor: either solution found or place failed successor on a FIFO queue (This holds the frontier) Select the first element of the queue as current node and go to 2
Term
 What re the criteria for any search algorithm?
Definition
 Completeness - If there is a solution, the algorithm will find it Optimality - It will find the optimal path Time Complexity Space complexity
Term
 What is the performance of the BFS?
Definition
 BFS is complete BFS is not optimal Suppose each node has b successors and thesolution is last node at depth d, then we search: 1 + b + b2 + ... + bd nodes => TC O(bd) To recover path end, we need to store information about (almost all) nodes which implies SC O(bd)
Term
 How can the BFS be made optimal (transforming into Branch and Bound)?
Definition
 By sorting the frontier nodes according to cost, i.e. use priority queue instead of FIFO queue At each stage, we expand the lowest-cost node Two other changes to BFS: APply goal test to current nodea, i.e. when node is taken off queue, not when it is added. REASON: we only know the minimal cost when all prontier nodes have been sorted Modify termination condition to stop only when total cost to goal node GN <= Gi For All i != N where i is an index over all frontier nodes. REASON: When we find a goal, there might still be a lower cost path from another frontier node
Term
 What is the depth first search and how does it operate?
Definition
 ALways expands deepest node in frontier Current node is a leaf, we automatically backgrack via parent(s) to another node of frontier When method succeeds, does not return path http://www.youtube.com/watch?v=zLZhSSXAwxI Select root node as current node Expand current node. For each successor Remove lower-cost duplicates on visited list and push remaining successors on a LIFO stack Pop the first eleent of the stack as current node Apply goal test to current node: either SOlution found of go to step 2
Term
 What is the performance of the DFS?
Definition
 It is complete It is not optimal In worse case - like BFS, we need to search the whole tree Time complexity is O(bm) where m is the maximum depth of the tree; m can be greater than d If we maintain a visited list, we have to store (almost all) nodes so no obvious advantage over BFS in space complexity either However If we are not concerned about redundant paths, expanded nodes can be removed from memory This can give a HUGE space saving relative to BFS: O(bm)
Term
 What is iterative deepening?
Definition
 Place a limit L on depth to which we search We start with L=0, apply DFS, and until success, progressively increment L
Term
 Time complexity of iterative deepening?
Definition
 If branching factor is b (assumed uniform) and solution is last node at depth d, then bd nodes at depth d are visited just once. The bd-1 nodes at deepest level are visited twice... ...The b nodes at depth 1 are visited d times The root node at depth 0 is visited d +1 times so: Nids = (d+1)b0 + ... + (2)bd-1 + (1)bd  BSF slightly more efficient, but both are asymptotically O(bd)
Term
 What is and how does Informed/Heuristic (greedy) search operate?
Definition
 Implements some problem specific information h(n) apart from g(n)  We now expand the node with the lowest evaluation f(n) equal to h(n) - this is called greedy search If we find city X which is a dead-end valley, we call this a local optimum - it may or may not be an acceptable alternative to the global optimum. To escape the local optimum we have to take an action that increases h(n) i.e. go back to parent. If we remove duplicate local optimal we should not revisit X Hence the greedy algorithm is complete But it may not be optimal because heuristics may be misleading or wrong Suppose h(n) over-estimates remaining distance from some city Y on the optimal solution path We may never revisit Y because h(Y) never becomes the 'best' alternative
Term
 What is and how does the A* Algorithm operate?
Definition
 Uniform-cost search, but with an evaluation function f(n) = g(n) + h(n) We can assure optimality if heuristic h(n) is never an over-estimate e.g. if we knew the exact "as the crow flies" distance to Bucharest This is called an admissible heuristic A related condtion is consistency (or monotonicity). A heuristic is consistent if h(n) <= (n, n+1) + h(n+1), where c(n, n+1) is the step cost from n to n+1
Term
 What is the performance of the A* algorithm?
Definition
 Admisability and consistency ensure that A* is optimal (hence the name) provided that h(gi) = 0 where i is an index over all goals Consistency ensure  that the values of f(n) along any path (and therefore along the solution path itself) are non-decreasing Whenever a node is selected for expansion at cost g(n), this is the optimal path cost to node n This is because if node had already been visited at lower cost, either on the frontier or before it, that path to the node would have been selected for the expansion instead (h(n) being the same) By the non-decreasing property, all nodes beyond the frontier have higher path cost than any frontier node prdecessor ( so must cost more than some value already greater than g(n)
Term
 What does the uniform-cost search algorithm consist of?
Definition
 Demands the use of a priority queue. Insert the root into the queue While the queue is not empty: Dequeue the maximum priority element If path is ending in goal state,  print path and exit else  insert all the children of the dequeued element, with the cumulative costs as priority
Term
 What is the dynamic programming principle?
Definition
 The optimal path form start S to goal G must consist of a sequence of optimal steps Given an intermediate node I, the optimal path from S to G through I consists of the optimal path S -> I concatenated with the optimal path I -> G This suggests a recursive formulation in which we let I range from S to G: g(n) = min[g(n') + Π(n', n)] for all precursors n'
Supporting users have an ad free experience!