الفصل الثاني

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

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

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

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

نمت المسألة إلى علم عالِم الرياضيات السويسري الشهير ليونهارت أويلر، لا نعرف تحديدًا كيف؛ إذ ورد ذكر المسألة في خطابٍ أُرسل يوم ٩ مارس ١٧٣٦ من عمدة مدينة دانزيج التي تقع في بروسيا على مسافة ٨٠ ميلًا شرقي كونيجسبرج (تغيَّر اسم دانزيج إلى جدانسك وتتبع بولندا). يبدو أن مراسلة أويلر كانت جزءًا من جهود عمدة المدينة لتشجيع ازدهار الرياضيات في بروسيا.

كان أويلر آنذاك يعيش في مدينة سانت بطرسبرج في روسيا. فعمل على هذه المسألة وقدم حلًّا إلى أعضاء أكاديمية سانت بطرسبرج للعلوم يوم ٢٦ أغسطس ١٧٣٥. في العام التالي، كتب أويلر ورقة بحثية باللاتينية يذكر فيها الحل.2 كان الحل «سلبيًّا»؛ إذ لم يكن ممكنًا القيام بجولة في المدينة بعبور كل جسر مرة واحدة فقط. قد تكون تلك الحقبة من تاريخ الرياضيات مثيرةً للاهتمام، ولكن بحل المسألة، أنشأ أويلر فرعًا جديدًا تمامًا في الرياضيات ألا وهو دراسة «التمثيلات البيانية».3
قبل أن نتناول التمثيلات البيانية، لنرى كيف تناول أويلر تلك المسألة. بادئ ذي بدء، جرَّد أويلر المسألة إلى عناصرها الأساسية. لا يلزم وجود خريطة مفصلة لمدينة كونيجسبرج لتمثيل المسألة. فقد رسم أويلر المخطط التالي لها:4
استخدم أويلر الحرفين A وD للإشارة إلى الجزيرتين، والحرفين B وC للإشارة إلى ضفتي البر الرئيسي. تمثَّلت الخطوة التالية في تجريد المخطط أكثر — بعيدًا عن الهندسة الفيزيائية — وتوضيح الروابط بين الجسور والجزيرتين والبر الرئيسي؛ لأن هذا ما يهم حقًّا فيما يتعلَّق بالمسألة:

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

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

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

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

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

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

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

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

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

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

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

عندما يمكن البدء من عقدةٍ ما في التمثيل البياني، وعبور الحواف والعودة إلى العقدة التي بدأنا منها، نقول إن ذلك التمثيل البياني له «دورة». لكن ليست كل التمثيلات البيانية لها دورات. يحتوي التمثيل البياني في مسألة كونيجسبرج على دورات، على الرغم من أنه لا يحتوي على دورة أويلرية. ويعتبر التمثيل البياني الدوري الأشهر (وهو في الواقع تمثيل بياني متعدد) في تاريخ العلم نموذج أوجست كيكولي لبنية جزيئات البنزين:5
figure

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

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

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

يتم ترميز الجينوم في الحمض النووي، وهو عبارة عن جزيء عضوي كبير يتكوَّن من لولب مزدوج. يتكوَّن اللولب المزدوج من أربع قواعد هي: السيتوسين (C) والجوانين (G) والأدينين (A) والثايمين (T). يتكوَّن كل جزء في اللولب المزدوج من سلسلة من القواعد، مثل ACCGTATAG. أما الجزء الآخر من اللولب المزدوج فيتكوَّن من قواعد ترتبط بنظيراتها في الجزء الأول وفقًا للقاعدتين A-T وC-G. فإذا كان أحد جزأَي اللولب ACCGTATAG، فسيكون الجزء الثاني TGGCATATC.

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

