Hey guess what you’re learning pseudoscience.12Are they going to kill us? Will they be slaves? That’s what we’re working towards.345Many problems can be encoded this way6How to encode as search problem?7Make a graph of possible states.State: config of puzzleTransition: up to 4 poss moves from each state Solvable in 22 steps on averageBut state space is really big. 2*1^5.8Allowed motions: You can move up, down, left, or right. You can’t move through 9walls.In the real world the graph is really really big. V large # states101112131415Keep in mind storing graph in mem is not an option.16171819202122The “right” way to implement232425Which is better? Depends on graph. For example, for a dense tree with start at root 26and goal at leaf then backwards is better. Others may vary.Guaranteed lowest cost IF all edges have uniform, nonnegative cost.2728Stopping: when intersect(V,V’) nonempty29Optimal if all costs uniform30Note: Going backwards isn’t always possible313233Complexity depends on the implementation of the PQ. This complexity is for a min 34heap implementation. For a survey of different PQ implementations see http://www.theturingmachine.com/algorithms/heaps.html353637Add cost from p to q to the value of p38The value for item e has been updated from 9 to 5. This is generally not supported 39by a PQ, but there are ways to fake it.404142434445If p is not in the queue but visited, we already visited it.46(If costs aren’t negative or 0, this works. In fact this is why it won’t work if costs are negative or 0) Note keep in memory everything we’ve seen.4748495051Can’t stop until you POP the goal!5253Why is this correct?54Log(Q) is due to priority queueEach edge cost >= epsilon, therefore B^(C/epsilon) is upper bound on number of steps.Why no log in space? Log has to do with popping priority queue, but space is just storing the thing (so multiply space by 2)55You could visit a lot of nodes (ex driving)5657585960616263646566676869What’s the problem? Cycles.70Didn’t just remember path (in the stack), also remembered which successor each node has already tried.717273Which should you do?74Current path: at least we won’t loop forever, and better for memory usage.Memdfs means you’d have to keep track of whole graph, and that’s a lot.75In PCDFS you can visit same node twice (though not in the same path). So no 76luxury of NPCDFS is same storage as DFS (we’re already storing the path in the stack)MEMDFS you would have to store whole graph. However, the time complexity could be as low as N.777879Why does it not matter to do the same stuff over and over? Exponential growth 80means the first levels aren’t all that
View Full Document