Как реализовать дерево пространства состояний?

Question

Я пытаюсь решить проблему, подобную ранцу из MIT OCW . Его проблема установлена ​​5.

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

Если я найду узел, где бюджета недостаточно, я должен остановиться здесь. Должен ли я добавить атрибут к каждому узлу дерева?

Когда я добавляю узел, я должен начинать с узла с наибольшей верхней границей. Как я могу найти такой узел? Нужно ли пройти через все узлы, прежде чем я добавлю каждый узел? Или я мог бы сохранить некоторые вар, чтобы помочь с этим?

У вас есть идеи? Не могли бы вы реализовать это в Python?

Answer 1

Надеюсь, я правильно понял проблему, если нет, напишите мне:)
(извините за путаницу, возникающую из-за двух разных значений слова "состояние")

Конечно, вы можете добавить атрибут в узел (это часть состояния!), Так как это очень маленький объем данных. Имейте в виду, что сохранять его не обязательно, поскольку он неявно присутствует в остальной части состояния (учитывая состояния, которые вы уже выбрали, вы можете его вычислить). Лично я бы добавил атрибут, так как нет смысла вычислять его много раз.

По второму вопросу: IIRC, когда вы добавляете узлы, вам не нужно проходить ВСЕ дерево, а только только границу (т. Е. Множество узлов, которые не имеют потомков - не путать с самый глубокий уровень дерева). Поскольку вы ищете верхнюю границу (и поскольку вы используете только положительные затраты), есть три случая, когда вы ищете узел с наибольшим значением:

• на последнем шаге, который вы добавили к узлу, который имел самое высокое значение, так что узел, который вы только что добавили, теперь имеет самое высокое значение
• на последнем шаге при добавлении вы превысили бюджет, поэтому вам пришлось исключить эту опцию. попробуйте добавить другое состояние
• больше нет состояний, которые можно добавить для создания нового узла. Эта ветвь не может идти дальше. Посмотрите на край для наибольшего значения в других узлах