Алгоритм родословной - PullRequest
Новая
       24

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

45 голосов
/ 23 мая 2011

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

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

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

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

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

Ответы [ 9 ]

11 голосов
/ 24 мая 2011

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

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

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

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's ancestors if you increased their generations, and if they
            still could have living ancestors.)

Death:
    Emit the person's 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 за исправление.)

7 голосов
/ 26 мая 2011

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

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

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

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

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

5 голосов
/ 26 мая 2011

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

  • в дополнение к значениям, описанным в постановке задачи, каждая личная запись будет иметь два поля: счетчик дочерних элементов и динамически растущий вектор (в смысле C ++ / 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). Большинство других предлагаемых решений, похоже, предполагают, что граф отношений уже существует.

3 голосов
/ 30 мая 2011

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

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

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

Если мы будем осторожны с тем, как мы выполняем слияния, мы можем показать, что общая стоимость таких слияний составляет O (n log n) для всего графа предков. Основная идея заключается в том, чтобы заметить, что после каждого объединения в объединенном дереве выживает не более одного узла каждого уровня. Мы связываем с каждым деревом 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 с помощью алгоритма, аналогичного стандартному алгоритму объединения двух двоичных деревьев поиска.

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

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

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

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

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

3 голосов
/ 24 мая 2011

Создать список людей, отсортированных по 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 можно установить в ЛОЖЬ. Каждый раз, когда человек рождается, мы совершаем ДФС через предков, но только тех предков, для которых ancestor.has_a_living_ancestor || ancestor.is_alive истинно.

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

2 голосов
/ 28 мая 2011

Недавно мы внедрили модуль отношений в одном из наших проектов, в котором у нас было все в базе данных, и да, я думаю, что алгоритм был наилучшим 2nO (м) (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 между каждым узлом.Тогда все, что вам нужно сделать, это то, что для каждого Человека вы должны перемещаться только по ToRelation типа (Сын, Дочь).И так как у вас есть дата, вы можете вычислить все.

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

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();
}
2 голосов
/ 26 мая 2011

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

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

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

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

0 голосов
/ 26 мая 2011

Вот мой удар: 

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();
0 голосов
/ 24 мая 2011

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

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

...