ما المقصود بالرسم البياني الموجَّه غير الدوري (DAG)؟

الرسم البياني الموجَّه غير الدوري (DAG) هو نوع من الرسوم البيانية تكون فيه العقد مرتبطة باتصالات أحادية الاتجاه لا تشكِّل أي دورات. ويُستخدَم لتوضيح التبعيات والعلاقات السببية.

مثل جميع الرسوم البيانية، يمكن أن تكون رسوم DAG مفيدة في تصور العلاقات بين العُقد التي تمثِّل البيانات أو المهام أو الأحداث. ومع ذلك، فإن رسوم DAG تكون مفيدة في تصوير الأنظمة التي تحدث فيها الأحداث بترتيب معين، مثل جدول المهام الذي يجب إكماله لتحقيق هدف.

تُعَد رسوم DAG مهمة أيضًا لإنشاء الرسوم البيانية السببية: تستطيع رسوم DAG تمثيل الأنظمة التي تؤثر فيها بعض العُقد على عُقد أخرى، لكن التأثيرات السببية لا تعمل في الاتجاه المعاكس. ويمكن العثور على مثال بسيط لهذه العلاقات أحادية الاتجاه في شجرات العائلة حيث تمثِّل رسوم DAG الأجيال المتعاقبة من الآباء والأبناء.

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

لفهم ماهية الرسم البياني الموجَّه غير الدوري بشكل أفضل، دعونا نقسِّم مكوناته:

العُقد: المعروفة أيضًا بالرؤوس، تمثِّل الكيانات أو الكائنات أو المتغيرات في الرسم البياني. ويتم تصويرها عادةً على شكل نقاط أو دوائر.

الحواف: تمثِّل الاتصالات بين الكيانات. ويتم تصويرها كخطوط.

الحواف الموجَّهة: تمثِّل الحواف الموجَّهة الاتصالات التي يمكن اجتيازها في اتجاه واحد فقط. وتُشير الأسهم الموجودة على هذه الحافة إلى اتجاهها.

الرسوم البيانية الموجَّهة: الرسوم البيانية التي تتكون بالكامل من حواف موجَّهة هي الرسوم البيانية الموجَّهة أو الرسوم البيانية الموجَّهة أحادية الاتجاه. على النقيض من ذلك، فإن الرسوم البيانية التي لا تحتوي على حواف موجَّهة هي الرسوم البيانية غير الموجَّهة.

المتقاطعات: هي العُقد التي تحتوي على حافتَين موجهتَين تشيران إليها.

المسارات: هي سلسلة من الحواف التي تربط عقدة معينة بأخرى. تُعرَف المسارات التي تتكون بالكامل من الحافة الموجَّهة بالمسارات الموجَّهة. والمسارات الموجَّهة التي تُشير إلى علاقات سببية تُسمَّى مسارات سببية.

الشجرة: في علوم الكمبيوتر، الشجرة هي رسم بياني موجَّه غير دوري، حيث كل عقدة لها حافة واحدة موجَّهة تُشير إليها، باستثناء عقدة البداية (عقدة "الجذر"). ورغم أن الحواف تنطلق من عقدة الجذر، إلا أنه لا توجد أي حواف تُشير إليها.

إلى جانب فهم مكونات الرسم البياني الموجَّه غير الدوري (DAG)، من المهم أيضًا إدراك المكوّن غير الموجود فيه: الدورة. يشير مصطلح "غير دوري" في الرسم البياني الموجَّه غير الدوري إلى غياب الدورات أو الحلقات المغلقة في هذا النوع من الرسوم البيانية. بعبارة أخرى، عند البدء من عقدة معينة في الرسم البياني الموجَّه غير الدوري (DAG) وتتبُّع العُقد والحواف التالية، لا يمكن العودة إلى عقدة البداية نفسها.

في نظرية الرسوم البيانية (دراسة الرسوم البيانية)، تُستخدَم العديد من المفاهيم أو العمليات عند التعامل مع الرسوم البيانية الموجَّهة غير الدورية. وتشمل ما يلي:

• الفرز الطوبولوجي
• الإغلاق الانتقالي
• الاختزال الانتقالي

الفرز الطوبولوجي، ويُعرَف أيضًا بالترتيب الهيكلي، هو أسلوب لتنظيم عقد الرسم البياني الموجَّه غير الدوري (DAG) بطريقة خطية بحيث تظهر العقد التي تُشير إلى عقد أخرى أولًا، ولا تسبق العقد التابعة العقد التي تسبقها. يمكن لخوارزميات الفرز الطوبولوجي إنتاج مثل هذه التتابعات اعتمادًا على الرسوم البيانية الموجَّهة غير الدورية (DAGs).¹

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

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

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

