فرز طوبولوجي

قراءة إضافية

وفي هذا السياق، برتراند ماير ، لمسة من الطبقة: تعلم البرمجة بشكل جيد مع الكائنات والعقود ، سبرينغر ، 2009، الفصل 15، ابتكار وهندسة خوارزمية: الفرز الطوبولوجي ، باستخدام لغة برمجة حديثة، لتقديم تربوي مفصل للفرز الطوبولوجي (باستخدام أحد متغيرات خوارزمية كان) مع مراعاة تصميم بنية البيانات، وتصميم واجهة برمجة التطبيقات، ومخاوف هندسة البرمجيات.

من جانب آخر، دي كنوث ، فن برمجة الكمبيوتر ، المجلد 1، القسم 2.2.3، الذي يقدم خوارزمية للفرز الطوبولوجي للترتيب الجزئي، وتاريخًا موجزًا.

أضف v إلى Q

في حين أن الحجم العالمي لـ Q > 0

تطبيق لإيجاد أقصر مسار

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

• Loop over the vertices as ordered in , starting from :
• For each vertex directly following (i.e., there exists an edge from to ):
• Let be the weight of the edge from to .
• Relax the edge: if , set

وعلى صعيد آخر، Let be an array of the same length as , with all elements initialized to . Each will hold the predecessor of in the shortest path from to .

إضافةً إلى ذلك، Let be an array of the same length as ; this will hold the shortest-path distances from . Set , all other .

,

• Loop over the vertices as ordered in , starting from :
• For each vertex into (i.e., there exists an edge from to ):
• Let be the weight of the edge from to .
• Relax the edge: if , set

.

وفي السياق ذاته، Let be an array of the same length as , with all elements initialized to . Each will hold the predecessor of in the shortest path from to .

علاوةً على ذلك، Let be an array of the same length as ; this will hold the shortest-path distances from . Set , all other .

إذا كان الرسم البياني له حواف، إذن

خطأ العودة (الرسم البياني يحتوي على دورة واحدة على الأقل)

الخوارزميات

من جانب آخر، تُحقق الخوارزميات الشائعة للفرز الطوبولوجي زمن تنفيذ خطيًا لعدد العقد إلى جانب عدد الحواف، بشكل مقارب،

الخوارزميات المتوازية

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

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

كذلك، على جهاز وصول عشوائي متوازي ، يُمكن بناء ترتيب طوبولوجي بزمن O ((log n ) 2 ) باستخدام عدد كثير من المعالجات متعدد الحدود، مما يَضَعُ المُشكلة ضمن فئة التعقيد NC 2.

وفي هذا الصدد، بعد إزالة جميع الرؤوس في ،تُرسل الرسائل المجمعة إلى عناصر المعالجة المعينة.

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

وفي هذا السياق، خوارزمية للترتيب الطوبولوجي المتوازي على آلات الذاكرة الموزعة تقوم بتمرير خوارزمية كان لـ DAG .

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

من جهة ثانية، في الخطوة الأولى، يقوم PE بإسناد الفهارس: إلى الرؤوس المحلية في .

إضافةً إلى ذلك، فيما يلي، يُفترض أن تقسيم الرسم البياني مخزّن على p من عناصر معالجة (PE)، والموسومة بالأرقام .

ومن جهة أخرى، في الخطوة ، يقوم PE بِتَعيين المُؤشِرات ، أين هُو العَدَد الإجمَالي للرؤوس المُعَالَجة بَعدَ تُتَكرر هَذِهِ العَملية حتى لا يَتبقى أي رؤوس لمُعَالجَتها، وبالتالي . وهذه نظرة عامة على الكود الزائف لبرنامج واحد عالي المستوى وبيانات متعددة لهذه الخوارزمية.

تُزال هذه الرؤوس في مع الحواف الخارجة منها.

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

