迭代图搜索无限运行

Question

我试图在一个图上运行迭代深化深度优先搜索。我已经知道了如何在树上实现它，并且运行正常。为了将其更改为图形搜索，我维护了一个列表（已关闭），在展开节点之前将对其进行检查，如果已展开，则将跳过该节点。当我运行程序时，它似乎无限地运行，这对我来说是有意义的，因为搜索列表的复杂性可能会达到数十万。我已经把代码贴在下面了

def df_graph(world, fringe, init):
    closed = []
    print("Starting Depth-First Graph Search")
    max_path_cost = -9999
    last_node = None
    start = time.time()
    node = Node(State(world, init[0], init[1]), None, None, 0, 0)                                                 # Creates the initial node
    fringe.put(node)                                                                                                                # Pushes node onto the queue (fringe)
    print("\nStates of first five search nodes: ")
    while(fringe.empty() == False):                                                                                                 # While the fringe is not empty
        node = fringe.get()                                                                                                         # Pops off the front node
        if(node.depth > MAX_DEPTH):
            print("ERROR: MAX DEPTH EXCEEDED")
            return None
        if(node.depth == MAX_DEPTH):                                                                                                # Depth Limiter
            if(node.path_cost > max_path_cost):
                max_path_cost = node.path_cost
                last_node = node
        if (node not in closed):
            closed.append(node)
            options = expand(node, fringe)
        if(options != None):
            costs = sorted(options, reverse=True, key=getDepth)                                                                     # This line is what makes this algorithm depth-first
            for n in costs:
                fringe.put(n)    
    end = time.time()
    path = []
    for i in range(MAX_DEPTH):
        path.append(last_node)
        last_node = last_node.parent
    path.reverse()
    print_results(path, max_path_cost)
    print("Execution time: " + str(end - start) + " seconds")
    return path