اجتياز الرسم البياني

في علم الحاسوب ، يُشير مصطلح اجتياز الرسم البياني (المعروف أيضًا باسم البحث في الرسم البياني ) إلى عملية زيارة (فحص و/أو تحديث) كل رأس في الرسم البياني . تُصنّف عمليات الاجتياز هذه حسب ترتيب زيارة الرؤوس. يُعدّ اجتياز الشجرة حالة خاصة من اجتياز الرسم البياني.

التكرار

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

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

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

خوارزميات اجتياز الرسوم البيانية

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

البحث العميق أولاً

البحث العميق أولاً (DFS) هو خوارزمية لاجتياز رسم بياني محدود. تزور خوارزمية DFS رؤوس الأبناء قبل زيارة رؤوس الأشقاء؛ أي أنها تجتاز عمق أي مسار معين قبل استكشاف عرضه. يُستخدم عادةً مكدس (غالباً مكدس استدعاءات البرنامج عبر الاستدعاء الذاتي ) عند تنفيذ الخوارزمية.

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

تعتبر خوارزمية البحث العمقي أولاً (DFS) أساسًا للعديد من الخوارزميات المتعلقة بالرسوم البيانية، بما في ذلك الفرز الطوبولوجي واختبار التسطح .

الشفرة الزائفة

المدخلات : رسم بياني G ورأس v من G.
الناتج : تصنيف الحواف في المكون المتصل من v على أنها حواف اكتشاف وحواف خلفية.

الإجراء DFS( G , v ) يُصنّف v على أنه مُستكشف. لكل حافة e في G.incidentEdges ( v ) ، إذا كانت الحافة e غير مُستكشفة، فإن w ← G.adjacentVertex ( v , e ). إذا كان الرأس w غير مُستكشف، فإن e يُصنّف على أنه حافة مُكتشفة. استدعِ خوارزمية البحث العمقي أولاً (DFS) بشكل متكرر ( G , w ) وإلا فقم بتسمية e كحافة خلفية

البحث بالعرض أولاً

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

الشفرة الزائفة

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

الإجراء BFS( G , v ) هو: إنشاء طابور Q ، إضافة v إليه ، وضع علامة عليه . طالما أن Q غير فارغة، قم بما يلي: w ← Q.dequeue () ، إذا كان w هو المطلوب، فأرجعه . لكل حافة e في G.adjacentEdges ( w ) ، قم بما يلي: x ← G.adjacentVertex ( w , e ) ، إذا لم تكن x مُعلَّمة، فضع علامة عليها ، وأضفها إلى Q، ثم أرجع null.

التطبيقات

يمكن استخدام البحث بالعرض أولاً لحل العديد من المشاكل في نظرية الرسم البياني، على سبيل المثال:

إيجاد جميع الرؤوس داخل مكون متصل واحد ؛
خوارزمية تشيني ؛
إيجاد أقصر مسار بين رأسين؛
اختبار الرسم البياني للتأكد من كونه ثنائي الأجزاء ؛
ترقيم الشبكة باستخدام خوارزمية كوثيل-مكي ؛
خوارزمية فورد-فولكرسون لحساب أقصى تدفق في شبكة التدفق ؛
التسلسل/فك التسلسل لشجرة ثنائية مقابل التسلسل بترتيب فرز (يسمح بإعادة بناء الشجرة بطريقة فعالة)؛
خوارزميات توليد المتاهات ؛
خوارزمية ملء الفيضان لتحديد المناطق المتجاورة في صورة ثنائية الأبعاد أو مصفوفة متعددة الأبعاد؛
تحليل الشبكات والعلاقات.

استكشاف الرسم البياني

يمكن اعتبار مشكلة استكشاف الرسم البياني نوعًا من أنواع اجتياز الرسم البياني. وهي مشكلة آنية ، أي أن المعلومات المتعلقة بالرسم البياني لا تُكشف إلا أثناء تشغيل الخوارزمية. النموذج الشائع هو كالتالي: لدينا رسم بياني متصل G = ( V , E ) بأوزان حواف غير سالبة. تبدأ الخوارزمية من رأس معين، وتعرف جميع الحواف المتصلة به والرؤوس الموجودة في نهايته - لا أكثر. عند زيارة رأس جديد، تُعرف جميع الحواف المتصلة به والرؤوس الموجودة في نهايته. الهدف هو زيارة جميع الرؤوس n والعودة إلى رأس البداية، مع الحرص على أن يكون مجموع أوزان المسار أصغر ما يمكن. يمكن أيضًا فهم هذه المشكلة على أنها نسخة محددة من مشكلة البائع المتجول ، حيث يتعين على البائع اكتشاف الرسم البياني أثناء تنقله.

