在python中运行一段时间后，如何退出递归DFS算法

Question

我在python中有一个递归深度优先搜索函数，我想在一定时间后完全退出(整个堆栈)。递归函数知道剩余的时间(它传递了一个名为time_remaining的变量)，当这个time_remainng小于100毫秒时，我想退出整个递归堆栈，并返回一些默认值。在python中实现这一点的最佳方法是什么？

Answer 1

这里有一种方法。它使用一个异常来展开堆栈，并使用一个装饰器来检查每次调用递归时剩余的时间。

import time
class TimeRemainingExpired(Exception):
pass
def enforce_time_remaining(f):
""" decorator to check time remaining and raise if expired """
def new_f(*args, **kwargs):
if kwargs.get('_time_remaining_end_time') is None:
kwargs['_time_remaining_end_time'] = 
time.time() + kwargs['time_remaining']
print(kwargs['_time_remaining_end_time'])
print(kwargs['time_remaining'])
if time.time() >= kwargs['_time_remaining_end_time']:
raise TimeRemainingExpired
return f(*args, **kwargs)
return new_f

@enforce_time_remaining
def recurse(**kwargs):
time.sleep(.01)
recurse(**kwargs)
print(time.time())
try:
recurse(time_remaining=1)
except TimeRemainingExpired:
print('Time Expired')
print(time.time())

Answer 2

本质上，您需要启动一个线程，在一组分配的时间后停止一个全局时间变量，然后允许您的搜索函数在之后运行，并检查最大时间条件何时为假，或者在告诉程序不再假设递归继续的某种状态下。

这是一个递归函数的例子，我传递了一个迭代，这样你就可以看到它的运行，并人为地减慢它的速度。您需要启动一个线程来启动全局计时器，然后在每次调用递归函数时检查该全局计时器。

import time
from threading import Thread
# create a global variable time that is ture
global_time = True 
# start the timer
def start_timer():
time.sleep(0.1) # 1/10 second
# Make sure you're referencing the GLOBAL time variable.
global global_time
# After 1/10 second, the timer will stop.
global_time = False
print("time stopped")
# The itteration variable is just for display.
def dfs(itteration):
# Put your search logic here.
# Again, make sure you're referencing the GLOBAL time variable.
global global_time
if global_time == True:
# Artificially slowing down the search function.
time.sleep(0.01)
# Just print the iteration so you can see what's going on.
itteration = itteration + 1 
print(itteration)
return dfs(itteration)
else:
return "DONE"
# First start the timer.
timer_thread = Thread(target = start_timer)
timer_thread.start()
# Run the search function.
print(dfs(0))

由于计时器是1/10秒，直到它为假，并且每次提交需要1/100，所以它应该只运行10次。这是我的结果：

python time.py 
1
2
3
4
5
6
7
8
9
time stopped
DONE

使用global或sle非常重要，dfs函数将不知道global_time是您在第4行设置的，并且它将永远持续下去。

请注意，我的python版本是3.5，线程在2.7版本中可能有所不同。

无关注释：DFS效率非常低。你应该使用BFS(广度优先搜索)或A*搜索(这被证明是最优的)，尽管这与问题无关。