تعبير Lambda العريض للعثور على المسار (المسار) من خلال رسم بياني موجه؟

Question

أحتاج إلى العثور على مسار أو مسارات أسفل بنية رسم بياني معقد. تم تصميم الرسم البياني باستخدام شيء مشابه لهذا:

class Node
{
    public string Value { get; set;}
    public List<Node> Nodes { get; set;}

    public Node()
    {
        Nodes = new List<Node>();
    }
}

ما يجعل هذا المعقد هو أن العقد يمكن الرجوع إلى عقدة سابقة. علي سبيل المثال،

أ -> ج -> E ->

ما أحتاج إليه هو الحصول على قائمة من كدسات تمثل المسارات من خلال العقد حتى أصل إلى عقدة بقيمة محددة. نظرا لأنه يمكن أن يكون هناك بعض المسارات الكبيرة للغاية المتوفرة، فيمكننا الحصول على أقصى العقد لمحاولة.

List<Stack<Node>> paths = FindPaths(string ValueToFind, int MaxNumberNodes);

هل لدى أي شخص طريقة لبناء هذا (أو شيء مماثل)؟ لقد قمت بالإعدام في الماضي ولكني أواجه ضرطة دماغية في التفكير في هذا الأمر لسبب ما. حدد سؤالي تعبير لامدا ولكن استخدام Lambda غير مطلوب بالضرورة. سأكون ممتنا لأي حل.

ملاحظة جانبية: رفعت الفصل من إجابة AKU الممتازة هذا السؤال العريضة. وبعد في حين أن محلوله الأنيق الذي يظهر أدناه يعبر بنية الشجرة لا يبدو أنه يسمح بمرونة كافية للقيام بما أحتاج إليه (على سبيل المثال، رفض المسارات التي هي مسارات دائرية وتتبعها الناجحة).

Action<Node> traverse = null;
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};
traverse(root);  // where root is the tree structure

يحرر:

بناء على المدخلات من التعليقات والأجوبة أدناه وجدت حل ممتاز في CodeProject. يستخدم خوارزمية العثور على المسار *. ها هو الرابط الالكتروني.

Answer 1

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

قد ترغب أيضا في إلقاء نظرة على خوارزمية Dijsktra.

Answer 2

لست متأكدا مما إذا كان الإخراج المقصود الخاص بك هو الكل مسارات إلى الهدف، أفضل المسار إلى الهدف (من قبل بعض القياسي، مثل طول المسار)، أو فقط أي الطريق إلى الهدف.

على افتراض أن الأخير، سأبدأ بالاستراتيجية العودية، بما في ذلك تتبع العقد التي تمت زيارتها على النحو المبين بواسطة Brann، وجعل هذه التغييرات:

1. أضف معلمات لتمثيل الهدف الذي يتم البحث عنه، وجمع المسارات الناجحة، والمسار الحالي من البداية.

2. عند إدخال عقدة تتطابق مع الهدف، أضف المسار الحالي (بالإضافة إلى العقدة الحالية) إلى قائمة المسارات الناجحة.

3. قم بتوسيع المسار الحالي مع العقدة الحالية لإنشاء المسار الذي تم تمريره في أي مكالمة متكررة.

4. استدعاء الأولي ExploreGraph اتصل بمسار فارغ وقائمة فارغة من المسارات الناجحة.

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

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

Answer 3

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

مثال :

  public void ExploreGraph(TreeNode tn, Dictionary<TreeNode, bool> visitednodes)
        {

            foreach (Treenode childnode in tn.Nodes)
            {
                if (!visitedNodes.ContainsKey(childnode))
                {
                    visitednodes.Add(childnode);
                    ExploreGraph(childnode, visitednodes);
                }
            }
        }