بالنسبة للرسوم البيانية العامة، فإن أفضل الخوارزميات المعروفة لكل من الرسوم البيانية غير الموجهة والموجهة هي خوارزمية جشعة بسيطة :

في حالة عدم التوجيه، يكون طول المسار الجشع أطول من المسار الأمثل بمقدار O (ln n ) مرة على الأكثر. ^{[ 1 ]} أفضل حد أدنى معروف لأي خوارزمية حتمية متصلة بالإنترنت هو 10/3. ^{[ 2 ]}
- يمكن استكشاف الرسوم البيانية غير الموجهة ذات الوزن الواحد بنسبة تنافسية تبلغ 2 − ε ، ^{[ 3 ]} وهو حد ضيق بالفعل على الرسوم البيانية من نوع Tadpole . ^{[ 4 ]}
في حالة التوجيه، يكون طول المسار الجشع أطول من المسار الأمثل بمقدار ( n - 1 ) مرة على الأكثر . وهذا يتوافق مع الحد الأدنى n - 1. ^{[ 5 ]} وينطبق حد أدنى تنافسي مماثل Ω ( n ) على الخوارزميات العشوائية التي تعرف إحداثيات كل عقدة في تمثيل هندسي. إذا كان المطلوب إيجاد عقدة "كنز" واحدة فقط بدلًا من زيارة جميع العقد، فإن الحدود التنافسية تكون Θ ( n² ⁾ على الرسوم البيانية الموجهة ذات الوزن الواحد، وذلك لكل من الخوارزميات الحتمية والعشوائية.

تسلسلات الاجتياز العالمية

سلسلة الاجتياز الشاملة هي سلسلة من التعليمات التي تشمل اجتياز أي رسم بياني منتظم ذي عدد محدد من الرؤوس، ولأي رأس بداية. استخدم أليليوناس وآخرون برهانًا احتماليًا لإثبات وجود سلسلة اجتياز شاملة بعدد تعليمات يتناسب مع O ( n^ ⁵ ) لأي رسم بياني منتظم ذي n رأسًا. ^{[ 6 ]} الخطوات المحددة في السلسلة نسبية للعقدة الحالية، وليست مطلقة. على سبيل المثال، إذا كانت العقدة الحالية هي vj ، وكان لـ vj _عدد d _من الجيران ، فإن سلسلة الاجتياز ستحدد العقدة التالية التي يجب زيارتها، vj ₊₁ ، على أنها الجار ^رقمi _لـ vj ، حيث 1 ≤ i ≤ d .

انظر أيضاً

اجتياز الرسم البياني للذاكرة الخارجية

مراجع

↑ روزنكرانتز، دانيال ج.؛ ستيرنز، ريتشارد إي.؛ لويس الثاني، فيليب م. (1977). "تحليل لعدة طرق استدلالية لمسألة البائع المتجول". مجلة SIAM للحوسبة . 6 (3): 563-581 . doi : 10.1137/0206041 . S2CID 14764079 .
↑ بيركس، ألكسندر؛ ديسر، يان؛ هوب، ألكسندر ف.؛ كاروساتو، كريستينا (مايو 2021). "حد أدنى مُحسَّن لاستكشاف الرسوم البيانية التنافسي". علوم الحاسوب النظرية . 868 : 65-86 . arXiv : 2002.10958 . doi : 10.1016/j.tcs.2021.04.003 . S2CID 211296296 .
↑ ميازاكي، شويتشي؛ موريموتو، ناويوكي؛ أوكابي، ياسوو (2009). "مشكلة استكشاف الرسوم البيانية عبر الإنترنت على الرسوم البيانية المقيدة". مجلة IEICE للمعاملات في المعلومات والأنظمة . E92-D (9): 1620-1627 . Bibcode : 2009IEITI..92.1620M . doi : 10.1587/transinf.E92.D.1620 . hdl : 2433/226939 . S2CID 8355092 .
↑ براندت، سيباستيان؛ فورستر، كلاوس-تيكو؛ ماورر، جوناثان؛ واتنهوفر، روجر (نوفمبر 2020). "استكشاف الرسوم البيانية عبر الإنترنت على فئة رسوم بيانية مقيدة: حلول مثلى لرسوم بيانية على شكل شرغوف". علوم الحاسوب النظرية . 839 : 176-185 . arXiv : 1903.00581 . doi : 10.1016/j.tcs.2020.06.007 . S2CID 67856035 .
↑ فورستر، كلاوس-تيكو؛ واتنهوفر، روجر (ديسمبر 2016). "الحدود التنافسية الدنيا والعليا لاستكشاف الرسوم البيانية الموجهة عبر الإنترنت" . علوم الحاسوب النظرية . 655 : 15-29 . doi : 10.1016/j.tcs.2015.11.017 .
↑ أليليوناس، ر.؛ كارب، ر.؛ ليبتون، ر.؛ لوفاس، ل.؛ راكوف، س. (1979). "المسارات العشوائية، وتسلسلات الاجتياز الشاملة، وتعقيد مسائل المتاهة". الندوة السنوية العشرون حول أسس علوم الحاسوب (SFCS 1979) . الصفحات 218-223 . doi : 10.1109/SFCS.1979.34 . S2CID 18719861 .

[1] روزنكرانتز، دانيال ج.؛ ستيرنز، ريتشارد إي.؛ لويس الثاني، فيليب م. (1977). "تحليل لعدة طرق استدلالية لمسألة البائع المتجول". مجلة SIAM للحوسبة . 6 (3): 563-581 . doi : 10.1137/0206041 . S2CID 14764079 .

[2] بيركس، ألكسندر؛ ديسر، يان؛ هوب، ألكسندر ف.؛ كاروساتو، كريستينا (مايو 2021). "حد أدنى مُحسَّن لاستكشاف الرسوم البيانية التنافسي". علوم الحاسوب النظرية . 868 : 65-86 . arXiv : 2002.10958 . doi : 10.1016/j.tcs.2021.04.003 . S2CID 211296296 .

[3] ميازاكي، شويتشي؛ موريموتو، ناويوكي؛ أوكابي، ياسوو (2009). "مشكلة استكشاف الرسوم البيانية عبر الإنترنت على الرسوم البيانية المقيدة". مجلة IEICE للمعاملات في المعلومات والأنظمة . E92-D (9): 1620-1627 . Bibcode : 2009IEITI..92.1620M . doi : 10.1587/transinf.E92.D.1620 . hdl : 2433/226939 . S2CID 8355092 .

[4] براندت، سيباستيان؛ فورستر، كلاوس-تيكو؛ ماورر، جوناثان؛ واتنهوفر، روجر (نوفمبر 2020). "استكشاف الرسوم البيانية عبر الإنترنت على فئة رسوم بيانية مقيدة: حلول مثلى لرسوم بيانية على شكل شرغوف". علوم الحاسوب النظرية . 839 : 176-185 . arXiv : 1903.00581 . doi : 10.1016/j.tcs.2020.06.007 . S2CID 67856035 .

[5] فورستر، كلاوس-تيكو؛ واتنهوفر، روجر (ديسمبر 2016). "الحدود التنافسية الدنيا والعليا لاستكشاف الرسوم البيانية الموجهة عبر الإنترنت" . علوم الحاسوب النظرية . 655 : 15-29 . doi : 10.1016/j.tcs.2015.11.017 .

[6] أليليوناس، ر.؛ كارب، ر.؛ ليبتون، ر.؛ لوفاس، ل.؛ راكوف، س. (1979). "المسارات العشوائية، وتسلسلات الاجتياز الشاملة، وتعقيد مسائل المتاهة". الندوة السنوية العشرون حول أسس علوم الحاسوب (SFCS 1979) . الصفحات 218-223 . doi : 10.1109/SFCS.1979.34 . S2CID 18719861 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]