3 Replies - 281 Views - Last Post: 22 April 2014 - 11:24 AM Rate Topic: -----

#1 Mordoc  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 21-April 14

Homework: Brute force graph search

Posted 21 April 2014 - 05:13 PM

As a homework assignment, I have to do a brute force graph search, and use those results to find the shortest route between two nodes in a weighted graph.
In this function I'm trying to recursively find all paths from the children of a node to the goal which are shorter than the maxDistance, and build up a complete list of routes.

def validPaths(graph, start, end, maxTotalDist, path = []):
    """ start and end are nodes in the graph
    maxTotalDistance is an int which should be the limit of how far you should travel on a weighted graph"""
    path = path + [start]
    if start == end:
        return path
    allChildrenPaths = []
    if getTotalLength(path, graph) < maxTotalDist: # check to make sure the path is shorter than MaxTotalDistance
        for child in graph.childrenOf(start):
            if child not in path: # so it doesn't contain loops, only include new nodes.
                newPaths = validPaths(graph, child, end, maxTotalDist, path) #find all valid paths for the child
                if newPaths != None: 
                    allChildrenPaths = allChildrenPaths + newPaths #generates a list of all the paths from all the children
    validPathsList = []
    for route in allChildrenPaths: #take all the children's paths, and append the parent node
        validPathsList.append([start] + route)
    return validPathsList


Here is what I have so far, but it doesn't work properly. It seems to give me a short route, and then a bunch of empty lists until it gets to an error when trying to append a node to a list, though, I don't understand where this is coming from. Please help me find the error in my code. At first I would appreciate hints and general nudges in the right direction so I can understand what I'm doing wrong and learn from it.

Is This A Good Question/Topic? 0
  • +

Replies To: Homework: Brute force graph search

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10488
  • View blog
  • Posts: 38,868
  • Joined: 27-December 08

Re: Homework: Brute force graph search

Posted 21 April 2014 - 07:20 PM

Are you sure "brute force" is the right term? The same thing can be accomplished with a greedy breadth-first search. It's called Dijkstra's algorithm.
Was This Post Helpful? 0
  • +
  • -

#3 Mordoc  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 21-April 14

Re: Homework: Brute force graph search

Posted 21 April 2014 - 08:22 PM

View Postmacosxnerd101, on 21 April 2014 - 07:20 PM, said:

Are you sure "brute force" is the right term? The same thing can be accomplished with a greedy breadth-first search. It's called Dijkstra's algorithm.


I had looked at that algorithm when trying to figure out the answer, but I didn't think it quite fit. The instructions were to list every path (hence brute force) that could go from the start node to the finish node which is shorter than the maximum distance, then see which one was the shortest. This is the helper function I wrote to list all of the paths from node A to node B. It is not supposed to be an optimized search, that is another problem in the same problem set, and I can wrap my head around that function better. It's also supposed to be a depth first search instead of a breadth first search, though I might have messed that part up.
Was This Post Helpful? 0
  • +
  • -

#4 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • Joined: 19-July 09

Re: Homework: Brute force graph search

Posted 22 April 2014 - 11:24 AM

I have really trouble understanding what your code is supposed to do.

Sometimes it's better to start again from scratch.
As you told us now your search is supposed to be based on a DFS algorithm.
It might be a good idea to start with a normal DFS and look if you can change it
in a way to solve your problem.

another hint, but please try without:
Spoiler

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1