اكتشف دورات في رسم بياني لعلم الأنساب أثناء البحث الأول

Question

أقوم بتحميل بيانات الأنساب الحصان بشكل متكرر. بالنسبة لبعض المجموعات الخاطئة من البيانات ، لا تتوقف عودتي أبدًا ... وذلك لأن هناك دورات في البيانات.

كيف يمكنني اكتشاف تلك الدورات للتوقف عن التكرار؟

فكرت أثناء تكرارها في الحفاظ على علامة تجزئة مع جميع الخيول "التي تمت زيارتها". لكن هذا سيجد بعض الإيجابيات الخاطئة ، لأن الحصان يمكن أن يكون مرتين في شجرة.

ما لا يمكن أن يحدث هو أن الحصان يظهر كأب أو جد أو جد عظيم بنفسه.

Answer 1

كود مزيف:

void ProcessTree(GenTreeNode currentNode, Stack<GenTreeNode> seen)
{
   if(seen.Contains(currentNode)) return;
   // Or, do whatever needs to be done when a cycle is detected

   ProcessHorse(currentNode.Horse); // Or whatever processing you need

   seen.Push(currentNode);

   foreach(GenTreeNode childNode in currentNode.Nodes)
   {
      ProcessTree(childNode, seen);
   }

   seen.Pop();
}

الفكرة الأساسية هي الاحتفاظ بقائمة لجميع العقد التي رأيناها بالفعل في طريقنا إلى العقدة الحالية ؛ إذا تم العودة إلى عقدة مررنا بها بالفعل ، فأنت تعلم أننا قمنا بتشكيل دورة (وعلينا أن نتخطى القيمة ، أو نفعل كل ما يجب القيام به)

Answer 2

الحفاظ على كومة من جميع العناصر التي تؤدي إلى جذر الشجرة.

في كل مرة تتقدم فيها أسفل الشجرة ، قم بمسح المكدس للعنصر الطفل. إذا وجدت تطابقًا ، فقد اكتشفت حلقة ويجب أن تتخطى هذا الطفل. خلاف ذلك ، ادفع الطفل إلى المكدس ومتابعة. كلما قمت بتراجع الشجرة ، قم بإخراج عنصر من المكدس وتجاهله.

(في حالة بيانات الأنساب ، يُفترض أن العقدة "الطفل" في الشجرة هي الوالد البيولوجي للعقدة "الوالد".)

Answer 3

هذا يبدو وكأنه حالة يمكنك من خلالها أخيرًا تطبيق سؤال التوافه المقابلة: ابحث عن دورة في قائمة مرتبطة باستخدام ذاكرة O (1) فقط.

في هذه الحالة ، "القائمة المرتبطة" هي تسلسل العناصر التي تعددها. استخدم اثنين من العدادات ، وقم بتشغيل واحد بسرعة نصف السرعة ، وإذا كان الصيام يركض في البطيء ، فأنت لديك حلقة. سيكون هذا أيضًا وقت O (n) بدلاً من الوقت O (n^2) المطلوب للتحقق من قائمة "المشاهدة". الجانب السلبي هو أنك تعرف فقط عن الحلقة بعد معالجة بعض العقد عدة مرات.

في المثال ، قمت باستبدال طريقة "نصف السرعة" بأسلوب علامات إسقاط أبسط إلى وصول.

class GenTreeNode {
    ...

    ///<summary>Wraps an the enumeration of linked data structures such as trees and linked lists with a check for cycles.</summary>
    private static IEnumerable<T> CheckedEnumerable<T>(IEnumerable<T> sub_enumerable) {
        long cur_track_count = 0;
        long high_track_count = 1;
        T post = default(T);
        foreach (var e in sub_enumerable) {
            yield return e;
            if (++cur_track_count >= high_track_count) {
                post = e;
                high_track_count *= 2;
                cur_track_count = 0;
            } else if (object.ReferenceEquals(e, post)) {
                throw new Exception("Infinite Loop");
            }
        }
    }

    ...

    ///<summary>Enumerates the tree's nodes, assuming no cycles</summary>
    private IEnumerable<GenTreeNode> tree_nodes_unchecked() {
        yield return this;
        foreach (var child in this.nodes)
            foreach (var e in child.tree_nodes_unchecked())
                yield return e;
    }
    ///<summary>Enumerates the tree's nodes, checking for cycles</summary>
    public IEnumerable<GenTreeNode> tree_nodes()
    {
        return CheckedEnumerable(tree_nodes_unchecked());
    }

    ...

    void ProcessTree() {
        foreach (var node in tree_nodes())
            proceess(node);
    }
}

Answer 4

طريقة بسيطة للغاية لاكتشاف هذا ، عن طريق التحقق من هذا القيد نفسه:

ما لا يمكن أن يحدث هو أن الحصان يظهر كأب أو جد أو الحفيد العظيم بنفسه.

كلما قمت بإدخال عقدة في شجرتك ، اجتاز الشجرة إلى الجذر للتأكد من عدم وجود الحصان كأي نوع من الوالدين.

لتسريع هذا الأمر ، يمكنك ربط علامة التجزئة بكل عقدة ، حيث تقوم بتخزين إجابة مثل هذا البحث. ثم ليس عليك البحث في المسار بأكمله في المرة القادمة التي تقوم فيها بإدخال حصان أسفل تلك العقدة.

Answer 5

يجب أن يعمل حل جدول التجزئة إذا كنت تتبع العقد بدلاً من الخيول. فقط تأكد من أن تقرأ حصانًا جديدًا تقوم بإنشاء عقدة جديدة حتى لو كانت القيمة/الحصان هي نفس قيمة/حصان العقدة السابقة.

Answer 6

أنت تتعامل مع أ إخراج الرسم البياني الحشيش, وليس شجرة. لا ينبغي أن تكون هناك أي دورات ، لأن سليل الحصان لا يمكن أن يكون أجداده أيضًا.

معرفة ذلك ، يجب عليك تطبيق تقنيات التعليمات البرمجية الخاصة بالرسوم البيانية الموجه.