Есть ли какой-нибудь известный алгоритм для построения дерева из набора множеств с использованием минимального количества узлов?
Например, у меня есть следующие наборы:
1. {A, B, C}
2. {B, C}
3. {D, B, A}
4. {C, A}
Каждый набор представленный путем от root до листа. Они являются наборами, поэтому порядок появления узлов в пути не важен.
Мне нужно дерево, использующее как можно меньше узлов, которые будут представлять все заданные наборы как пути. Одно из возможных решений (не уверен, что оно минимально):
0
/ \
C A
/ \ \
A B B
/ \ \ \
4 B 2 D
| |
1 3
, где root узел 0 - это какой-то пустой элемент.