关于递归：避免Python的堆栈

Avoiding Python’s Stack

我正在尝试多种搜索算法来解决广义 AI 问题，其中之一是深度优先搜索。我已经将广度优先搜索、贪心搜索和 A* 搜索从它们的自然递归形式转换为迭代形式，但是在使用深度优先搜索 cleanly 时遇到了更多麻烦(尽管这并不超出我的能力，我不确定这样做的最pythonic方式，因此问题)。

我遇到了 CPython 的 1000 次递归调用限制，即使是一些中型问题。后继状态是延迟生成的(_generate_states 是生成器，而不是列表)，并且需要从初始状态开始的路径。

从使用调用堆栈到显式堆栈的最 Pythonic 方式是什么？堆栈中应该存储多少信息？回溯时(当没有状态返回非空列表时)，从堆栈前面弹出死信息的最佳方法是什么？

1
2
3
4
5
6
7
8
9
10

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 []

这里有一个解决方案，可以让生成器保持周围以保留所需的惰性属性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

注意，路径是定位到目标时的栈，因为栈是到达当前节点所访问的节点的记录。

我假设你知道如何使用堆栈迭代地实现 DFS(它与 BFS 基本相同，只是 LIFO 而不是 FIFO)，所以我将发布一些一般性提示。

在迭代实现 DFS 时，您应该使用 collections.deque 作为堆栈，该堆栈针对快速追加和弹出元素进行了优化。
您绝对应该为 closed_set 使用集合而不是列表。 (如果您想找到最短路径，也可以使用地图 {state: depth}。)
为了跟踪路径，您可以创建一个package类，封装您的当前状态和对前一个状态的引用(基本上是状态的链接列表)，或者使用前驱状态的映射。

但不确定在这种情况下如何使用生成器，因此您的堆栈将容纳深度 x 个分支因子元素…或者您可以将生成器放在堆栈上，而不是实际的元素?只是一个想法…

这就是我将如何创建迭代深度优先搜索的方法。它使用 candidate_states 作为接下来应该探索的状态堆栈。您可以使用 parents 字典重建从任何访问节点到初始节点的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def reconstruct_path(state, parents):
path = []
while state != None:
path.append(state)
state = parents[state]
path.reverse()
return path

def dfs(initial, goal):
visited_states = set()
candidate_states = [initial]
parents = {initial: None}
while len(candidate_states) > 0:
cur_state = candidate_states.pop()
if cur_state in visited_states: continue
if cur_state == goal:
return reconstruct_path(cur_state, parents)
for state in _generate_states(cur_state):
parents[state] = cur_state
candidate_states.append(state)
return None

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/python/267850.html

关于递归：避免Python的堆栈

Avoiding Python’s Stack

相关推荐

发表回复

分享到: