التمثيلات البيانية
في القرن الثامن عشر، كان مواطنو مدينة كونيجسبرج الشرفاء يتجولون في شوارع المدينة في أيام الأحد بعد الظهيرة. بُنيت مدينة كونيجسبرج على ضفاف نهر بريجل. تسبَّب النهر في تكوين جزيرتين كبيرتين داخل المدينة، وكانت الجزيرتان متصلتين بالبر الرئيسي وبإحداهما الأخرى من خلال سبعة جسور في المجمل.
اجتاحت مدينة كونيجسبرج تقلبات التاريخ الأوروبي، فانتقلت من سيطرة فرسان التيوتون ثم أصبحت عاصمة بروسيا واجتاحتها روسيا ثم جمهورية فايمر ثم ألمانيا النازية، وبعد الحرب العالمية الثانية، أصبحت جزءًا من الاتحاد السوفييتي وتغيَّر اسمها إلى كالينينجراد، وهو الاسم الحالي للمدينة. إنها جزء من روسيا اليوم على الرغم من أنها ليست متصلة بالأراضي الروسية. تقع كالينينجراد داخل جيب روسي على بحر البلطيق، بين كل من بولندا وليتوانيا.
نمت المسألة إلى علم عالِم الرياضيات السويسري الشهير ليونهارت أويلر، لا نعرف تحديدًا كيف؛ إذ ورد ذكر المسألة في خطابٍ أُرسل يوم ٩ مارس ١٧٣٦ من عمدة مدينة دانزيج التي تقع في بروسيا على مسافة ٨٠ ميلًا شرقي كونيجسبرج (تغيَّر اسم دانزيج إلى جدانسك وتتبع بولندا). يبدو أن مراسلة أويلر كانت جزءًا من جهود عمدة المدينة لتشجيع ازدهار الرياضيات في بروسيا.
رسمنا كتل اليابسة في شكل دوائر والجسور في شكل خطوط تصل بين تلك الدوائر. ومِن ثَم يمكن إعادة صياغة المسألة على النحو التالي: إذا كان معك قلم رصاص، فهل يمكنك البدء من أي دائرة، وتخفض القلم الرصاص على الورقة وتتبع الخطوط من دون رفع القلم من فوق الورقة بحيث لا يمكن المرور على كل خط أكثر من مرة؟
يتألَّف الشَّكل الذي رسمناه من دوائرَ وخطوطٍ تصل بين تلك الدوائر. وعلى سبيل استخدام المصطلحات الصحيحة، فقد أنشأنا بنيةً تتكوَّن من «عُقد» أو «رءوس» تتصل ﺑ «حواف» أو «روابط» تصل بينها. يطلق على البنية التي تتكوَّن من مجموعاتٍ من العُقَد والحواف «التمثيل البياني»، وكان أويلر أوَّل مَن عرَّف التمثيلات البيانية باعتبارها بنيةً، واستكشفَ خصائصَها. بلغة اليوم، تتعامل مسألة جسور كونيجسبرج السبعة مع «المسارات»، والمسار في التمثيل البياني هو سلسلة من الحواف تصل بين سلسلةٍ من العُقَد. إذن، فمسألة كونيجسبرج تدور حول إيجاد «مسار أويلري» أو «طريق أويلري»، وهو خطٌّ يمر من خلال تمثيل بياني بحيث يمر من كل حافة مرة واحدة فقط. والمسار الذي يبدأ وينتهي عند النقطة نفسها يسمَّى «جولة» أو «دورة». وإذا أضفنا أيضًا قيدًا (ليس في المسألة الأصلية) يتمثَّل في بدء مسار أويلري من نقطة وانتهائه عند النقطة نفسها، يصبح لدينا ما يطلَق عليه «جولة أويلرية» أو «دورة أويلرية».
تطبيقات التمثيلات البيانية كثيرة لدرجة أنها قد تملأ كتبًا كاملة. أي شيء يمكن تمثيله بعُقَدٍ متصلة بعُقَد أخرى يمكن توضيحه بتمثيل بياني. بمجرد أن نفعل ذلك، يمكننا طرح كل الأسئلة المهمة بشأن التمثيل البياني؛ ولكن في هذا الكتاب، ستُتاح لنا الفرصة أن نلقي نظرة سريعة فقط.
الانتقال من التمثيلات البيانية إلى الخوارزميات
إن تعريف التمثيل البياني شامل لدرجة أنه قد يضم أيَّ شيء يمكن تمثيله في صورة عناصر مرتبطة بعناصر أخرى. قد يتشابه التمثيل البياني في بعض الجوانب مع طبوغرافية مكانٍ ما، ولكن قد لا يكون للعُقَد والروابط علاقة بالنقاط في حيز المكان.
تُعَد «الشبكات الاجتماعية» مثالًا لمثل هذا التمثيل البياني. في الشبكات الاجتماعية، تمثِّل العُقَد الممثلين الاجتماعيين (وهؤلاء قد يكونون أفرادًا أو مؤسسات)، بينما تمثِّل الروابطُ التفاعلات بينهم. قد يكون الممثلون الاجتماعيون ممثلين حقيقيين، وقد تكون الروابط هي عمليات التعاون بينهم في الأفلام. قد نكون نحن الممثلين الاجتماعيين، والروابط قد تكون هي علاقاتنا مع الآخرين في أحد تطبيقات الشبكات الاجتماعية. عندئذٍ، يمكننا استخدام الشبكات الاجتماعية للعثور على جماعاتٍ من الناس، انطلاقًا من فرضية أن الجماعات تتكوَّن بفضل أشخاصٍ يتفاعلون بعضهم مع بعض. وتوجد خوارزميات تمتاز بالفاعلية في إيجاد جماعات في شكل رسوم بيانية بها ملايين العُقَد.
إن تعريف التمثيل البياني شامل لدرجة أنه قد يضم أيَّ شيء يمكن تمثيله في صورة عناصر مرتبطة بعناصر أخرى.
وتُعَد الشبكة العنكبوتية العالمية مثالًا لتمثيل بياني موجَّه (ضخم). يمكننا تمثيل الشبكة بحيث ترمز العُقَد إلى صفحات الويب، بينما ترمز الحواف إلى الروابط التشعُّبية بين كل صفحتين. وهذا التمثيل البياني موجَّه؛ لأن الصفحة يمكن أن ترتبط بصفحةٍ أخرى، ولكن ليس بالضرورة أن تعود تلك الصفحة الثانية للارتباط بالأولى.
يُطلق على التمثيل البياني الذي ليس له دورة «تمثيل بياني غير دوري». تشكِّل التمثيلات البيانية غير الدورية الموجَّهة فئةً مهمة في التمثيلات البيانية. وللتمثيلات البيانية غير الدورية الموجَّهة استخدامات عديدة؛ على سبيل المثال، نستخدمها للتعبير عن الأولويات بين المهام (نعبِّر عن المهام بالعُقَد، والأولويات هي الروابط بينها)، وعلاقات الاعتماد على الغير والمتطلبات الأساسية وغيرها من الترتيبات المشابهة. سننحي التمثيلات البيانية غير الدورية جانبًا الآن ونوجِّه انتباهنا إلى التمثيلات البيانية الدورية التي ستفتح لنا أول نافذة على الخوارزميات في التمثيلات البيانية.
المسارات والحمض النووي
كان من أهم التطورات العلمية التي حدثت في العقود الأخيرة فكُّ شفرة الجينوم البشري. فبفضل التقنيات التي طُوِّرت في هذا الصدد، يمكننا الآن فحصُ الأمراض الجينية واكتشافُ الطفرات الجينية ودراسة جينومات الأنواع المنقرضة وغيرها من التطبيقات المذهلة.
لمعرفة تكوين حمض نووي غير معروف، يمكننا اتباعُ الإجراءات التالية. ننشئ نسخًا عديدة من السلسلة ونقسِّمها إلى أجزاءٍ صغيرة؛ كأن نقسمها إلى أجزاء يحتوي كلٌّ منها على ثلاث قواعد. وباستخدام أدوات متخصصة، يمكننا تحديد مثل هذه الأجزاء الصغيرة بسهولة. وبهذه الطريقة، نتوصَّل إلى مجموعة من الأجزاء المعروفة. بعد ذلك يتبقى أمامنا مشكلة تجميع الأجزاء في سلسلة حمض نووي، سنعرف تكوينها حينئذٍ.
-
(١)
نحدِّد عقدة بداية.
-
(٢)
ننتقل من عقدةٍ إلى أخرى حتى نعود إلى عقدة البدء. ليس بالضرورة أن تغطي الدورة التي تتبَّعناها جميع الحواف.
-
(٣)
ما دام هناك رأس ينتمي إلى الدورة التي اتبعناها ولكنه في الوقت نفسه جزء من حافة ليست على المسار، نبدأ مسارًا جديدًا من ذلك الرأس باستخدام الحواف التي لم نستخدمها بعدُ حتى نعود إليها بحيث نكوِّن دورة أخرى. ثم نوصل تلك الدورة بالدورة التي اتبعناها بالفعل.
إذا استخدمنا الخوارزمية في التمثيل البياني المذكور في المثال، فسنحصل على مسارٍ بالشكل التالي:
جدولة المسابقات الرياضية
لنفترض أنك تنظِّم بطولة رياضية سوف يتبارى فيها المتسابقون أزواجًا، ومِن ثَم سيكون لدينا سلسلة من المباريات. لدينا ثمانية متسابقين، وسيلعب كل متسابق أربع مباريات. تدور المسألة التي نحن بصددها حول طريقة جدولة المسابقة. فنحن نريد جدولة المباريات بحيث يلعب كل متسابق مباراة واحدة فقط في اليوم.
يمكننا أن نجد حلًّا أفضلَ إذا أنشأنا مخططًا بيانيًّا لتمثيل المسألة. سنحدِّد رأسًا لكل لاعب وحافة لكل مباراة. عندئذٍ سيتخذ التمثيل البياني الشكل الموضَّح جهة اليمين أدناه. وعلى اليسار، ميزنا الحواف باسم اليوم الذي ستُقام فيه المباراة. كيف وجدنا ذلك الحل؟
نتَّفق على وضعِ أرقام أيام المباريات بترتيب متسلسل. لنقل إن البطولة ستبدأ في اليوم صفر. سنجدول كل المباريات، واحدة بواحدة.
-
(١)
نأخذ مباراةً لم تُدرَج في الجدول بعد. علينا التوقُّف إذا كنَّا قد أدرجنا كل المباريات.
-
(٢)
نحدِّد موعد المباراة في أقربِ يوم بحيث لا يشارك أيٌّ من اللاعبين في مباراة أخرى في ذلك اليوم. ثم نرجع إلى الخطوة الأولى.
تبدو هذه الخوارزمية بسيطةً إلى درجة خادعة، وقد يساورك الشك في قدرتها على حل المسألة حقًّا. لذا، دعنا نواصل ونرى ما يحدث. في الجدول التالي، يمكننا أن نرى المباريات، واحدة بواحدة، واليوم المحدَّد لإقامة كل مباراة، كما طبَّقنا الخوارزمية على التمثيل البياني. ينبغي قراءة أول عمودين في الجدول ثم العمودين التاليين:
| المباراة | اليوم | المباراة | اليوم |
|---|---|---|---|
| A, B | 0 | C, F | 3 |
| A, D | 1 | C, G | 2 |
| A, E | 2 | D, G | 3 |
| A, H | 3 | D, H | 2 |
| B, C | 1 | E, F | 0 |
| B, E | 3 | E, H | 1 |
| B, F | 2 | F, G | 1 |
| C, D | 0 | G, H | 0 |
نبدأ بمباراة أليس ضد بوب. لن يلعب أليس أو بوب أيَّ مباراة أخرى في اليوم صفر؛ أي في اليوم الذي سنحدِّده لإقامة المباراة.
بعد ذلك نأخذ مباراةً أخرى لم تُدرج في الجدول بعد، ولنقل مباراة أليس ضد ديف. سنرتِّب أسماء اللاعبين ترتيبًا أبجديًّا، على الرغم من عدم ضرورة ذلك في مسيرتنا، ولكن تذكَّر أنه كان يمكننا إدراجهم بترتيبٍ آخر — حتى ولو كان عشوائيًّا — ما دمنا نتعامل مع كل مباراة مرة واحدة فقط. لدى أليس مباراة أُدرجت في اليوم صفر بالفعل؛ لذا فإن أول يوم متاح للمباراة هو اليوم واحد.
يأتي بعد ذلك المباراة بين أليس وديف. أُدرجت أليس في اليوم صفر واليوم واحد، ومِن ثَم سندرج المباراة في اليوم اثنين. آخر مباراة لأليس ستكون مع هيدي؛ فأليس مشغولة في الأيام صفر وواحد واثنين ومن ثم سندرج هذه المباراة في اليوم ثلاثة.
انتهينا من أليس. ننتقل إلى مباريات بوب؛ باستثناء اليوم الذي أدرجناه كي يلعب فيه ضد أليس، سنحتاج إلى وضع خطة لمباراة بوب ضد كارول. أُدرِج بوب بالفعل في اليوم صفر (مع أليس)؛ ومِن ثَم سيكون لزامًا أن تُقام هذه المباراة في اليوم واحد. عندما ندرج بوب مع إيف، نلاحظ أن بوب مشغول بالفعل في اليوم صفر واليوم واحد (أدرجنا هاتين المباراتين لتونا)، بينما أُدرِج إيف للعب ضد أليس في اليوم اثنين؛ ولذا أدرجنا مباراة بوب ضد إيف في اليوم ثلاثة. بالانتقال إلى مباراة بوب ضد فرانك، نجد أن بوب لديه مباريات في اليوم صفر واليوم واحد، ولكنَّه متفرغ في اليوم اثنين بينما فرانك ليس لديه مباريات على الإطلاق حتى ذلك اليوم. إذن، نقيم مباراة بوب ضد فرانك في اليوم «اثنين»، قبل مباراة بوب ضد إيف.
بعد بوب، سنلتفت إلى مباريات كارول. لم تُدرَج كارول ولا ديف في مباريات اليوم صفر، ومِن ثَم ستُقام مباراة كارول ضد ديف في اليوم الأول من البطولة. بعد ذلك، يمكن إقامة مباراة كارول ضد فرانك في اليوم ثلاثة؛ لأن كارول لديها مباراتان في اليوم صفر (وهي تلك التي رتَّبنا لها لتونا) واليوم واحد (مع بوب كما رتَّبنا من قبل)، بينما يلعب فرانك ضد بوب في اليوم اثنين (كما رتَّبنا من قبل أيضًا). ستُقام مباراة كارول ضد جريس «قبل ذلك» في اليوم اثنين؛ لأن جريس ليس لديها مباريات أخرى مزمعة بعدُ، وكارول لا تزال متفرغة في اليوم اثنين.
نواصل على هذا المنوال مع باقي المباريات؛ المثير في الأمر أن المباريات في المربَّعات الداخلية والخارجية من التمثيل البياني ستُقام في أول يومين. تلك المباريات عبارة عن مجموعتين مختلفتين ستُلعبان بالتوازي قبل أن يبدأ اللعب بينهما. في النهاية، كان في الحل الذي وجدناه تحسنٌ كبير على الحل الساذج الذي يتطلب ١٦ يومًا؛ إذ لن نحتاج إلى أكثر من أربعة أيام!
تُعَد مسألة جدولة المسابقات تلك، في الحقيقة، مثالًا لمسألةٍ أعم، ألا وهي مسألة «تلوين الحواف». وتلوين الحواف في التمثيل البياني هو تعيين ألوان للحواف بحيث لا يكون لحافتين متلاصقتين لونٌ واحد. وفي هذا المثال، سنتعامل مع الألوان على سبيل المجاز. في المثال المذكور، تُعبِّر الألوان عن الأيام؛ وبوجه عام، يمكن أن تَكُون أي مجموعة أخرى من القيم المختلفة. وإذا أردنا تلوين الرءوس في المخطَّط البياني بدلًا من الحواف، بحيث لا يتشارك رأسان تربطهما حافة واحدة لونًا واحدًا، يصبح بين يدينا مسألة «تلوين الرءوس». ولا عجب في أن كلًّا من تلوين الحواف وتلوين الرءوس ينتمي إلى فئةٍ أكبر وهي مسائل «تلوين التمثيل البياني».
يمكننا أن ندرك ببعض التفكير أن ما يبدو أنه الأفضل في الوقت الحالي في الخوارزميات — وكذلك في الحياة الواقعية — قد لا يكون الاستراتيجية المثلى. قد يكون من المفيد أن نؤجِّل الشعور بالرضا؛ فالخيار الأفضل الآن ربما يقودنا إلى فخٍّ نندم عليه لاحقًا. تخيَّل أنك تتسلَّق جبلًا. قد يدفعك الاستدلال الجشع إلى اختيار أشد المسارات انحدارًا عند كل نقطة (على افتراض أنك تتمتَّع ببراعةٍ لا تُضاهى في التسلُّق). ليس بالضرورة أن يأخذك هذا المسار إلى القمة، فقد يقودك إلى مرتفعٍ ليس عنده طريق سوى طريق العودة. قد يكون الطريق الحقيقي للوصول إلى القمة بين المنحدرات الأخف انحدارًا.
تُستخدم استعارة التسلُّق كثيرًا في حل المسائل في علوم الكمبيوتر. فنقوم بتمثيل المسألة التي بين يدينا بحيث يكمُن الحل عند «قمة» الخطوات التي يمكن أن نقوم بها ونحاول العثور على الخطوات الصحيحة؛ فيما يُسمى ﺑ «أسلوب تسلُّق التل». عندما نصل إلى شيءٍ أشبه بمرتفع، نقول إننا وصلنا إلى «الحل الأمثل الموضعي» ولكن ليس إلى «الحل الأمثل الشامل» وهو أعلى قمَّة نسعى للوصول إليها.
إذا كنت تريد أن تعرف كيف يمكن أن يحدث هذا، ففكر في تمثيلٍ بيانيٍّ يتكوَّن من «نجوم» متصلة بعقدة مركزية، كما في التمثيل البياني التالي:
أقصر المسارات
في الفصل الأول، تناولنا عدم جدوى محاولة إيجاد أقصر المسارات بين نقطتين على شبكة عن طريق عدِّ كل المسارات المحتملة. ورأينا أن القيام بذلك مستحيل عمليًّا؛ لأن عدد المسارات يتزايد على نحوٍ هائل. أما وقد تعرَّفنا على التمثيلات البيانية الآن، فسنرى أن هناك طريقة للقيام بذلك. في الحقيقة، سنرتقي بالمسألة إلى مستوًى أعلى بعض الشيء. فبدلًا من البحث عن أقصر المسارات على شبكةٍ ما، لها شكل هندسي جميل وتتساوى فيها المسافات بين النقاط، سنسمح بأي شكل هندسي بل سنضيف مسافات مختلفة بين النقاط.
للقيام بذلك، سننشئ مخططًا بيانيًّا يحتوي على حوافَّ وعُقَد تمثِّل خريطة، ونريد إيجاد أقصر مسار بين عقدتين على الخريطة. إضافة إلى ذلك، سنلحق «وزنًا» بكل حافة. قد يكون الوزن موجبًا أو صفرًا، وسنربطه بقياس للمسافة بين عقدتين متصلتين. قد يكون هذا القياس مسافةً بالأميال أو زمنَ سيرٍ بالساعات؛ أيُّ وحدة قياس غير سالبة ستفي بالغرض. «طول المسار» يساوي مجموع الأوزان على طول المسار؛ ومِن ثَم يكون «أقصر مسار» بين عقدتين هو المسار الأقل طولًا. إذا كانت جميع الأوزان تساوي واحدًا، فإن طول المسار يساوي عدد الحواف على ذلك المسار. بمجرد أن نعطي الأوزان قيمًا أخرى، لن تصبح تلك القيمة صحيحة بعد الآن.
إذن، ما هي خطوات الخوارزمية؟ نريد إيجاد أقصر المسارات من عقدة إلى كل العُقَد الأخرى في مخطَّط بياني. تَستخدم الخوارزمية فكرةً يُطلق عليها «التخفيف»، وفيها نعيِّن تقديراتٍ للقيم التي نريد إيجادها (المسافات في هذه المسألة). في البداية، تكون التقديرات هي الاحتمال الأسوأ. ثم مع التقدُّم في خطوات الخوارزمية، نتمكَّن من تخفيف تلك التقديرات وتحويلها من التقديرات الشديدة السوء التي بدأنا بها إلى تقديراتٍ أفضلَ وأفضلَ تدريجيًّا حتى نصل إلى القيم الصحيحة.
- (١)
تعيين مسافةٍ لما لانهاية لجميع العُقَد باستثناء عقدة البداية؛ وتعيين مسافة تساوي صفرًا لعقدة البداية.
- (٢)
إيجاد العقدة التي لم يتم المرور بها ذات المسافة الأقل. ستكون هذه هي العقدة الحالية. إذا لم يتبقَّ عُقَد لم يتم المرور بها، توقف.
- (٣)
التحقُّق من جميع العُقَد المجاورة للعقدة الحالية. إذا كانت المسافات إلى تلك العُقَد أكبرَ من المسافة التي سنحصل عليها بدايةً من العقدة الحالية وقبل الوصول إلى العُقَد المجاورة لها، نخفِّف المسافة ونحدِّث المسار إلى العقدة المجاورة. ننتقل إلى الخطوة ٢.
إذا كان اهتمامنا منصبًّا فقط على إيجاد أقصر مسار إلى عقدةٍ محدَّدة، يمكننا التوقُّف عندما نختار المرور بها في الخطوة ٢. وبمجرد الانتهاء من ذلك، نكون قد وجدنا أقصر مسار إلى تلك العقدة، ولن يتغير فيما تبقى من خطوات تنفيذ الخوارزمية.
يمكن استخدام خوارزمية ديكسترا في أي تمثيل بياني حتى إذا كان يتضمَّن دورات، بشرط ألَّا يحتوي على أوزان سالبة. قد تحدث الأوزان السالبة إذا كانت الحواف تمثل نوعًا من المكافآت والعقوبات بين العُقَد. الخبر السار أنه توجد خوارزميات أخرى فعالة يمكننا استخدامها في حالة وجود أوزان سالبة، ولكن هذا يبيِّن أنه قد يكون لتلك الخوارزميات متطلبات خاصة في تطبيقها. وعندما نحاول إيجاد خوارزمية لحل مسألةٍ ما، ينبغي أن نتأكد من أن المسألة تستوفي متطلبات تلك الخوارزمية. وإلَّا فلن تؤتي الخوارزمية أيَّ فائدة؛ ولكن اعلم أن الخوارزمية لا تخبرنا بأنها عديمة الجدوى. إذا نفَّذنا الخوارزمية على جهاز كمبيوتر، فسيظل الجهاز ينفِّذ خطواتها حتى لو لم يكن لذلك أي فائدة. ومِن ثَم ستؤدي إلى إجابةٍ بلا أي معنًى. فالأمر يعود إلينا نحن في التأكُّد من أننا نستخدم الأداة المناسبة للمهمة المناسبة.
عندما نحاول إيجاد خوارزمية لحل مسألةٍ ما، ينبغي أن نتأكد من أن المسألة تستوفي متطلبات تلك الخوارزمية. وإلا فلن تُؤتي الخوارزمية أيَّ فائدة؛ ولكن اعلم أن الخوارزمية لا تخبرنا بأنها عديمة الجدوى.
لنضرب مثالًا مبالغًا فيه، فكِّر ماذا سيحدث إذا لم يكن المخطَّط البياني يحتوي على أوزان سالبة فحسب، بل يحتوي على دورة، حيث مجموع الحواف يكون عددًا سالبًا؛ أي دورة سالبة. عندئذٍ «ما من خوارزمية» ستجد أقصر المسارات في المخطط البياني «نظرًا لعدم وجود مسارات». إذا كانت لدينا دورة سالبة، يمكننا الدوران مرارًا وتكرارًا حول حواف المخطط، وفي كل مرة سيتقلص طول المسار. يمكننا الاستمرار على هذا المنوال إلى الأبد، وسينتهي المسار عبر الدورة إلى عددٍ لا نهائي سالب. يطلِق علماء الكمبيوتر والمبرمجون اسمًا على ما يحدث عندما نضع شيئًا في برنامجٍ لا يعطي معنًى له، وهو: «المدخلات الخاطئة تعطي مخرجات خاطئة». والأمر يعتمد على الإنسان في الكشف عن المدخلات الخاطئة ومعرفةِ ما ينبغي استخدامه ومتى. يوجد جزء مهم في الدورات التدريبية في الجامعات عن الخوارزميات مخصَّص تحديدًا لتعليم علماء الكمبيوتر الناشئين ما ينبغي لهم استخدامه ومتى.
