CODEWITHSUNDEEP
pythonalgorithmdijkstradepth-first-search
Dr Xorile
Dr Xorile

Reputation: 1009

Python Search Algorithm from Implied Graphs

A little while ago I asked a question (depth first search algorithm in python), which was answered brilliantly by @6502. It's allowed me to think about this problem more precisely and leads to this follow up question.

In the previous question you have an implied directed tree from a function like this:

def neighbors1(node):
    "Returns neighboring nodes in directed tree"
    #some code
    yield node_1
    #some more code
    yield node_2
    #...
    yield node_n

and a success criteria function like this:

def goal(node):
    "Returns true if node is the end goal and false otherwise"
    if node #meets some goal#:
        return True
    else:
        return False

The first function implies some kind of graph, and depending on the details it may be a tree or a graph with cycles and it may be directed or non-directed. But suppose that the above implies a directed tree (like the diagram).

enter image description here

This means that for any node you can find the children nodes, and recursively continue searching down this tree. Now if you want to get from node A to node H (say), you can use the code from the previous question, passing the neighbors1 function to the search function (reproduced below):

def search(start_state, neighbors, goal):
    path = [start_state]

    class PathFound(RuntimeError):
        pass

    def rsearch(x):
        if goal(x):
            raise PathFound
        for y in neighbors(x):
            path.append(y)
            rsearch(y)
            path.pop()

    try:
        rsearch(start_state)
    except PathFound:
        return path

    return None # No path exists

So with this you'd simply call

search(A,neighbors1,goal)

Now (after that long introduction), the question is, what if there are different graphs implied by the neighbor function?

I think if the neighbor function implies a non-directed tree like this:

enter image description here

then the above may not work, because you could end up with an endless loop where you jump back and forth between e.g. B and F. However, I think this can be fixed by adding in a simple check to see if you're doubling back:

def search(start_state, neighbors, goal):
    path = [start_state]

    class PathFound(RuntimeError):
        pass

    def rsearch(x):
        if goal(x):
            raise PathFound
        for y in neighbors(x):
            if y in path: continue  #New line for undirected graphs
            path.append(y)
            rsearch(y)
            path.pop()

    try:
        rsearch(start_state)
    except PathFound:
        return path

    return None # No path exists

Thoughts or comments on the efficiency/effectiveness of the above welcome.

However, the crux of the question, is what if you've got a general graph that is implied by the neighbors function (as follows):

Random Graph

Is there a similar search function that will allow you to explore shortest paths through that (again just using the neighbors function, rather than a priori knowledge of the entire graph). One option would be to implement dijkstra's algorithm, but I think (though good for finding the best solution), this may be inefficient for finding a good solution to a very large graph. Is there such a thing as a depth-first search for a graph like this? Or can dijkstra be implemented in a similar way? Or what approach would you consider?

I hope the question makes sense and is useful to more people than just me!

Upvotes: 1

Views: 346

Answers (1)

Prune
Prune

Reputation: 77867

There's a rather effective version of Dijkstra's algorithm for finding a path. Split the search into two lobes, starting one from each terminal node. Alternate between the two, expanding one depth level on each iteration.

Success is when you add a node to one list that is already on the other: the two searches have met in the middle.

Understood: depth-first search, find terminal nodes by examination. In that case, we need to make a couple of simple alterations:

def rsearch(x, found=[]):
    if goal(x):
        raise PathFound
    for y in neighbors(x) and y not in found:
        found.append(y)
        path.insert(0, y)    # switch to depth-first search
        rsearch(y, found)
        path.pop()

You can also handle the "found" list accounting by adding a boolean to the node object, marking each node as you touch it.

How does this work for you? Do you have any way to intuit when you're getting close to a goal node? If so, there could be some heuristic to shorten the search.

Upvotes: 1

Related Questions