على سبيل المثال، فكِّر في رسم بياني أصلي يحتوي على حافة موجهة تربط العقدة A بالعقدة C، وسلسلة من الحواف الموجهة تربط العقدة A بالعقدة B والعقدة B بالعقدة C. في الاختزال الانتقالي لهذا الرسم البياني، سيتم استبعاد الحافة بين A وC مع الحفاظ على الحواف بين مجموعة العقد الأكبر: A وB وB وC.

بمعنى آخر، يتم تضمين أطول مسار بين A و C في الرسم البياني الأصلي في الرسم البياني الجديد، بينما يتم حذف المسار الذي يحتوي على حافة واحدة فقط.

تظهر الرسوم البيانية الموجهة غير الدورية بشكل بارز في علوم الكمبيوتر من خلال مجموعة من حالات الاستخدام:

• معالجة البيانات
• الشبكات العصبية
• الاستدلال السببي في التعلم الآلي
• التشغيل الآلي
• تصميم المحول البرمجي
• سلسلة الكتل

تساعد الرسوم البيانية الموجهة غير الدورية مهندسي البيانات على تعريف هياكل البيانات وتحقيق التحسين في تدفقات البيانات. على سبيل المثال، تستخدِم منصات تنسيق البيانات، مثل Apache Airflow، الرسوم البيانية الموجهة غير الدورية (المعرفة في نصوص Python) لتعريف مهام معالجة البيانات وتحديد ترتيب تنفيذها في مسارات البيانات وعمليات سير العمل.

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

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

الشبكة العصبية هي برنامج تعلم آلي يتخذ قرارات بطريقة مشابهة للدماغ البشري باستخدام عمليات تحاكي كيفية عمل الخلايا العصبية البيولوجية معًا لإجراء الملاحظات والوصول إلى الاستنتاجات. تُستخدَم رسوم DAG لتخطيط الشبكات العصبية، ويمكن الاستفادة منها بشكل خاص في تصور الشبكات العصبية العميقة ذات الطبقات المتعددة.

يمكن أن تؤدي الرسوم البيانية الموجهة غير الدورية دورًا في الجهود المبذولة من أجل "تعليم" نماذج الذكاء الاصطناعي كيفية التعرُّف على العلاقات السببية من خلال الاستدلال السببي. الاستدلال السببي هو نموذج لتحديد التأثيرات السببية وغالبًا ما يستخدِم الرسوم البيانية الموجهة غير الدورية. على سبيل المثال، يمكن للرسوم البيانية الموجهة غير الدورية (DAGs) المساعدة على اكتشاف "المتشابكات"، وهي المتغيرات التي تشوّه أو تُخفِي السبب الحقيقي. يظهر الذكاء الاصطناعي المدعوم بالاستدلال السببي كأداة في علم الأوبئة بشكل خاص، مع إمكانية مساعدته للباحثين على دراساتهم لتحديد أسباب الأمراض.³

اقترح الباحثون استخدام طريقة تخطيط هيكلية تعتمد على الرسوم البيانية الموجهة غير الدورية (DAG) والنماذج اللغوية الكبيرة لتحسين أداء الروبوتات ذات الذراعين المزدوجتين. في الإطار المقترح، يُنشئ النموذج اللغوي الكبير رسمًا بيانيًا موجهًا غير دوري (DAG) يمثل المهام المعقدة كمهام فرعية، مع وجود الحواف التي تُشير إلى التبعيات بينها. في إطار العمل، يتم استخدام هذه المعلومات للمساعدة على تحديد تخطيط الحركة والتنسيق بين الذراعين لتنفيذ المهام.⁴

تُستخدَم الرسوم البيانية الموجهة غير الدورية (DAGs) لتحسين تصميم المحولات البرمجية، وهي برامج تعمل على تحويل لغات البرمجة (رمز المصدر) إلى تعليمات لأجهزة الكمبيوتر (رمز الآلة). على سبيل المثال، يمكن أن تساعد رسوم DAG على تحديد التعبيرات الفرعية الشائعة التي يمكن التخلص منها لتحسين الكفاءة.

وفقًا للباحثين، تُظهر سلسلة الكتل (البلوك تشين) المعتمدة على الرسم البياني الموجه غير الدوري (DAG) أداءً أفضل من سلاسل الكتل التقليدية. تُتيح سلسلة الكتل القائمة على رسوم DAG المعالجة المتوازية للمعاملات، وبالتالي زيادة معدل المعاملات التي تتم معالجتها في فترة معينة وتمكين المزيد من المرونة وقابلية التوسع. يمكن أن تكون هذه التحسينات مفيدة في مجالات مثل إدارة سلسلة التوريد والتحكم في الوصول لشبكات إنترنت الأشياء.⁵