Построить дерево из списка отношений "Содержит"

Вопрос:

У меня есть список областей (A, B, C…), каждый из которых содержит список городов (1, 2, 3, 4), которые они содержат.

Обратите внимание, что это НЕ прямые родители, тот же город появляется в любой области, в которой он содержится.

A: 1 2 3 4 5 6 7 8 9
B: 2 3 4 5
C: 4 5
D: 2 3
E: 5 6 7

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

A: B E   1 8 9
B: C D
C:       4 5
D:       2 3
E:       5 6 7

Если предположить, что иерархия уникальна, может ли кто-нибудь дать мне указатель на алгоритм на любом языке общего назначения (или псевдокоде) (я использую С#) для получения иерархии?

Я разработал что-то, что, как мне кажется, работает, но я бы предпочел нечто более математически определенное, чем «похоже, что это работает».

Я совершенно счастлив, если бы он был разрушен, если нет уникальной иерархии.

Большое спасибо

Ответ №1

Мое решение, которое я считаю правильным, но неэффективно,

(1) Определите ближайшую родительскую зону для каждого города:

Для каждого города найдите район с наименьшим количеством городов, в котором находится этот город.

(2) Определите непосредственного родителя для каждой области:

Для каждой области найдите область с наименьшим количеством городов, которая полностью содержит эту область (не включая себя, конечно) [полностью содержит = все города в области А также находятся в районе B]

Опять же: это, похоже, работает, предполагая, что если в области X содержится город, в котором находится область Y, тогда область X содержит все города, в которых находится область Y, или наоборот.

В моем случае я тестирую это (снова массово неэффективно, но у меня есть небольшие (<1,000 городов) наборы данных) путем изменения шага 1. Для каждого города я нахожу все районы, которые содержат этот город, и сортируют их по количеству городов в области. Затем я проверяю, что каждая область полностью заполнена следующей областью в списке.

Если у кого-то есть правильный ответ (или еще более эффективно, я был бы благодарен за ваш вклад).

Оцените статью
TechArks.Ru
Добавить комментарий