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 + b^{2} + ... + b^{d} nodes => TC O(b^{d})
 To recover path end, we need to store information about (almost all) nodes which implies SC O(b^{d})



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 lowestcost node
 Two other changes to BFS:
 APply goal test to current node^{a}, 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 <= G_{i} 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 lowercost 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(b^{m}) 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 b^{d} nodes at depth d are visited just once.
 The b^{d1} 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)b^{0} + ... + (2)b^{d1} + (1)b^{d}
 BSF slightly more efficient, but both are asymptotically O(b^{d})



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 deadend 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) overestimates 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
 Uniformcost search, but with an evaluation function f(n) = g(n) + h(n)
 We can assure optimality if heuristic h(n) is never an overestimate 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 nondecreasing
 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 nondecreasing 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 uniformcost 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,
 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'