• لاحظ أن مجموع البادئة للإزاحات المحلية يمكن حسابها بكفاءة بالتوازي.
• عناصر معالجة p ذات معرفات من 0 إلى p -1
• المدخلات: G = (V, E) DAG، موزعة على PEs، مؤشر PE j = 0، ... ، ص - 1
• الإخراج: الفرز الطوبولوجي لـ G
• دالة traverseDAGDistributed
• δ الدرجة الواردة للرؤوس المحلية V
• // جميع الرؤوس ذات الدرجة الداخلية 0
• عدد الرؤوس المعالجة = 0

ومن ناحية أخرى، على مستوى عالٍ، تقوم خوارزمية Kahn بإزالة الرؤوس ذات الدرجة الداخلية 0 بشكل متكرر و إضافتها إلى الترتيب الطوبولوجي حسب الترتيب الذي أُزيلت فيه.

التفرد

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

أضف n إلى رأس L

من جهة ثانية، هذه الخوارزمية المبنية على البحث بالعمق هي التي وصفها ؛ ويبدو أنها وُصفت لأول مرة في المطبوعات بِوَاسِطة تارجان في سنة 1976.

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

من جانب آخر، و بِمَا أنَّ كُلَ حَافة ورَأس يَتِمَ زِيَارَتُهُ مَرة وَاحِدَة، فإن الخوارزمِية تَعمل بِزَمن خَطِي.

أضف n إلى L

لكل عقدة m ذات حافة e من n إلى m

البحث المتعمق

L ← قائمة فارغة تحتوي على العقد المصنفة

في حين أن هناك عقدًا بدون علامة دائمة ،

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

يفعل

لكل u في Q

وفي هذا الصدد، offset = nrOfVerticesProcessed + sum(Q i, i = 0 to j - 1) // j هو مؤشر المعالج

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

أمثلة

من جانب آخر، في علم الحاسوب، تَظهر تطبيقات من هذا النوع في مجالات مُتعددة، منها: جدولة التعليمات ، وترتيب تقييم خلايا الصيغ عند إعادة حساب القيم في جدولة البيانات ، وتوليف المنطق الرقمي ، وتحديد ترتيب مهام التجميع التي يجب القيام بها في ملفات Makefiles ، وتسلسل البيانات، وحل تبعيات الرموز في الروابط . ويَتم استخدامه كذلك لتحديد الترتيب الذي يتم به تحميل الجداول ذات المفاتيح الأجنبية في قواعد البيانات.

كذلك، يُعد التطبيق النموذجي للفرز الطوبولوجي هو جدولة سلسلة من الوظائف أو المهام بناءً على علاقات الاعتمادية بينها. تُمثَّّل الوظائف برؤوس(عُقد)، وتكون هناك حافة من x إلى y إذا كان لا بد من إتمام المهمة x قبل أن تبدأ المهمة y (مثلًا، عند غسل الملابس، يجب أن تنتهي الغسالة من عملها قبل وضع الملابس في المجفف).

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

آخر

وفي السياق ذاته، نظرًا لعدم تفرد النوع الناتج، يمكن أن تكون البنية S عبارة عن مجموعة أو طابور أو كومة أو مكدس.

ومن ناحية أخرى، إذا كان المخطط البياني عبارة عن DAG ، فستحتوي القائمة L (مع الملاحظة أن الحل ليس بالضرورة فريدًا). بخلاف ذلك، يجب أن يحتوي الرسم البياني على دورة واحدة على الأقل وبالتالي يكون الفرز الطوبولوجي مستحيلاً.

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

العودة L (ترتيب مرتب طوبولوجيًا)

إزالة الحافة e من الرسم البياني

أدخل m في S

إذا لم يكن لدى m أي حواف واردة أخرى ، فإن

إرجاع الطلب المحلي

وفي السياق ذاته، تعتمد تكلفة الاتصال بدرجة كبيرة على قسم الرسم البياني المُعطى. أما بالنسبة لوقت التشغيل، ففي نموذج CRCW-PRAM الذي يَسمح بالجلب والتناقص في وقتٍ ثابت، تَعمل هذه الخوارزمية في الزمن حيث إن : هو مرة أطول مسار في و الدرجة العُظمى لأي رأس في G.

العلاقة بالأوامر الجزئية

