Как переделать дерево решений «да / нет»?

Я хочу решить загадку. Но я просто не знаю, какой код нужен для этого. Задача – экспоненциальная.

Описание:

Игрок идет / работает по одному шагу за раз. Иногда будет принято решение; это вопрос «да / нет». После ответа на вопрос игрок продолжает идти до следующего решения / вопроса. Продолжайте это до тех пор, пока общее расстояние не будет покрыто.

Проблема именно в этом.

Проблема в том, что я хочу видеть все возможные маршруты через это (многие списки 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!' 

Решение того, что я ищу, выглядит так:

  • Прогулка, пока не будет достигнут вопрос
  • Сделайте копию маршрута
  • На маршруте А говорят «Да»
  • На маршруте B (копия): Нет

Маршрут A:
повторите то, что выше (это разворачивает еще два маршрута)

Маршрут B:
повторите то, что выше (это разворачивает еще два маршрута)

Используя код, который у меня есть, это что-то вроде:

 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? 

Эта проблема экспоненциальна, потому что при каждом решении маршрут развивает еще два маршрута. Мне нужны все возможности; Я знаю, что существует менее 512 возможностей, поэтому компьютер может решить это в одно мгновение.

Каждый маршрут будет храниться в экземпляре Player.route (в виде списка, например: ['y', 'y', 'n', 'y'])

Я просто понятия не имею, как решить такую ​​проблему программно. Я был бы признателен за некоторые идеи относительно того, как структурировать код для решения такой проблемы.

Фактически такая структура данных – двоичное дерево – используется для того, чтобы просто избежать экспоненциальной проблемы, о которой вы говорили. Или, другими словами, предполагаемый список '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) .

Это кажется довольно простой задачей для рекурсии, и у вас уже есть довольно простая древовидная структура. Возможно, вам следует просто перенести процесс принятия решения в явную древовидную структуру и реализовать рекурсивный обход узлов? Это, наверное, самое разумное решение, учитывая то, что похоже на то, что вы пытаетесь сделать. Я думаю, вы ищете «грубую силу» … но альтернативное итерационное решение было бы намного менее изящным (и сложнее писать).

Наивный, но, вероятно, подходящий способ генерации перестановок, подобных этому, состоит в том, чтобы пробегать числа 0..512 , преобразовывать их в двоичные (с правильным дополнением) и обрабатывать нули как «Нет», а «Да». Девять бит достаточно для 512 значений, поэтому создайте такую ​​строку:

 '{0:0>9b}'.format(123)