Подтвердить что ты не робот

Алгоритм семейного древа

Я работаю над составлением задачи, заданной для внутриуровневого курса CS, и придумал вопрос, который на первый взгляд кажется очень простым:

Вам предоставляется список людей с именами их родителей, даты их рождения и даты их смерти. Вы заинтересованы в том, чтобы выяснить, кто в какой-то момент своей жизни был родителем, прародителем, прабабушкой и т.д. Разработать алгоритм, чтобы помечать каждому человеку эту информацию как целое число (0 означает, что у человека никогда не было ребенок, 1 означает, что человек был родителем, 2 означает, что человек был дедушкой и бабушкой и т.д.)

Для простоты вы можете предположить, что семейный граф является DAG, неориентированной версией которого является дерево.

Интересная задача здесь заключается в том, что вы не можете просто взглянуть на форму дерева, чтобы определить эту информацию. Например, у меня 8 пра-прабабушек и бабушек, но поскольку ни один из них не был жив, когда я родился, в их жизни ни один из них не был великим прабабушкой и бабушкой.

Лучший алгоритм, который я могу придумать для этой проблемы, выполняется во времени O (n 2), где n - количество людей. Идея проста - начать DFS с каждого человека, найдя более далекого потомка в генеалогическом древе, которое родилось до даты смерти этого человека. Тем не менее, я уверен, что это не оптимальное решение проблемы. Например, если граф - это всего два родителя и их n детей, то проблема может быть решена тривиально в O (n). Я надеюсь, что это какой-то алгоритм, который либо превосходит O (n 2), либо время выполнения которого параметризуется по форме графика, что делает его быстрым для широких графов с грациозным деградации до O ( n 2) в худшем случае.

4b9b3361

ОТВЕТЫ

Ответ 1

Я подумал об этом сегодня утром, потом обнаружил, что у Алексея Куканова были подобные мысли. Но мой больше связан и имеет некоторую оптимизацию, поэтому я буду публиковать его в любом случае.

Этот алгоритм O(n * (1 + generations)) и будет работать для любого набора данных. Для реалистичных данных это O(n).

  • Запуск всех записей и создание объектов, представляющих людей, которые включают дату рождения, ссылки на родителей и ссылки на детей, а также еще несколько неинициализированных полей. (Время последней смерти между собой и предками и множество дат, в которых у них было 0, 1, 2,... выживших поколения).
  • Пройдите всех людей и рекурсивно найдите и сохраните время последней смерти. Если вы снова вызовете человека, верните сохраненную запись. Для каждого человека вы можете столкнуться с человеком (ему нужно его вычислить), и он может генерировать еще 2 вызова для каждого родителя при первом его вычислении. Это дает общее количество O(n) для инициализации этих данных.
  • Пройдите всех людей и рекурсивно создайте запись, когда они впервые добавили поколение. Эти записи нужны только в максимальной степени, когда умер человек или их последний предок. O(1) вычислять, когда у вас было 0 поколений. Затем для каждого рекурсивного вызова ребенку вам нужно выполнить O(generations) работу, чтобы объединить эти дочерние данные в ваш. Каждый пользователь получает вызов, когда вы сталкиваетесь с ним в структуре данных, и может быть вызван один раз от каждого родителя для вызовов O(n) и общего расхода O(n * (generations + 1)).
  • Пройдите всех людей и выясните, сколько поколений было живым при их смерти. Это снова O(n * (generations + 1)), если оно реализовано с помощью линейного сканирования.

Сумма всех этих операций равна O(n * (generations + 1)).

Для реалистичных наборов данных это будет O(n) с довольно небольшой константой.

Ответ 2

Обновление. Это не лучшее решение, с которым я столкнулся, но я оставил его, потому что его так много комментариев.

У вас есть набор событий (рождение/смерть), родительское состояние (нет потомков, родитель, бабушка и т.д.) и жизненное состояние (живое, мертвое).

Я бы сохранил свои данные в структурах со следующими полями:

mother
father
generations
is_alive
may_have_living_ancestor

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

