Сокращение дерева или графика

Question

В настоящее время я использую Python для решения проблемы «суммирования дерева». Мое дерево состоит из узлов с весами и дочерними элементами. Пример

Node(
    name: "Parent", weight: 20, children: {[ 
     Node(name: "Child 1" weight: 10, children: {[]}, 
     Node(name: "Child 2", weight: 10, children: {[ 
      Node(name: "Grandchild 1", weight: 5, children: {[]} 
     ]} 
    ]}) 

Я заинтересован в поиске всех возможных графиков, получаемых реберными сокращениями. Когда я сжимаю два ребра, старые вершины заменяются новой вершиной, вес которой является суммой старых вершин. Например, договаривающиеся ребенка 2 с Grandchild 1 Результаты в:

Node(
    name: "Parent", weight: 20, children: {[ 
     Node(name: "Child 1" weight: 10, children: {[]}, 
     Node(name: "(Child 2, Grandchild 1)", weight: 15, children: {[]} 
    ]}) 

Конечно, это только один возможный край сжатия. Даже для этого небольшого дерева существует еще много сокращений (например, (child 1, child 2), (child 1, parent), (child 2, parent)).

Для каждого из этих новых деревьев мне нужно снова найти все деревья, полученные путем сжимания одного узла (в конечном итоге проблема состоит в том, чтобы свести дерево n-узлов к дереву m-узлов).

Я в настоящее время «грубой форсинг», рекурсивный вызов edge_contract(), пока не дойду до деревьев нужного размера. Но код должен иметь возможность работать на деревьях умеренного размера (~ 25-50 узлов), а текущая реализация - нет.

Является ли этот тип сокращения дерева решаемой проблемой. Каковы хорошие способы решения этой проблемы?

Answer 1

Каждый раз, когда вы трансформируете дерево, вы решаете на множества ребер, которые вы сжимаете. В примере, который вы указали, набор будет содержать только один край от «Ребенок 2» до Grandchild 1 ».

Если вы заинтересованы в поиске всех деревьев, которые вы можете получить, сократив края, это будет 2^d (где d - общее количество ребер в исходном дереве). Как вы сказали, вы хотите преобразовать дерево n-узлов в дерево m-node. Если вы уже знаете «m», вам нужно найти все наборы из полных наборов 2^d, которые имеют m-1-элементы (поскольку m-дерево узлов будет иметь ребра m-1).

Если вас интересует только подмножество дерева узлов m, то произвольно выберите способ