A community for students.
Here's the question you clicked on:
 0 viewing
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!!
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!!

This Question is Closed

bwCA
 2 years ago
Best ResponseYou've already chosen the best response.1what have you done so far to try and find the problem? what were the results  what have you ruled out?

Loubot
 2 years ago
Best ResponseYou've already chosen the best response.0I'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.

bwCA
 2 years ago
Best ResponseYou've already chosen the best response.1in 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.

bwCA
 2 years ago
Best ResponseYou've already chosen the best response.1it 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.

bwCA
 2 years ago
Best ResponseYou've already chosen the best response.1definitely 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

Loubot
 2 years ago
Best ResponseYou've already chosen the best response.0Thanks 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.

bwCA
 2 years ago
Best ResponseYou've already chosen the best response.1I 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 109121 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

bwCA
 2 years ago
Best ResponseYou've already chosen the best response.1hmm after doing that, it makes me wonder if you need a return somewhere in your 'for edge in digraph.childrenOf ...' loop

Loubot
 2 years ago
Best ResponseYou've already chosen the best response.0Thank 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

bwCA
 2 years ago
Best ResponseYou've already chosen the best response.1cool  would you mind posting your final graph.py or at least your MitMpa, MitEdge and MitNode classes?

Loubot
 2 years ago
Best ResponseYou've already chosen the best response.0http://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!
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.