Birth:
    Create new person with a mother, father, 0 generations, who is alive and may
        have a living ancestor.
    For each parent:
        If generations increased, then recursively increase generations for
            all living ancestors whose generations increased.  While doing that,
            set the may_have_living_ancestor flag to false for anyone for whom it is
            discovered that they have no living ancestors.  (You only iterate into
            a person ancestors if you increased their generations, and if they
            still could have living ancestors.)

Death:
    Emit the person name and generations.
    Set their is_alive flag to false.

Худший случай O(n*n), если у каждого есть много живых предков. Однако, как правило, у вас есть шаг предварительной обработки сортировки, который равен O(n log(n)), а затем вы O(n * avg no of living ancestors), что означает, что общее время в большинстве населения имеет тенденцию быть O(n log(n)). (Я не считал, что сортировка должным образом, спасибо @Alexey Kukanov за исправление.)

Ответ 3

Мое предложение:

  • дополнительно к значениям, описанным в заявлении проблемы, каждая личная запись будет иметь два поля: дочерний счетчик и динамически растущий вектор (в смысле С++/STL), который сохранит самый ранний день рождения в каждом поколении потомков человека.
  • используйте хэш-таблицу для хранения данных, при этом имя человека является ключом. Время его создания линейно (при условии хорошей хэш-функции, карта амортизировала постоянное время для вставок и находок).
  • для каждого человека, определить и сохранить количество детей. Это также выполняется в линейном времени: для каждой личной записи найдите запись для своих родителей и увеличьте их счетчики. Этот шаг можно объединить с предыдущим: если запись для родителя не найдена, она создается и добавляется, а детали (даты и т.д.) Будут добавляться, когда они будут найдены во входе.
  • пересечь карту и поместить ссылки на все личные записи без каких-либо дочерних элементов в очередь. Тем не менее O(N).
  • для каждого элемента, выведенного из очереди:
    • добавьте день рождения этого человека в descendant_birthday[0] для обоих родителей (при необходимости увеличивайте этот вектор). Если это поле уже установлено, измените его, только если новая дата была ранее.
    • Для всех descendant_birthday[i] дат, доступных в векторе текущей записи, выполните те же правила, что и выше, для обновления descendant_birthday[i+1] в записях родителей.
    • декремент дочерних счетчиков родителей; если он достигает 0, добавьте соответствующую родительскую запись в очередь.
    • стоимость этого шага O(C*N), причем C является наибольшим значением "глубина семейства" для данного входа (т.е. размер самого длинного вектора descendant_birthday). Для реалистичных данных он может быть ограничен некоторой разумной константой без потери корректности (как уже указывали другие), и поэтому не зависит от N.
  • еще раз перейдите к карте и "отметьте каждого человека" самым большим i, для которого descendant_birthday[i] все еще раньше даты смерти; также O(C*N).

Таким образом, для реалистичных данных решение задачи можно найти в линейном времени. Хотя для надуманных данных, как это предлагается в комментарии @btilly, C может быть большим и даже порядка N в вырожденных случаях. Его можно решить, поставив колпачок на размер вектора или расширив алгоритм с помощью шага 2 решения @btilly.

Хэш-таблица является ключевой частью решения в случае, если отношения родитель-потомок во входных данных предоставляются через имена (как написано в постановке задачи). Без хэшей потребовалось бы O(N log N) построить график отношений. Большинство других предлагаемых решений, по-видимому, предполагают, что график отношений уже существует.

Ответ 4

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

Для каждого Лица определите поле is_alive. Сначала это будет ЛОЖЬ для всех. Когда люди рождаются и умирают, обновите эту запись соответственно.

Определите другое поле для каждого человека, называемое has_a_living_ancestor, сначала инициализированное FALSE для всех. При рождении x.has_a_living_ancestor будет установлено значение x.mother.is_alive || x.mother.has_a_living_ancestor || x.father.is_alive || x.father.has_a_living_ancestor. Таким образом, для большинства людей (но не для всех) это будет установлено TRUE при рождении.

Задача состоит в том, чтобы идентифицировать случаи, когда has_a_living_ancestor можно установить на FALSE. Каждый раз, когда человек рождается, мы делаем DFS через предков, но только те предки, для которых ancestor.has_a_living_ancestor || ancestor.is_alive истинно.

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

