Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Loubot Group Title

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

  • one year ago
  • one year ago

  • This Question is Closed
  1. Loubot Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    http://dpaste.com/1079728/

    • one year ago
  2. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • one year ago
  3. Loubot Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • one year ago
  4. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

    • one year ago
  5. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    remember to avoid cycles

    • one year ago
  6. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

    • one year ago
  7. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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

    • one year ago
  8. Loubot Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • one year ago
  9. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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

    • one year ago
    1 Attachment
  10. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • one year ago
  11. Loubot Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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

    • one year ago
  12. bwCA Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

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

    • one year ago
  13. Loubot Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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!

    • one year ago
    • Attachments:

See more questions >>>

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

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.