1. An initial state
2. A goal state
3. A set of possible actions in each state
4. The transition model 
• (result[in(arad), goto(zerind)] -> in(Zerind)
5. Path cost for each state; a summation of step costs

• 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

• 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

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

1. Select root node as current node
2. Expand current node - For each successor
1. Remove duplicate successor states already found at lower cost. (Requires that we keep a visited list with associated path/costs)
2. Apply goal test to each remaining successor: either solution found or place failed successor on a FIFO queue (This holds the frontier)
3. Select the first element of the queue as current node and go to 2

1. Completeness - If there is a solution, the algorithm will find it
2. Optimality - It will find the optimal path
3. Time Complexity
4. Space complexity

• 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² + ... + 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)

• 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 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

• 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

1. Select root node as current node
2. Expand current node. For each successor
3. Remove lower-cost duplicates on visited list and push remaining successors on a LIFO stack
4. Pop the first eleent of the stack as current node
5. Apply goal test to current node: either SOlution found of go to step 2

• 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)

• Place a limit L on depth to which we search
• We start with L=0, apply DFS, and until success, progressively increment L

• 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^d-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)b⁰ + ... + (2)b^d-1 + (1)b^d 
• BSF slightly more efficient, but both are asymptotically O(b^d)

• 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

• 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

• 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)

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

• 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'