Ответ 5

Ниже приведен алгоритм O (n log n), который работает для графиков, в которых каждый ребенок имеет не более одного родителя (EDIT: этот алгоритм не распространяется на двухпользовательский случай с производительностью O (n log n)), Стоит отметить, что я считаю, что производительность может быть улучшена до O (n log (максимальная метка уровня)) с дополнительной работой.

Один родительский случай:

Для каждого node x в обратном топологическом порядке создайте двоичное дерево поиска T_x, которое строго увеличивается как в дату рождения, так и в количестве поколений, удаленных из x. (T_x содержит первого родившегося ребенка c1 в подграфе графа родословной, внедренного в x, вместе со следующим самым ранним родившимся c2 на этом подграфе, так что c2 "уровень великого дедушки и бабушки" строго больше, чем c1, наряду с следующий самый ранний родившийся ребенок c3 в этом подграфе, такой, что уровень c3 строго больше, чем c2 и т.д.). Чтобы создать T_x, мы объединим ранее построенные деревья T_w, где w - дочерний элемент x (они ранее построены, потому что мы повторяются в обратном топологическом порядке).

Если мы будем осторожны с тем, как мы выполняем слияния, мы можем показать, что общая стоимость таких объединений равна O (n log n) для всего графика предков. Основная идея - отметить, что после каждого слияния в объединенном дереве сохраняется не более одного node каждого уровня. Каждому дереву T_w сопоставим потенциал h (w) log n, где h (w) равен длине самого длинного пути от w до листа.

Когда мы объединяем дочерние деревья T_w для создания T_x, мы "уничтожаем" все деревья T_w, освобождая весь потенциал, который они хранят, для использования при построении дерева T_x; и мы создаем новое дерево T_x с потенциалом (log n) (h (x)). Таким образом, наша цель состоит в том, чтобы потратить не более O ((log n) (sum_w (h (w)) - h (x) + constant)) время для создания T_x из деревьев T_w, так что амортизированная стоимость слияния будет только O (log n). Этого можно добиться, выбирая дерево T_w таким образом, чтобы h (w) было максимальным как начальная точка для T_x, а затем модифицировало T_w для создания T_x. После того, как такой выбор сделан для T_x, мы объединяем каждое из других деревьев один за другим в T_x с алгоритмом, аналогичным стандартным алгоритмом для слияния двух деревьев двоичного поиска.

По существу, слияние выполняется путем повторения каждого node y в T_w, поиска y-предшественника z по дате рождения, а затем вставки y в T_x, если это больше уровней, удаленных из x, чем z; то, если z был вставлен в T_x, мы ищем node в T_x самого низкого уровня, строго превышающего уровень z, и сплайсируем промежуточные узлы для поддержания инварианта, что T_x упорядочивается строго как по дате рождения, так и по уровень. Это стоит O (log n) для каждого node в T_w, и в T_w есть не более O (h (w)) узлов, поэтому общая стоимость слияния всех деревьев равна O ((log n) (sum_w (h (w))), суммируя по всем детям w, за исключением того, что ребенок w 'такой, что h (w') максимален.

Мы сохраняем уровень, связанный с каждым элементом T_x во вспомогательном поле каждого node в дереве. Нам нужно это значение, чтобы мы могли определить фактический уровень x, как только мы построили T_x. (В качестве технической детали мы фактически сохраняем разницу в каждом уровне node с уровнем ее родительского элемента в T_x, чтобы мы могли быстро увеличивать значения для всех узлов в дереве. Это стандартный трюк BST.)

Что это. Просто отметим, что начальный потенциал равен 0, а конечный потенциал положителен, поэтому сумма амортизированных оценок является верхней границей общей стоимости всех слияний по всему дереву. Мы найдем метку каждого node x, как только мы создадим BST T_x, путем двоичного поиска последнего элемента в T_x, который родился до того, как x умер по цене O (log n).

