التمثيلات البيانية

الانتقال من التمثيلات البيانية إلى الخوارزميات

إن تعريف التمثيل البياني شامل لدرجة أنه قد يضم أيَّ شيء يمكن تمثيله في صورة عناصر مرتبطة بعناصر أخرى. قد يتشابه التمثيل البياني في بعض الجوانب مع طبوغرافية مكانٍ ما، ولكن قد لا يكون للعُقَد والروابط علاقة بالنقاط في حيز المكان.

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

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

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

المسارات والحمض النووي

كان من أهم التطورات العلمية التي حدثت في العقود الأخيرة فكُّ شفرة الجينوم البشري. فبفضل التقنيات التي طُوِّرت في هذا الصدد، يمكننا الآن فحصُ الأمراض الجينية واكتشافُ الطفرات الجينية ودراسة جينومات الأنواع المنقرضة وغيرها من التطبيقات المذهلة.

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

إذا استخدمنا الخوارزمية في التمثيل البياني المذكور في المثال، فسنحصل على مسارٍ بالشكل التالي:

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

جدولة المسابقات الرياضية

لنفترض أنك تنظِّم بطولة رياضية سوف يتبارى فيها المتسابقون أزواجًا، ومِن ثَم سيكون لدينا سلسلة من المباريات. لدينا ثمانية متسابقين، وسيلعب كل متسابق أربع مباريات. تدور المسألة التي نحن بصددها حول طريقة جدولة المسابقة. فنحن نريد جدولة المباريات بحيث يلعب كل متسابق مباراة واحدة فقط في اليوم.

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

نتَّفق على وضعِ أرقام أيام المباريات بترتيب متسلسل. لنقل إن البطولة ستبدأ في اليوم صفر. سنجدول كل المباريات، واحدة بواحدة.

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

نبدأ بمباراة أليس ضد بوب. لن يلعب أليس أو بوب أيَّ مباراة أخرى في اليوم صفر؛ أي في اليوم الذي سنحدِّده لإقامة المباراة.

بعد ذلك نأخذ مباراةً أخرى لم تُدرج في الجدول بعد، ولنقل مباراة أليس ضد ديف. سنرتِّب أسماء اللاعبين ترتيبًا أبجديًّا، على الرغم من عدم ضرورة ذلك في مسيرتنا، ولكن تذكَّر أنه كان يمكننا إدراجهم بترتيبٍ آخر — حتى ولو كان عشوائيًّا — ما دمنا نتعامل مع كل مباراة مرة واحدة فقط. لدى أليس مباراة أُدرجت في اليوم صفر بالفعل؛ لذا فإن أول يوم متاح للمباراة هو اليوم واحد.

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

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

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

نواصل على هذا المنوال مع باقي المباريات؛ المثير في الأمر أن المباريات في المربَّعات الداخلية والخارجية من التمثيل البياني ستُقام في أول يومين. تلك المباريات عبارة عن مجموعتين مختلفتين ستُلعبان بالتوازي قبل أن يبدأ اللعب بينهما. في النهاية، كان في الحل الذي وجدناه تحسنٌ كبير على الحل الساذج الذي يتطلب ١٦ يومًا؛ إذ لن نحتاج إلى أكثر من أربعة أيام!

تُعَد مسألة جدولة المسابقات تلك، في الحقيقة، مثالًا لمسألةٍ أعم، ألا وهي مسألة «تلوين الحواف». وتلوين الحواف في التمثيل البياني هو تعيين ألوان للحواف بحيث لا يكون لحافتين متلاصقتين لونٌ واحد. وفي هذا المثال، سنتعامل مع الألوان على سبيل المجاز. في المثال المذكور، تُعبِّر الألوان عن الأيام؛ وبوجه عام، يمكن أن تَكُون أي مجموعة أخرى من القيم المختلفة. وإذا أردنا تلوين الرءوس في المخطَّط البياني بدلًا من الحواف، بحيث لا يتشارك رأسان تربطهما حافة واحدة لونًا واحدًا، يصبح بين يدينا مسألة «تلوين الرءوس». ولا عجب في أن كلًّا من تلوين الحواف وتلوين الرءوس ينتمي إلى فئةٍ أكبر وهي مسائل «تلوين التمثيل البياني».

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

تُستخدم استعارة التسلُّق كثيرًا في حل المسائل في علوم الكمبيوتر. فنقوم بتمثيل المسألة التي بين يدينا بحيث يكمُن الحل عند «قمة» الخطوات التي يمكن أن نقوم بها ونحاول العثور على الخطوات الصحيحة؛ فيما يُسمى ﺑ «أسلوب تسلُّق التل». عندما نصل إلى شيءٍ أشبه بمرتفع، نقول إننا وصلنا إلى «الحل الأمثل الموضعي» ولكن ليس إلى «الحل الأمثل الشامل» وهو أعلى قمَّة نسعى للوصول إليها.

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

إذا كنت تريد أن تعرف كيف يمكن أن يحدث هذا، ففكر في تمثيلٍ بيانيٍّ يتكوَّن من «نجوم» متصلة بعقدة مركزية، كما في التمثيل البياني التالي:

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

