Как построить дерево из набора фрагментов пути для листовых узлов - PullRequest
1 голос
/ 25 июня 2019

Я ищу алгоритм для построения возможной нисходящей древовидной структуры, когда единственными входными данными являются решения о пути (в случайном порядке) для конечных узлов.

Решение о пути указывается с помощью [nodeID] +, если конечный узел прошел через этот узел, и [nodeID] - если конечный узел не прошел через этот узел.Пример ввода:

enter image description here

Одна возможная древовидная структура из приведенного выше примера ввода будет:

enter image description here

Выходными данными должен быть список узлов и соответствующий родительский узел, например:

enter image description here

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

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

Я думаю, нужно как-то объединять факты из каждого пути Leaf, как, например, из Leaf1, который вы знаете.: A и E не должны быть в параллельных строках, и из Leaf2 вы знаете, что A и I не должны быть в параллельных строках и т. Д.!

1 Ответ

1 голос
/ 26 июня 2019

Поскольку никто не ответил, я дам несколько частичных мыслей.

Вы начинаете с:

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...