وفي هذا الصدد، أما الامتداد الخطي للترتيب الجزئي، هو ترتيب كلي يتوافق معه، بمعنى أنه إذا كان x ≤ y في الترتيب الجزئي، فإنه يجب أن يكون x ≤ y كذلك في الترتيب الكلي.

في هذا الإطار، إنشاء مخطط يحتوي على رأس لكل عنصر في مجموعة الترتيب الجزئي ، ورسم حافة xy لكل زوج من الكائنات التي يكون x لها ≤ ي .

كذلك، المجموعة المرتبة جزئيًا هي ببساطة مجموعة من العناصر تعريف لعلاقة عدم المساواة "≤"، مما يُلبي مسلمات الانعكاسية ( x ≤ x )، التناظر المضاد (إذا x ≤ ي و ي ≤ x ثم x = y ) والتعدية (إذا x ≤ ي و ي ≤ z ، ثم x ≤ ز ).

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

هناك طريقتان لبناء هذا النوع من المخططات:

إضافةً إلى ذلك، يمكن تعريف ترتيب جزئي انطلاقًا من أي مخطط بياني موجه لا دوريًا (DAG )، وذلك باعتبار مجموعة العناصر هي رؤوس DAG، وتحديد x ≤ يكون y بأنها صحيحًا لأي رأسين x و y ، كلما وُجد مسار مُوجَّه من x إلى y ؛ أي كلما أمكن الوصول إلى y من x . بهذه التعريفات، يكون الترتيب الطوبولوجي لـ DAG هو نفسه الامتداد الخطي لهذا الترتيب الجزئي. و بالعكس، يمكن تعريف أي ترتيب جزئي باعتباره علاقة الوصول في مخطط DAG.

ومن ناحية أخرى، أما الترتيبات الكلية هو ترتيب جزئي حيث لكل كائنين x و y في المجموعة، إما x أو y ≤ ي أو ي ≤ x . تعتبر الطلبات الإجمالية مألوفة في علوم الحاسوب باعتبارها مشغلي المقارنة اللازمين لأداء خوارزميات فرز المقارنة . بالنسبة للمجموعات المنتهية، يمكن تمثيل الترتيب الكلي بتسلسل خطي من العناصر، حيثُ تَكُون العَلاقة "≤" صحيحة كلما سَبَقَ العنصر الأول العنصر الثاني في الترتيب؛ ويمكن استخدام خوارزمية فرز المقارنة لتحويل الترتيب الكلي إلى تسلسل بهذه الطريقة.

وفي السياق ذاته، الترتيبات الطوبولوجية ترتبط ارتباطًا وثيقًا بمفهوم الامتداد الخطي للترتيب الجزئي في الرياضيات.

خوارزمية خان

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

• L ← قائمة فارغة تحتوي على العناصر المصنفة
• S ← مجموعة من جميع العقد بدون حافة واردة
• في حين أن S ليست فارغة، افعل
• إزالة عقدة n من S

حدد عقدة غير مميزة n

• زيارة( ن )
• دالة الزيارة (العقدة n )
• إذا كان n له علامة دائمة، إذن

الروابط الخارجية

قاموس NIST للخوارزميات وهياكل البيانات: الترتيب الطوبولوجي

,

ومن جهة أخرى، .في الرسم البياني المكون من رأسًا و حافة، تأخذ هذه الخوارزمية ، أي زمنًا خطيًا .

ضع علامة n بعلامة مؤقتة

• لِكلُ عقدة m ذات حافة من n إلى m
• زيارة( م )
• علامة n بعلامة دائمة

العلاقة بتحسين الجدولة

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

المراجع

إزالة جميع الرؤوس في Q

لكل رسالة ( u, v ) مستلمة:

إذا --δ[v] = 0

يعود

توقف (يحتوي الرسم البياني على دورة واحدة على الأقل)

إذا كان n له علامة مؤقتة ،

localOrder[u] = index++;

• foreach (u,v) في E قم بنشر الرسالة ( u, v ) إلى PE صاحب الرأس v
• توصيل جميع الرسائل إلى جيران الرؤوس في Q
• استقبال الرسائل للرؤوس المحلية V