Python中前瞻算法的生成器理解

Question

我昨天打电话来询问如何在Python中展望未来。我的问题是迭代所有可能的边以添加到网络中，对于每个添加了边的网络，查看要添加的所有可能的边，依此类推（n depth）。最后，将在n深度生成的所有网络与根网络进行比较，并实际添加最佳第一步（要添加的最佳第一个边，以在n深度获得最佳结果）。添加第一条边后，再次进行深度搜索，依此类推，直到找到一个良好的网络。就像一个移动的窗口，我可以说（请参见lookahead algorithm in Python以获得问题的更彻底的解释）。在

不幸的是，为了问题的清楚性，代码需要igraph，可以在这里找到：http://igraph.org/python/#downloads

@Peter Gibson立即回答，引导我理解生成器理解的逻辑，并帮助我生成以下代码：

from igraph import * # http://igraph.org/python/

def delta(g,gOld): # evaluates the improvement of the graph from one generation to the next 
   print "delta"
   return g.diameter()-gOld.diameter()

def possible_new_edges(G):
    print "Possible new edges"
    allPossibleNewEdges = []
    for n1 in range(50):
        for n2 in range(n1,50):
            if G.are_connected(G.vs[n1],G.vs[n2]) == False and n1 != n2:
                allPossibleNewEdges.append(G.vs[n1],G.vs[n2])
    return allPossibleNewEdges

def add_optimal_edge(graph, n=3):
    print "Add optimal edge"

    paths = [[graph]] # start off with just one graph path, which contains a single graph
    for generation in range(n):
        print "Generation:", generation

        # path[-1] is the latest graph for each generation
        paths = (path + path[-1].add_edge(e) for path in paths for e in path[-1].possible_new_edges())
    # select best path by comparison of final generation against original graph 
    best = max(paths, lambda path: comp_delta(path[-1],graph)) 
    return best[1] # returns the first generation graph

graph = Graph.Erdos_Renyi(50, .15, directed=False, loops=False) # create a random root graph of density 0.15

add_optimal_edge(graph)

发电机简洁典雅。对于我笨拙的Python风格来说，有点太优雅了，为了使它正常工作，我需要了解一些事情。代码运行时出现以下错误：

^{pr2}$

我想是因为在生成器中错误地使用了函数。。。在

所以，我的问题是：在这样的生成器中使用函数的正确方法是什么？我需要调用可能的\u new_edges（）和delta（），需要什么来传递它们（图形？）怎么做呢？在

非常感谢！在

Answer 1

尝试来自your gist的代码时，我发现了几个相当小的错误，这些错误阻止了代码的运行。我在下面包含了固定代码。然而，这并不能真正解决问题。这是因为你的算法需要考虑大量的潜在图，而这在任何合理的时间内都做不到。在

在我的测试中，向前看一步非常好，但是看两步需要很长时间（至少10分钟，我从来没有等到它完成），三步可能需要几天时间。这是因为您的possible_new_edges函数返回一千多个可能的边。每一个都将被添加到初始图形的副本中。然后，对于每个后续步骤，该过程将在上一步骤的每个展开图上重复。这会导致图的指数爆炸，因为您必须按1000**n图的顺序来评估某个图，以确定哪个是最好的。在

所以，要取得实际效果，你还需要改变一些事情。我对图论和你的问题领域不太了解，不足以提出什么建议。在

总之，以下是“工作”代码的更改部分（删除了原始注释，以便我对所更改内容的注释更清楚）：

def possible_new_edges(G):

    print("Possible new edges")

    allPossibleNewEdges = []
    for n1 in range(50):
        for n2 in range(n1,50):
            if G.are_connected(G.vs[n1],G.vs[n2]) == False and n1 != n2:
                allPossibleNewEdges.append((G.vs[n1],G.vs[n2]))        # append a tuple
    return allPossibleNewEdges

def add_optimal_edge(graph, n=3):

    print("Add optimal edge")

    paths = [[graph]]
    for generation in range(n):

        print("Generation:", generation)

        paths = (path + [path[-1] + e]   # use + to add an edge, and to extend the path
                 for path in paths
                 for e in possible_new_edges(path[-1]))   # call this function properly
    best = max(paths, key=lambda path: comp_delta(path[-1],graph)) 
    return best[1]

如果循环中的生成器表达式使您感到困惑，可以用列表理解来替换它（通过用方括号替换最外层的圆括号）。然后可以检查循环中的paths列表（并执行打印其len()等操作）。无论哪种方式，代码的逻辑都是一样的，生成器表达式只是推迟计算展开的结果，直到max函数开始在paths上迭代，以找到最佳得分函数。在

使用列表理解对n=1当然有效，但是当你尝试n=2时，你可能会开始耗尽内存（当然，n=3或更多）。上面的版本不会耗尽内存（因为生成器表达式一次只扩展O(n)个图），但这并不意味着它运行得足够快，可以在合理的时间内检查数十亿个图形。在