المشكلة أن الخوارزمية الجشعة تقرِّر ترتيب الحواف للتلوين بطريقةٍ ليست مثالية في النهاية، أو تحريًّا للمصطلحات السليمة، بطريقةٍ ليست «مثالية في العموم». ربما تتوصَّل إلى الحل الأفضل، ولكن قد لا يكون هو الأفضل. لذا نكرِّر مرة أخرى، أن الاختلاف عن الحل الأمثل ليس كبيرًا للدرجة. ولعل في هذا مدعاة للارتياح؛ لأن تلوين التمثيل البياني بالغ الصعوبة لدرجة أننا لو أردنا خوارزمية دقيقة يمكنها إيجاد أفضل حل لكل تمثيل بياني، فستحتوي الخوارزمية على تعقيدٍ أُسيٍّ بقيمة تقريبًا، حيث تساوي عدد الحواف في التمثيل البياني. ولذا فلا فائدة تُرجى من خوارزميات تلوين الحواف، إلا في التمثيلات البيانية الصغيرة.

أقصر المسارات

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

للقيام بذلك، سننشئ مخططًا بيانيًّا يحتوي على حوافَّ وعُقَد تمثِّل خريطة، ونريد إيجاد أقصر مسار بين عقدتين على الخريطة. إضافة إلى ذلك، سنلحق «وزنًا» بكل حافة. قد يكون الوزن موجبًا أو صفرًا، وسنربطه بقياس للمسافة بين عقدتين متصلتين. قد يكون هذا القياس مسافةً بالأميال أو زمنَ سيرٍ بالساعات؛ أيُّ وحدة قياس غير سالبة ستفي بالغرض. «طول المسار» يساوي مجموع الأوزان على طول المسار؛ ومِن ثَم يكون «أقصر مسار» بين عقدتين هو المسار الأقل طولًا. إذا كانت جميع الأوزان تساوي واحدًا، فإن طول المسار يساوي عدد الحواف على ذلك المسار. بمجرد أن نعطي الأوزان قيمًا أخرى، لن تصبح تلك القيمة صحيحة بعد الآن.

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

في خوارزمية ديكسترا، يسير التخفيف على النحو التالي. نبدأ بتعيين أسوأ القيم المحتملة للمسافات من عقدة البداية إلى جميع العُقَد، فنعيِّن المسافة إلى ما لانهاية؛ ولا يخفى أنه لا يوجد ما هو أسوأ من ذلك! في الشكل التالي، وضعنا التقدير الأولي لأقصر مسار والعقدة السابقة في ذلك المسار، سواء فوق كل عقدة أو تحتها. بالنسبة إلى العقدة A، لدينا القيمة لأن المسافة من A إلى A تساوي صفرًا ولا توجد عقدة سابقة على A. أما بالنسبة إلى جميع العُقَد الأخرى، لدينا القيمة ؛ لأن المسافة لا نهائية وليس لدينا فكرة عن أقصر مسار إليها.

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

• (١)

  تعيين مسافةٍ لما لانهاية لجميع العُقَد باستثناء عقدة البداية؛ وتعيين مسافة تساوي صفرًا لعقدة البداية.

• (٢)

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

• (٣)

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

إذا كان اهتمامنا منصبًّا فقط على إيجاد أقصر مسار إلى عقدةٍ محدَّدة، يمكننا التوقُّف عندما نختار المرور بها في الخطوة ٢. وبمجرد الانتهاء من ذلك، نكون قد وجدنا أقصر مسار إلى تلك العقدة، ولن يتغير فيما تبقى من خطوات تنفيذ الخوارزمية.

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

لنضرب مثالًا مبالغًا فيه، فكِّر ماذا سيحدث إذا لم يكن المخطَّط البياني يحتوي على أوزان سالبة فحسب، بل يحتوي على دورة، حيث مجموع الحواف يكون عددًا سالبًا؛ أي دورة سالبة. عندئذٍ «ما من خوارزمية» ستجد أقصر المسارات في المخطط البياني «نظرًا لعدم وجود مسارات». إذا كانت لدينا دورة سالبة، يمكننا الدوران مرارًا وتكرارًا حول حواف المخطط، وفي كل مرة سيتقلص طول المسار. يمكننا الاستمرار على هذا المنوال إلى الأبد، وسينتهي المسار عبر الدورة إلى عددٍ لا نهائي سالب. يطلِق علماء الكمبيوتر والمبرمجون اسمًا على ما يحدث عندما نضع شيئًا في برنامجٍ لا يعطي معنًى له، وهو: «المدخلات الخاطئة تعطي مخرجات خاطئة». والأمر يعتمد على الإنسان في الكشف عن المدخلات الخاطئة ومعرفةِ ما ينبغي استخدامه ومتى. يوجد جزء مهم في الدورات التدريبية في الجامعات عن الخوارزميات مخصَّص تحديدًا لتعليم علماء الكمبيوتر الناشئين ما ينبغي لهم استخدامه ومتى.