Avoiding Python's Stack

Question

I am trying a number of search algorithms for an generalized AI problem, one of which is depth-first-search. I have converted breadth-first-search, greedy, and A* searches from their natural recursive form into an iterative one, but am having a bit more trouble doing it cleanly with depth-first-search (although it's not beyond my abilities, I'm not sure the most pythonic way to do so, hence the question).

I am running into trouble with CPython's 1000 recursive-call limit for even some medium-sized problems. Successor states are generated lazily (_generate_states is a generator, not a list), and the path from the initial state is required.

What is the most pythonic way to move from using the call stack to an explicit stack? How much information should be stored in the stack? When backtracking (when no states return a non-empty list), what is the best way to pop dead information from the front of the stack?

def dfs(initial, closed_set, goal, capacity):
    if initial == goal:
        return [initial]

    for state in _generate_states(initial, capacity):
        if state not in closed_set:
            result = dfs(state, [initial] + closed_set, goal, capacity)
            if result:
                return [state] + result
    return []

Answer 1

Here's a solution that keeps the generators around to preserve the desired laziness property:

def dfs(initial, goal, capacity):
    # These three variables form the "stack".
    closed_set = {initial}
    stack = [initial]
    gens = [_generate_states(initial, capacity)]

    while stack:
        cur = stack[-1]
        gen = gens[-1]
        try:
            state = next(gen)
        except StopIteration:
            # This node is done
            closed_set.discard(cur)
            gens.pop()
            stack.pop()
            continue

        if state == goal:
            return stack

        if state not in closed_set:
            closed_set.add(state)
            stack.append(state)
            gens.append(_generate_states(state, capacity))

    return None

Note that the path is the stack when the target is located, because the stack is a record of the nodes visited to get to the current node.

Answer 2

I assume that you know how to implement DFS iteratively using a stack (its basically the same as for BFS, just LIFO instead of FIFO), so I'll post just some general tipps.

• When implementing DFS iteratively, you should use collections.deque for the stack, which is optimized for quickly appending and popping elements.
• You should definitely use a set for the closed_set instead of a list. (Or a map {state: depth} if you want to find the shortest path.)
• For keeping track of the path, you could create a wrapper class, encapsulating your current state and a reference to the previous one (basically a linked list of states), or use a map of predecessor states.

Not sure how to make use of the generator in this case, though, so your stack will hold up to depth x branching-factor elements... or maybe you could put the generator on the stack, instead of the actual elements? Just an idea...