[algorithm] ファミリーツリーアルゴリズム



3 Answers

アップデート :これは私が思いついた最善の解決策ではありませんが、それに関する多くのコメントがあるので、私はそれを残しました。

あなたは一連の出来事(出生/死)、親の状態(子孫、親、祖父母など)および生命状態(生きている、死んでいる)を持っています。

私は次のフィールドを持つ構造体に自分のデータを格納します:

mother
father
generations
is_alive
may_have_living_ancestor

イベントを日付順にソートし、イベントごとに次の2つのロジックコースのいずれかを選択します。

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のおかげで、私は適切にソートの前段階を数えていなかった。)

Question

私は、イントロレベルのCSコースの問題をまとめようと努力しており、表面上の問題は非常にシンプルなように思えます。

あなたは、両親の名前、生年月日、死亡者の名前の人のリストが与えられます。 あなたは、生涯のある時点で誰が親、祖父母、曽祖父母なのかを知ることに興味があります。この情報を各人にラベル付けするためのアルゴリズムを整数で表します(0は、子供は1人は親であったことを意味し、2人は祖父母であったことを意味する)

簡単にするために、ファミリーグラフは、無向バージョンがツリーであるDAGであると仮定できます。

興味深いのは、この情報を判断するためにツリーの形を見ることができないということです。 例えば、私には8人の曽祖父母がいますが、私が生まれたときに生きていた人はいないので、生涯では誰も偉大な祖父母ではありませんでした。

この問題のために私が思いつくことができる最良のアルゴリズムは、時間O(n 2 )で実行されます.nは人数です。 アイデアは簡単です - 各人からDFSを始め、その人の死亡日前に生まれた家系の中で最も遠い子孫を見つける。 しかし、私はこれが問題の最適な解決策ではないと確信しています。 例えば、グラフがちょうど2つの親とそのnの子である場合、問題はO(n)において簡単に解くことができる。 私が望んでいるのは、O(n 2 )を叩くか、ランタイムがグラフの形状にパラメータ化され、ワイドグラフではO(n 2 )場合。




birth_dateでソートされた人のリストを作成します。 death_dateでソートされた別の人々のリストを作成します。 あなたは論理的に時間をかけて移動し、これらのリストから人々をポップして、起こったイベントのリストを取得することができます。

各Personに対して、 is_aliveフィールドを定義します。 これは誰にとってもまず当てはまりません。 人々が生まれて死ぬにつれて、それに応じてこの記録を更新してください。

has_a_living_ancestorというhas_a_living_ancestor人物ごとに別のフィールドを定義し、最初はすべての人がFALSEに初期化します。 出生時に、 x.has_a_living_ancestorx.has_a_living_ancestorに設定されx.mother.is_alive || x.mother.has_a_living_ancestor || x.father.is_alive || x.father.has_a_living_ancestor x.mother.is_alive || x.mother.has_a_living_ancestor || x.father.is_alive || x.father.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 ancestor.has_a_living_ancestor || ancestor.is_aliveはtrueです。

そのDFS中に、生きている祖先がなく、現在は死んでいる祖先を見つけると、 has_a_living_ancestorをFALSEに設定することができます。 これは、 has_a_living_ancestorhas_a_living_ancestorなることがあることを意味しますが、うまくいけば早く捕らえられることを意味します。




私は、それぞれの人にマッピング(世代 - >日付の最初の子孫が生まれた)を取得することが役立つだろうかと思う。

日付は厳密に増加しなければならないので、バイナリ検索(またはきちんとしたデータ構造)を使用して、O(log n)時間でもっとも遠い生きた子孫を見つけることができます。

問題は、これらのリストを(少なくともnaiveに)マージすることはO(世代数)なので、これは最悪のケースではO(n ^ 2)になる可能性があるということです(AとBはCとDの両親、 EとFの...)。

私はまだ最善のケースがどのように働いているのかを試して、最悪のケースをよりよく特定しようとします(そして、それらの回避策があるかどうかを見てください)




ここに私の刺し傷があります:

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();



Related