Python的搜索算法从隐含图 [英] Python Search Algorithm from Implied Graphs

问题描述

不久之前我问了一个问题（在Python 深度优先搜索算法），这是由@ 6502精辟回答。它让我思考这个问题更多的precisely，导致这一后续问题。

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.

在previous问题，你必须从这样的功能隐含向树：

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

这意味着，对于任何一个节点，你可以找到子节点，并递归地继续向下搜索这棵树。现在，如果你想从节点A到节点H（说），你可以用code从previous问题，传递neighbors1功能，搜索功能（转载如下）：

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:

则上述可能无法工作，因为你可以和你的地方来回跳转，例如之间的无限循环结束B和F.不过，我认为这可以是固定的，加入了简单的检查，看看，如果你加倍回：

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):

有没有类似的搜索功能，可以让你通过探索最短路径（再次只​​用邻居的功能，而不是的的先验的知识，整个图形的）。一个办法是实施Dijkstra算法，但我认为（虽然寻找最佳的解决方案好），这可能是低效找到很好的解决了一个非常大的图形。有没有这样的事，作为一个深度优先搜索这样的图？或者可以迪杰斯特拉可以以类似的方式执行？或者你会考虑什么办法？

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!

推荐答案

有查找路径，而有效的版本Dijkstra算法的。拆分搜索到两叶，开始从每个终端节点。两者之间交替，在每次迭代扩大一个深度级别

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.

这篇关于Python的搜索算法从隐含图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！