لنفترض أن لدينا الأجزاء التالية، أو البوليمرات كما يسمونها: GTG وTGG وATG وGGC وGCG وCGT وGCA وTGC وCAA وAAT. يتكوَّن كل بوليمر من ثلاث قواعد؛ ولإيجاد سلسلة الحمض النووي التي تؤلِّفها تلك البوليمرات، ننشئ مخططًا بيانيًّا. في هذا المخطط، تعبِّر الرءوس عن بوليمرات مكوَّنة من قاعدتين ومشتقة من بوليمرات مكوَّنة من ثلاث قواعد، ويأخذ من البوليمرات المكوَّنة من ثلاث قواعد أول بوليمرين وآخر بوليمرين. إذن، من البوليمر GTG، سنأخذ GT وTG، ومن البوليمر TGG، سنأخذ TG وGG. في المخطط البياني، نضيف حافة لكل واحد من البوليمرات الأولية أو المكوَّنة من ثلاث قواعد الذي استُخدم لاشتقاق الرأسين. نسمي تلك الحافة البوليمر. ومن البوليمر ATG نحصل على الرأسين AT وTG والحافة ATG. يمكنك الاطلاع على المخطط البياني الناتج عن هذا المثال:
باستخدام المخطط البياني الذي أنشأناه، لن نحتاج إلا إلى إيجاد دورة في المخطط البياني تمر على كل الحواف مرة واحدة فقط — أي دورة أويلرية — من أجل إيجاد سلسلة الحمض النووي الأولية. وقد نُشرت الورقة البحثية «خوارزمية هيرهولزر» لإيجاد الدورات الأويلرية على المخططات البيانية على يد عالِم الرياضيات الألماني كارل هيرهولزر عام ١٨٧٣ وتسير كالتالي:6
  • (١)

    نحدِّد عقدة بداية.

  • (٢)

    ننتقل من عقدةٍ إلى أخرى حتى نعود إلى عقدة البدء. ليس بالضرورة أن تغطي الدورة التي تتبَّعناها جميع الحواف.

  • (٣)

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

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

لقد بدأنا من AT وقمنا بالدورة AT → TG → GG → GC → CA → AA → AT. لقد صنعنا دورةً ولكننا لم نغطِّ كلَّ الحواف. نرى أن TG لها حافة — TGC — لم نمرَّ بها بعدُ. لذا ننتقل إلى TG ونقوم بدورة تبدأ عبر الحافة TGC بحيث نحصل على المسار TG → GC → CG → GT → TG. نضم المسار الثاني إلى المسار الأول، لنحصل بذلك على المسار الوارد في الشكل البياني: AT → TG (→ GC → CG → GT → TG) → GG → GC → CA → AA → AT. إذا مشينا في المسار الناتج من العقدة الأولى إلى العقدة الأخيرة، دون لمس العقدة الأخيرة، وجمعنا الرءوس في سلسلةٍ واحدة بحيث نمر على القاعدة المشتركة مرة واحدة، فسنحصل على سلسلة الحمض النووي ATGCGTGGCA. يمكنك التحقُّق من أن تلك السلسلة تحتوي على جميع البوليمرات التي بدأنا بها؛ علمًا بأنك ستجد البوليمرات CAA وCAT إذا استدرت عندما تصل إلى نهاية السلسلة وعُدت إلى نقطة البداية.
في هذا الشرح التوضيحي الخاص، أوجدنا مسارًا واحدًا إضافيًّا فقط وألحقناه بالمسار الأصلي. وبوجه عام، قد يكون هناك المزيد من المسارات؛ لأن الخطوة الثالثة من الخوارزمية تتكرَّر ما دام هناك رءوس ذات حواف لم نمرَّ بها بعد. تمتاز خوارزمية هيرهولزر بالسرعة؛ فإذا طُبقت تطبيقًا صحيحًا، فإنها تعمل في وقت خطِّي ، حيث ترمز إلى عدد الحواف في المخطط البياني.7

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

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

الحل البديهي هو أن نقيم مباراةً واحدة في اليوم ونترك المسابقة تستمر المدة التي تحتاج إليها. وبما أن لدينا ثمانية متسابقين وكل متسابق سيلعب أربع مباريات، فستستمر المسابقة ١٦ يومًا (٨ × ٤ / ٢؛ والقسمة على اثنين هنا بغرض عدم عدِّ كل مباراة مرتين). سنسمي المتسابقين الثمانية أليس (A) وبوب (B) وكارول (C) وديف (D) وإيف (E) وفرانك (F) وجريس (G) وهيدي (H). وهذا يتيح لنا استخدام الحرف الأول فقط من أسمائهم لتعريفهم.

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

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

  • (١)

    نأخذ مباراةً لم تُدرَج في الجدول بعد. علينا التوقُّف إذا كنَّا قد أدرجنا كل المباريات.

  • (٢)

    نحدِّد موعد المباراة في أقربِ يوم بحيث لا يشارك أيٌّ من اللاعبين في مباراة أخرى في ذلك اليوم. ثم نرجع إلى الخطوة الأولى.

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

المباراة اليوم المباراة اليوم
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

