0

我有一个some_result = treesearch(node)递归搜索大树的函数（蒙特卡洛树搜索的变体）。它决定遍历树的顺序，next_node = expensive_heuristic(node)然后在叶子上将结果传播到树上。我必须执行许多这样的搜索，并且expensive_heuristic(...)可以有效地批量计算，例如，通过 SIMD。

所以我的想法是创建一个包含所有搜索/根节点的列表，批量计算expensive_heuristic以选择遍历的“方向”，然后重复此操作，直到找到叶子并将结果传播回树。

当然，我可以使用队列而不是递归来重写我的搜索（保留历史记录），但我很好奇是否可以保持递归风格。我可以“中断”递归并将其放入列表/队列中以便稍后在 python 中继续它吗？

4

1 回答 1

0

可以使用yield,yield from和send; 感谢 juanpa.arrivillaga 在评论中提出的建议。

下面的代码在随机二叉树中搜索最多 10 个节点并返回其中的最大值。每当它必须计算heuristic用于指导搜索的 a 时，它就会中断生成/搜索。

import random


class Node(object):
    def __init__(self, heuristic_value):
        self.children = {"left": None, "right": None}
        self.child_values = heuristic_value
        self.value = random.randint(0, 100)
        self.terminal = random.random() > 0.9

    def add_leaf(self):
        if self.terminal:
            return self.value

        direction = self.select()
        if self.children[direction]:
            value = yield from self.children[direction].add_leaf()
        else:
            value = yield from self.expand(direction)
        value = self.backup(direction, value)

        return value

    def select(self):
        if self.child_values["left"] > self.child_values["right"]:
            return "left"
        else:
            return "right"

    def expand(self, direction):
        heuristic_value = yield
        child = Node(heuristic_value)
        self.children[direction] = child
        return child.value

    def backup(self, direction, value):
        self.child_values[direction] = value
        if value > self.value:
            return value
        else:
            return self.value


def heuristic():
    return {"left": random.randint(0, 100), "right": random.randint(0, 100)}


tree = Node(heuristic())
for _ in range(10):
    gen = tree.add_leaf()
    value = None
    while True:
        try:
            gen.send(value)
            value = heuristic()
        except StopIteration as value:
            max_val = value
            break

print(f"Largest Value: {max_val}")
于 2020-07-03T11:53:04.723 回答