Python 从隐含图搜索算法

Question

不久前我问了一个问题()，@6502 回答得很好。它让我可以更准确地思考这个问题并引出这个后续问题。

在上一个问题中，您从这样的函数中得到了一个隐含的有向树：

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

成功标准函数如下：

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

第一个函数暗示了某种图形，根据细节，它可能是树或循环图，可能是有向的也可能是无向的。但是假设上面暗示了一个有向树（如图）。

这意味着对于任何节点，您都可以找到子节点，并递归地继续搜索这棵树。现在如果你想从节点 A 到节点 H（比如说），你可以使用上一个问题的代码，将 neighbors1 函数传递给搜索函数（在下面重现）：

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

所以你只需调用

search(A,neighbors1,goal)

现在（经过那么长的介绍），问题是，如果邻居函数隐含了不同的图怎么办？

我认为如果邻居函数意味着像这样的无向树：

那么上面的方法可能行不通，因为你最终可能会陷入无限循环，你可以在其中来回跳转，例如B 和 F。但是，我认为这可以通过添加一个简单的检查来解决，看看你是否在加倍返回：

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

对以上efficiency/effectiveness的想法或意见欢迎。

但是，问题的症结在于，如果您有一个由 neighbors 函数（如下所示）隐含的一般图怎么办：

是否有类似的搜索功能可以让您探索通过它的最短路径（再次仅使用邻居功能，而不是 a priori 整个图的知识）。一种选择是实施 dijkstra 算法，但我认为（虽然这有助于找到最佳解决方案），但对于为非常大的图找到好的解决方案而言，这可能效率低下。是否存在像这样的图的深度优先搜索之类的东西？或者 dijkstra 可以用类似的方式实现吗？或者您会考虑什么方法？

我希望这个问题有道理并且对更多人有用，而不仅仅是我！

Answer 1

有一个相当有效的 Dijkstra 算法版本用于查找路径。将搜索分成两个叶，从每个终端节点开始一个。在两者之间交替，每次迭代扩展一个深度级别。

成功是当您将一个节点添加到一个列表中，而另一个列表中已经存在：两个搜索在中间相遇。

理解：深度优先搜索，通过检查找到终端节点。在这种情况下，我们需要做一些简单的改动：

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

您还可以通过向节点对象添加一个布尔值来处理 "found" 列表记帐，在您触摸它时标记每个节点。

这对你有用吗？当您接近到目标节点时，您有什么直觉的方法吗？如果是这样，可能会有一些启发式方法来缩短搜索。

Python 从隐含图搜索算法

Python Search Algorithm from Implied Graphs

python

algorithm

dijkstra

depth-first-search