في المخطَّط البياني التالي، لدينا ست عُقَد متصلة بتسع حواف ذات أوزان متفاوتة، ونريد إيجاد أقصر المسارات للانتقال من العقدة A إلى العقدة F.
figure
إذا اتبعنا الاستدلال الجشع، فسنبدأ من العقدة A إلى العقدة C؛ وهكذا يصبح أفضل خيار هو الانتقال إلى العقدة E، ومنها نسلك طريقنا إلى العقدة F. إجمالي طول المسار A وC وE وF يساوي ثمانية، ولكنه ليس المسار الأفضل. أفضل مسار هو الانتقال من العقدة A إلى العقدة C ثم إلى العقدة D، وبعدها إلى العقدة F بإجمالي طولٍ يساوي ستة. إذن فالاستدلال الجشع لا يصلح، وعلى العكس من تخطيط المسابقات، لا توجد ضمانات بشأن أسوأ أداء له فيما يتعلَّق بأقصر مسارٍ فعلي. على الرغم من ذلك، وخلافًا لتخطيط المسابقات مرة أخرى، توجد خوارزميات فعَّالة في إيجاد أقصر المسارات؛ ومِن ثَم فلا داعي لاستخدام الاستدلال الجشع في الواقع على الإطلاق.
في عام ١٩٥٦، كان هناك عالِم كمبيوتر هولندي شاب، يُدعى إيدسكر ديكسترا يتسوَّق في أمستردام مع خطيبته. لما تعبا، جلسا في مقهًى لاحتساء كوبين من القهوة، حيث أخذ ديكسترا يفكِّر في مسألة إيجاد أفضل الطرق للانتقال من مدينة إلى أخرى. وصمَّم الحل في غضون ٢٠ دقيقة على الرغم من أن الخوارزمية استغرقت بعض الوقت — ثلاث سنوات — حتى نشرها. حظيَ ديكسترا بمسيرةٍ مهنية لامعة، لكن ما أثار دهشته أن هذا الاختراع الذي استغرق ٢٠ دقيقة ظل حجرَ الأساس لشهرته.10

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

