لتوضيح ما يدور حوله هذا ، سأقدم أبسط مثال.
الرسم البياني بسيط للغاية ، وبالنسبة لهذا النوع من الرسم البياني ، من السهل التوصل إلى خوارزمية تختار الدورات بدون وتر (أي الدورات التي لا تحتوي على تقاطعات ذاتية ولا يمكن تقسيمها إلى دورات أصغر). تكمن المشكلة في أن الرسوم البيانية يمكن أن تكون أكثر تعقيدًا ، ويجب النظر في جميع الحالات. من خلال المداولات والترميز والتجربة والخطأ ، في النهاية ولدت الخوارزمية ، والتي تعمل الآن لصالح المنقبين الهندسيين.
وصف النص:
- لكل رأس من رؤوس الرسم البياني ، نجد جميع الرؤوس المجاورة ونبدأ في تكوين دورة من خلال التحرك باتجاه كل رأس مجاور بدوره.
- إذا كان عدد الرؤوس المجاورة (باستثناء التي أدخلتها) = 0 ، فإننا نعود لنشكل دورة ---> العنصر 5
- إذا كان عدد الرؤوس المجاورة (باستثناء الرأس الذي أدخلته) يساوي 1 ، فسنمضي على طوله ، ونشكل دورة ---> العنصر 5
- ( , ) >=2, ( ), , ---> .5
- — ? , ---> .2
- , .
- , , , .
- , , ---> .1 ( )
- مرة أخرى نمر بالدورة وننظر إلى الفروع اليسرى منها. بعد العثور على مثل هذه الفروع ، ننظم لكل منها بحثًا واسعًا أولاً (أو العمق أولاً ، لا يهم). إذا انتهى بنا الأمر في نفس الوقت إلى قمة الدورة المشكلة (باستثناء الدورة الحالية) ، فإننا نقطع تشكيل الدورة وننتقل إلى ---> العنصر 1
- نكتب الدورة ونذهب للبحث عن دورة جديدة ---> البند 1
رمز زائف أكبر:
في البداية ، تم إنشاء المزيد والمزيد من الرسوم البيانية المعقدة لاختبار الخوارزمية.
أو
، في النهاية ، تم اختباره على جميع الرسوم البيانية الاستكشافية الحقيقية مثل هذا:
لا أعتقد أنه مثالي ، ولكنه يعمل حاليًا (3 سنوات بالفعل) دون إخفاقات أو شكاوى.
أنا لا أقتبس من الكود ، ولن يهتم به أي شخص تقريبًا ، وسيكون من الصعب سحب قطعة ، لأن هذا مجرد جزء صغير من العمل.