python - 如何暴力破解一棵 'yes/no' 决策树？

Question

我想解决一个难题。但我根本不知道它需要什么样的代码。该问题呈指数级增长。

描述:

玩家一次走/跑一步。有时会做出决定；这是一个是/否的问题。一旦回答了问题，玩家将继续行走，直到做出下一个决定/问题。继续这样做，直到覆盖总距离。

问题是我想通过它查看所有可能的路径(许多 python 列表，例如 ['y','y','n','y','n'])。这是我到目前为止编写的代码:(Player 在 Player() 类中，我已将其删除，因为它在这里不重要。)

class Solver(object):
    """ Solver object. """

def __init__(self, field):
    self.field = field
    self.dinc = 113
    self.distance = 128

def take_step(self, player):
    """ Takes a step and records players route. """
    # Adds 0 if there is no decision to be made on this step
    # Adds 1 if there is a decision to be made on this step

    player.run(self.dinc)
    if self._is_decision_time(player):
        player.route.append((player.step_id, 1))
    else:
        player.route.append((player.step_id, 0))

def next_decision(self, player):
    """ Accepts a player object. Walks until reaches next decision. """
    while not self._is_decision_time(player):
        self.take_step(player)
    self.display_stats(player)

def say_no(self, player):
    """ Simulates a no response. Resets danger. Updates route with decision. """
    player.route[-1] = (player.step_id, 'n')
    player.danger = 0
    print 'no!'

def say_yes(self, player):
    """ Simulates a yes response. Updates route with decision. """
    player.route[-1] = (player.step_id, 'y')
    print 'yes!'

我正在寻找的解决方案是这样的:

• 一直走到问题为止
• 复制路线
• 在路线 A 上说是
• 在路线 B ​​上(副本)说不

路线A:
重复上面的内容(这 fork 了另外两条路线)

路线B:
重复上面的内容(这 fork 了另外两条路线)

使用我目前的代码，它是这样的:

route_a = Player()
solver = Solver()

# walk until a battle is reached
solver.next_decision(route_a)
# make a copy of the route (there are now two routes A + route B)
route_b = copy.deepcopy(route_a)

# on route A say 'yes'
solver.say_yes(route_a)
# on route B say 'no'
solver.say_no(route_b)
# walk until the next decision is reached
solver.next_battle(route_a)
solver.next_battle(route_b)
# Then?

这个问题是指数级的，因为在每次决策时，路线都会 fork 成另外两条路线。我需要所有的可能性；我碰巧知道有不到 512 种可能性，所以计算机可以瞬间解决它。

每条路线都将存储在 Player.route 实例中(作为列表，例如:['y','y','n','y'])

我只是不知道如何以编程方式解决这样的问题。关于如何构建代码来解决此类问题的一些想法，我将不胜感激。

Answer 1

实际上，使用这种数据结构——二叉树——只是为了避免你提到的指数问题。或者，换句话说，假定的 'y' 和 'n' 列表将呈指数增长，但通常你不需要它，因为你有二叉树.你知道你通过一个是或否的问题来解决问题。

但是，如果你想打印你要求的列表，就像在这个伪代码中那样做(因为我迷失了 C++，我仍然不能用 Python 编程 ;-))

def recurse(node, s=''):
    if node == end_node:
        print s
        return

    recurse(node.left,  s + 'n')
    recurse(node.right, s + 'y')

然后调用从根节点或头节点开始的函数，即 recurse(root_node)。