في خوارزمية ديكسترا، يسير التخفيف على النحو التالي. نبدأ بتعيين أسوأ القيم المحتملة للمسافات من عقدة البداية إلى جميع العُقَد، فنعيِّن المسافة إلى ما لانهاية؛ ولا يخفى أنه لا يوجد ما هو أسوأ من ذلك! في الشكل التالي، وضعنا التقدير الأولي لأقصر مسار والعقدة السابقة في ذلك المسار، سواء فوق كل عقدة أو تحتها. بالنسبة إلى العقدة A، لدينا القيمة لأن المسافة من A إلى A تساوي صفرًا ولا توجد عقدة سابقة على A. أما بالنسبة إلى جميع العُقَد الأخرى، لدينا القيمة ؛ لأن المسافة لا نهائية وليس لدينا فكرة عن أقصر مسار إليها.
نأخذ العقدة الأقصر مسافة من A حتى الآن. إنها العقدة A نفسها. إنها العقدة الحالية، ومِن ثَم نظلِّلها باللون الرمادي.
من العقدة A، يمكننا التحقُّق من التقديرات لأقصر المسارات إلى العُقَد المجاورة لها وهي العقدة B والعقدة C. في البداية، عينَّا هذه التقديرات إلى ما لانهاية، ولكننا نجد الآن أنه يمكننا في الواقع الانتقال من B إلى A بقيمة تساوي ٣، ومن العقدة C إلى العقدة A بقيمة تساوي ١. نحدِّث هذه التقديرات ونشير أيضًا إلى أن التقديرات تمرُّ من على العقدة A؛ ومِن ثَم نكتب 3/A فوق العقدة B و1/A أسفل العقدة C. وبذلك نكون قد انتهينا من العقدة A لما تبقى من الخوارزمية. نحدِّث الشكل بناءً على ذلك ونظلل العقدة A باللون الأسود. ننتقل إلى عقدةٍ لم نمرَّ عليها وتتضمَّن أفضل تقدير في الوقت الحالي. إنها العقدة C.
من العقدة C، نتحقَّق من تقديرات أقصر المسارات إلى العُقَد المجاورة لها وهي العقدة D والعقدة E. كانت التقديرات لا نهائية، ولكننا نرى الآن أنه يمكننا الوصول إلى كل واحدة منها من خلال العقدة C. المسار من A إلى D مرورًا بالعقدة C يساوي ٥ إجمالًا، ومِن ثَم نكتب 5/C فوق العقدة D. المسار من A إلى E مرورًا بالعقدة C يساوي ٣ إجمالًا، ومِن ثَم نكتب 3/C أسفل العقدة E. انتهينا من العقدة C ولذا نظللها باللون الأسود وننتقل إلى عقدةٍ لم نمرَّ عليها وتتضمَّن أفضل تقدير حتى الآن. تتضمَّن العقدتان B وE تقديرات جيدة على السواء بقيمة ٣. يمكننا اختيار أيٍّ منهما. لنختر العقدة B.
figure
نعمل بالطريقة نفسها. من العقدة B، نتحقَّق من تقديرات أقصر المسارات إلى العُقَد المجاورة لها وهي العقدة D والعقدة F. لدينا بالفعل تقدير بطول ٥ للعقدة D بداية من العقدة C؛ هذا أفضل من الطول ٦ الذي كنا سنحصل عليه لو بدأنا من عند العقدة B. ومِن ثَم نبقي تقدير المسافة إلى العقدة D من دون تغيير. التقدير الحالي للعقدة F لا نهائي ومِن ثَم سنحدِّثه إلى ٩ مبتدئين من العقدة B. نظلل العقدة B للدلالة على المرور بها وننتقل إلى العقدة التي لم يتم المرور بها وتتضمَّن أفضل تقدير حتى الآن. إنها العقدة E.
العقدة E تجاورها العقدة F. طول المسار إلى العقدة F من العقدة E يساوي ٨، ما يجعله أفضل من المسار الذي أوجدناه من العقدة B. نحدِّث المسار ونظلِّل العقدة E دلالة على المرور بها وننتقل إلى العقدة التي لم يتم المرور بها ولها أفضل تقدير حتى الآن، وهي العقدة D.
العقدة D تجاورها العقدة F، حيث طول المسار من النقطة E يساوي ٨. بما أنه يمكننا الوصول إلى F مرورًا بالعقدة D بطول يساوي ٦ إجمالًا، نحدِّث ذلك المسار. وكما في السابق، نمر علها وتتضمن أفضل تقدير حتى الآن، العقدة التي لم يتم المرور عليها حتى الآن هي العقدة F.
من العقدة F، نتحقَّق مما إن كان ينبغي أن نُحدِّث تقديرنا للعقدة E المجاورة لها أم لا. المسار الحالي إلى العقدة E يساوي ٣، بينما المسار عبر العقدة F ستبلغ قيمته ١٠. نبقي العقدة E من دون تغيير. المرور على العقدة F لم يحدِث أيَّ فرق، ولكننا لم نستطِع معرفة هذا من قبل. بما أننا قد مررنا على جميع العُقَد، تنتهي الخوارزمية.
بينما كنَّا نسير بين خطوات الخوارزمية، كنا نسجِّل أطوال المسارات والعُقَد السابقة على كل عقدة عبر أقصر مسار. وقد فعلنا ذلك بحيث إذا أردنا — بعد الانتهاء من الخوارزمية — إيجاد أقصر مسار من العقدة A إلى أي عقدة أخرى في التمثيل البياني، ولنقل العقدة F، نبدأ من النهاية ونسلك طريقنا إلى عقدة البداية. نطلع على العقدة السابقة لها، وهي العقدة D. ونتوصَّل إلى العقدة السابقة على D ألا وهي العقدة C، والعقدة السابقة على C وهي العقدة A. المسار الأقصر من A إلى F هو A وC وD وF بإجمالي طول يساوي ستة، كما ذكرنا من قبل في بداية نقاشنا.
في النهاية، توصَّلت خوارزمية ديكسترا إلى «كل المسارات الأقصر» من عقدة البداية إلى كل العُقَد الأخرى في التمثيل البياني. الخوارزمية فعَّالة؛ إذ تساوي درجة تعقيدها ، حيث تعبِّر عن عدد الحواف في التمثيل البياني، و تعبِّر عن عدد العُقَد. وفيما يلي الخوارزمية في شكل خطوات:
  • (١)

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

  • (٢)

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

  • (٣)

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

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

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

عندما نحاول إيجاد خوارزمية لحل مسألةٍ ما، ينبغي أن نتأكد من أن المسألة تستوفي متطلبات تلك الخوارزمية. وإلا فلن تُؤتي الخوارزمية أيَّ فائدة؛ ولكن اعلم أن الخوارزمية لا تخبرنا بأنها عديمة الجدوى.

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

جميع الحقوق محفوظة لمؤسسة هنداوي © ٢٠٢٢