Чтобы улучшить привязку к O (n log (метка максимального уровня)), вы можете с лёгкостью объединить деревья, только объединяя первые несколько элементов дерева по мере необходимости, чтобы обеспечить решение для текущего node. Если вы используете BST, который использует локальность ссылки, например дерево splay, то вы можете достичь указанной выше.

Надеемся, что вышеупомянутый алгоритм и анализ, по крайней мере, достаточно ясны, чтобы следовать. Просто прокомментируйте, если вам нужно какое-либо разъяснение.

Ответ 6

У меня есть догадка, что получение для каждого человека сопоставления (генерация → дата рождения первого потомка в этом поколении).

Поскольку даты должны быть строго возрастающими, мы могли бы использовать бинарный поиск (или аккуратную структуру данных), чтобы найти самого отдаленного живого потомка в O (log n) времени.

Проблема заключается в том, что объединение этих списков (по крайней мере наивно) - это O (количество поколений), поэтому в худшем случае это может быть O (n ^ 2) (рассмотрим A и B являются родителями C и D, которые являются родителями E и F...).

Мне все же нужно разобраться, как работает лучший случай, и попытаться лучше определить наихудшие случаи (и посмотреть, есть ли у них обходной путь)

Ответ 7

Недавно мы реализовали модуль отношений в одном из наших проектов, в котором у нас было все в базе данных, и да, я думаю, что алгоритм был лучшим 2nO (m) (m - максимальный фактор ветвления). Я дважды умножал операции на N, потому что в первом раунде мы создаем график отношений, а во втором раунде мы посещаем каждого Лица. Мы сохранили двунаправленную связь между каждыми двумя узлами. Во время навигации мы используем только одно направление для путешествия. Но у нас есть два набора операций, один - только дети, другой - только родительский.

Person{
  String Name;

  // all relations where
  // this is FromPerson
  Relation[] FromRelations; 

  // all relations where
  // this is ToPerson
  Relation[] ToRelations;

  DateTime birthDate;
  DateTime? deathDate;
}

Relation
{
  Person FromPerson;
  Person ToPerson;
  RelationType Type;
}

enum RelationType
{
  Father,
  Son,
  Daughter,
  Mother
}

Этот вид выглядит как двунаправленный граф. Но в этом случае сначала вы создаете список всего Person, а затем вы можете создавать отношения списка и настраивать FromRelations и ToRelations между каждым node. Тогда все, что вам нужно сделать, это для каждого Лица, вы должны только ориентироваться на ToRelations типа (Son, Daughter). А поскольку у вас есть дата, вы можете рассчитать все.

У меня нет времени проверить правильность кода, но это даст вам представление о том, как это сделать.

void LabelPerson(Person p){
   int n = GetLevelOfChildren(p, p.birthDate, p.deathDate);
   // label based on n...
}

int GetLevelOfChildren(Person p, DateTime bd, DateTime? ed){
   List<int> depths = new List<int>();
   foreach(Relation r in p.ToRelations.Where(
             x=>x.Type == Son || x.Type == Daughter))
   {
      Person child = r.ToPerson;
      if(ed!=null && child.birthDate <= ed.Value){
         depths.Add( 1 + GetLevelOfChildren( child, bd, ed));
      }else
      {
         depths.Add( 1 + GetLevelOfChildren( child, bd, ed));
      }
   }
   if(depths.Count==0)
      return 0;
   return depths.Max();
}

Ответ 8

Вот мой удар:

class Person
{
    Person [] Parents;
    string Name;
    DateTime DOB;
    DateTime DOD;
    int Generations = 0;

    void Increase(Datetime dob, int generations)
    {
        // current person is alive when caller was born
        if (dob < DOD)
            Generations = Math.Max(Generations, generations)
        foreach (Person p in Parents)
            p.Increase(dob, generations + 1);
    }

    void Calculate()
    {
        foreach (Person p in Parents)
            p.Increase(DOB, 1);
    }
}

// run for everyone
Person [] people = InitializeList(); // create objects from information
foreach (Person p in people)
    p.Calculate();

Ответ 9

  • Существует относительно простой алгоритм O (n log n), который хронологически проводит хронологию событий с помощью подходящего верхнего дерева.

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