Поскольку никто не ответил, я дам несколько частичных мыслей.
Вы начинаете с:
1: [A+, E+, H-]
2: [B-, A+, I+, D-]
3: [K+, G+, E+, C-]
4: [H+, A-, G-]
Сначала найдите узлы, которые появляются только с +.Сделай эти корни.Сканируя это, мы можем сделать это для узлов E
, I
и K
.Итак, наш ответ начинается с:
E
E I
I K
И наши данные пути упрощаются до:
1: [A+, H-]
2: [B-, A+, D-]
3: [G+, C-]
4: [H+, A-, G-]
И теперь у нас есть операция разбиения.Для этого мы строим график, где 2 узла связаны, если они появляются вместе с +.Затем мы разделяем узлы по соединенным компонентам и разделяем листы на разделы, где есть + (любой лист без раздела можно сделать листом прямо в дереве, а затем отбросить).Удаление любого - о котором заботится это разделение.В нашем случае это полностью отключенный граф, который помещает каждый узел в свой собственный раздел и делит данные пути на 3 группы (обратите внимание, мы теряем все - правила, которые объясняются разделением):
1: [A+]
2: [A+]
3: [G+]
4: [H+]
И теперь мы решаем каждую проблему, придя к окончательному решению:
E
E I
I K
K A
K B
K C
K D
K G
K H
Я считаю, что этот подход не сможет добиться прогресса только в том случае, если дерево невозможно.Если найдется дерево, оно найдет его.