## Loubot 2 years ago Stuck again on ps11. I have the graph built correctly I think! I'm trying to get the bruteforcesearch part working. I'm using recursion(which I'm not very good at. I have it producing a valid path but not the shortest. I don't think my recursion is iterating over all possibilites. It won't find the shortest route defined in the first test i.e. shortest path between nodes 32 and 56. Please help!!

1. Loubot
2. bwCA

what have you done so far to try and find the problem? what were the results - what have you ruled out?

3. Loubot

I've tried changing everything really I think. I had it just returning the visited list if if found the end node but I changed it to return a tuple cotaining the list and the dist used. I've printed out the visited list while running to see what's happening and it looks like the algorithm doesn't backtrack all the way. It's returning a valid path at the moment but not the optimal one. The reason being I think is cause there is a one step route to the end node but my algorithm never gets back to analyse that step. It returns a 4 step solution.

4. bwCA

in the pset, there is a brute force method and a directed method - i seem to recall discussions that nobody could figure out what the difference was, they wrote a 'directed' algorithm for the bruteforce then couldn't figure out what to do for the other function. anyway, there should be a lecture that shows how to go about searching a map depth first. structure the algorithm like that. I don't have mine in front of me right now but i think i kept all paths found in a list then used the sort() method to sort on distance and picked the shortest.

5. bwCA

remember to avoid cycles

6. bwCA

it looks like the algorithm should be going down all possible paths that begin with start what happens if you get to the end of a path and it isn't where you want to go? does it just return an empty list (path)? i don't see where you accumulate the edge distances along a path - every time you add a node to a path shouldn't the distance increase? it seems like all instances of bruteForceSearch() will share and mutate the list 'visited'- is this causing you a problem? each time you go down a different path (recurse) that path should be unique to the other paths - since visited points to a mutable object, i think each instance of the function (each new path) will be using the same list object (pointed to by visited). when you recurse, you might try using a copy (visited[:]) for the argument.

7. bwCA

definitely each function instance is acting upon the same list object (visited) http://dpaste.com/1089649/ - that will probably produce unexpected results you need to accumulate the distance

8. Loubot

Thanks again. I've been at this one for ages. Getting very frustrated by it. I'm going to give it another go with copies of visited. I was hoping to get my recursion to work correctly before I start accumulating distance. I know there is something wrong simply by printing out visited. It doesn't backtrack to the first child of the start node. So it only recurses down one path . Once I get it to recurse through all possible outcomes the rest should be pretty straight forward. As I said my recursion is really weak. I seem to have a mental block when it comes to it for some reason.

9. bwCA

I think you have the correct sequence of steps to traverse the entire graph - the ething that might mess it up is the conditional at step 109 (which avoids cycles). if you just want to make sure that your recursion will traverse the entire graph, make a file with a few edges that Won't have any cycles - then substitute lines 109-121 with a print statement that will let you know where you are at then a recursion statement maybe something like this: something like this: http://dpaste.com/1093865/ with a graph like the attached pic

10. bwCA

hmm after doing that, it makes me wonder if you need a return somewhere in your 'for edge in digraph.childrenOf ...' loop

11. Loubot

Thank you so much for your help. I finally got it figured out. I actually made a mistake but the mistake turned out to be the answer. I needed to increment the distance just before I returned the result. By adding the node locations to a list and summing the distances on each step backwards the correct path and equivalent distance are returned through the backtracking. http://pastebin.com/ZfPd4aYy

12. bwCA

cool - would you mind posting your final graph.py or at least your MitMpa, MitEdge and MitNode classes?

13. Loubot

http://dpaste.com/1113337/ http://dpaste.com/1113342/ Sorry I took so long. My classes were borrowed from yours. I didn't know about __hash__() functions till I saw your one. Thanks again!