في عالم مزدحم…كيف نحدد أقصر طريق ممكن؟

ما المقصود بالمسار؟

نتخذقراراتحولالطُرُقالتيسنسلكهاللتنقلبينالأماكنالمُختلفةيوميًّا。وقد تتنقل في منزلك بين غرفة نومك والمطبخ。

وفي الخارج، قد تتنقل من منزلك إلى المدرسة。لذا، لنفترض أن لديناشبكةمنالأماكنالتيترتبطببعضهاالبعضعبرالشوارعوالممرات。ويُعرف كل مكان من هذه الأماكن باسمالعقدة، وتُعرف الشوارع والممرات باسمالحواف．كماأن”جيران”العُقدةهمالعقدالتيتتصلبالحافة。لذا،فالمسارهوسلسلةمنالحوافالمُمتدةمنعقدةالبدايةإلىعقدةالوجهة[1，2］．

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

يُستخدمعلمالرياضياتلدراسةأطوالالمساراتبغرضاستنتاجالمساراتالأقصر。وغالبًامايكونمُفيدًافيالعثورعلىالمسارالأقصر。ويُعرفالمسارالأقصربأنهالمسارالموجودبينعُقدتينتمتلكانأقلعددٍمنالحوافِ،فيحالتساويتكلفةالتنقلعلىطولكلحافة(علىسبيلالمثال،إذاكانتكلحافةشارعًالهنفسالطول)。وبعبارةأعم،بالنظرإلىالعقدةالأصليةوعقدةالوجهة،يُعدُالمسارالأقصرالمُمتدمنعقدةالبدايةإلىعقدةالنهايةهوالمسارالأقلتكلفةإجمالًابينجميعالمساراتالموجودةمنالبدايةحتىالوجهة[1］．ولحسابتكلفةالمسار، يجمع الشخص تكاليف كل حافة على حدة。ويُمكناستخدامالتكلفةلقياس المسافة، أو الوقت، أو أي عامل آخر。على سبيل المثال، في خريطة المدينة الصغيرة فيالشكل1،يُمكنأنيكونالمسارالأقصرمنالمنزلحتىالمدرسةهوالطريقالذييُمكناجتيازهفيأقلوقتمنبينالمساراتالمُتاحة。ومنالمُمكنتواجدأكثرمنمسارقصيربينعقدتينفيالشبكة؛لاحتماليةامتلاكالمساراتالمتعددةالحدالأدنىذاتهمنالتكلفة。ولهذاالسبب،نقول”أحد”أقصرالمساراتبينعقدتين(حتىوإنبداذلكغريبًا)،بدلًامنأننقول”أقصر”مساربينهما。

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

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

فيالرياضيات،كثيرًامانُميزالعقدباستخدامالأرقام(انظرتقاطعاتالطُرُقفيالشكل1)، أو الحروف (انظرالشكل2)．وللتبسيط،نفترضأنجميعالأشياءتحتويعلىبُعدين(كماهوالحالفيالرسمعلىقطعةمنالورق)؛لذلكسنقيسالمسافةبالطريقةالتيتُقاسبهاالمسافةالموجودةبيننقطتينعلىأرضيةمنزلك。ولن نقلق حيال أشياء مثل ارتفاع، أو انحناء الأرض。وفي الشبكة الموجودة فيالشكل2، إذا أردنا العثور علىالمسارالأقصرالمُمتدمنالعقدة一إلىالعقدة،Fفينبغيأننختارالحوافذاتالتكلفةالأقل。وعلىسبيلالمثال،نختارالحافةذاتالتكلفة2المُمتدةمنالعقدة一إلىالعقدة،Cبدلًامناختيارالحافةذاتالتكلفة4والمُمتدةمنالعقدة一إلىالعقدةCإذيُعدُاختيارالحوافذاتالتكلفةالأقلللعثورعلىالمسارالأقصر،إحدىالأفكارالرئيسيةفيخوارزميةديكسترا(迪杰斯特拉)^2，3.．

خوارزميةديكسترا

“الخوارزمية”هيمجموعةمُحددةمنالخطواتالتينتبعُهالحلمسألةٍما؛مثل مسألة إيجاد المسار الأقصر [1］．وتعنيخوارزميةديسكتراالشهيرةبحلمسألةإيجادالمسارالأقصر،وسُميتبهذاالاسمنسبةًإلىمُخترعهاعالمالحاسوبالهولنديإدسخرديكسترا⁴．

ويُمكننا استخدام هذه الخوارزمية؛لخلقشجرة امتداد للمسارات الأقصر(انظرالشكل2)؛للعثورعلىالمسارالأقصرالمُمتدمنعقدةالبدايةإلىجميعالعُقدالأخرىالموجودةفيالشبكة。ويمكنتحقيقذلكبحسابالمسافةالمُمتدةمنعقدةالبدايةإلىجميعالعُقدالأخرىعلىحدة。وفيهذهالمُناقشة،نستخدمالمسافةباعتبارهاالتكلفة،كمايُمكناستخدامخوارزميةديكسترالحسابأينوعمنالتكلفة。

فيالشكل2، نوضح طريقة استخدام خوارزمية ديكسترا؛لاستنتاجشجرةامتدادالمسارالأقصرللحصولعلىشبكةمُترابطة。تابعالشكل2أثناء قراءة شرحنا هذا، وشاهدالفيديو1؛لتجد شرح هذا المثال بالرسوم المُتحركة。

فيما يلي الخطوات التي نتبِعُها:

1 .نُظلل عقدة“البداية”。(انظر العقدة a فيالشكل2)بالنسبةلجميعالعُقدالمجاورةلعقدةالبداية،نضعالقيمةالأولية”للمسافة”؛لتكونهيالمسافةالمُمتدةمنعقدةالبدايةإلىتلكالعٌقدالمجاورة،والقيمةالأوليةللعقدة”النهائية”؛لتكون هي عقدة البداية。وفي المثال الموضح فيالشكل2،عنداكتمالهذهالخطوة،نضعقيم”المسافة”والعقدة”النهائية”الخاصةبالعقدتين“B”و“C”،فيحينتظلمُدخلات”المسافة”والعقدة”النهائية”الخاصةبالعُقد“D”،و“E”،و“F”خالية。

2.نُماثلالعقدةغيرالمُظللةمعأقلقيمة”مسافة”(باستثناءالخاناتالخالية)،ونصنفهاباعتبارهاعُقدتنا”الحالية”。علىسبيلالمثال،إذابدأناباعتبارالعقدة一عقدةالبداية،فستكونالعقدةCهيالعقدةالحالية؛”لأنالمسافة”المُمتدةمنالعقدة一إلىالعقدةCأقلمن”المسافة”المُمتدةمنالعقدة一إلىالعقدةbوإذاتواجدتأيصلةبينهما،فسنختارالعقدةذاتقيمة”المسافة”الأقل。

3.نُنفذالخطواتالتاليةلجميعالعُقدالمجاورةغيرالمُظللةللعقدة”الحالية”:

”。نُضيفمسافة”العُقدة”الحالية”لقيمةالحافةالمُمتدةمنالعقدة”الحالية”إلىالعقدةالمجاورة。

b。إذاكانت”المسافة”المُمتدةمنالخطوة3أقلمن”مسافة”العُقدةالمجاورة(أوإذاكانت”مسافة”العقدةالمجاورةلاتزالخالية)،فسنُجدد”مسافة”العقدةالمجاورةلتُصبحهي”المسافة”التيحسبناهافيالخطوة3،ونُعينالعقدة”النهائية”المجاورة؛لتُصبح هي العقدة الحالية。

4.عندمانُطبقالخطوة3علىجميعالعقدالمُجاورةللعقدة”الحالية”،نُظللالعقدة”الحالية”،ونشطُبوسمالعقدة”الحالية”。

5.إذا ظُلِلَت جميع العُقد، فسننتقل إلى الخطوة 6。عدا ذلك، نعود مرة أخرى إلى الخطوة 2。

6.نُسلطالضوءعلىالحافةالمُمتدةبينكلعقدةوعقدتها”النهائية”؛لإظهار شجرة امتداد المسار الأقصر من عقدة البداية。

الاستخدامات

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

ولنفترضأنكتُريدزيارةأماكنعدةقبلالعودةإلىالمنزل。كيفتعثرعلىالطريقالأفضلللوصولإلىهذهالوجهات،معتقليلالنفقات؛مثل البنزين، والفنادق، والوقت؟وباختصار،كيفيُمكنناالعثورعلىالمسارالأقصرالذييمُربجميعالعقدالموجودةفيشبكة،ومنثمالعودةإلىعقدةالبداية؟تُعرفهذهالمسألةباسم”مسألةالبائعالمتجول”،وتُعدُامتدادًالمسألةإيجادالمسارالأقصر⁶．

يُعدُّ العثور على المسار الأقصر أمرًا مُهمًّا؛لحلالمسائلالمُختلفةالتيتظهرفيالعديدمنأنواعالشبكاتالمختلفة。علىسبيلالمثال،يُمكنللمساراتالأقصرزيادةفاعليةتخطيطالمدينة。إذيُمكنللمُهندسينالمدنيينتخطيطالمدينةفيصورةشبكة،وتحديدأفضلالأماكنلبناءطرق؛للحدمنالازدحامالمروري،وأفضلالأماكنلتركيبأنابيبالري؛لتوصيل المياه إلى السكان [2］．كمايسمحالعثورعلىالمساراتالأقصربنقلالبياناتمنحاسوبإلىآخربسرعاتٍعاليةٍ؛ممايسمحبانتقالكمياتكبيرةمنالمعلوماتفيثوانٍمعدودة[1，2］．

ويوجدأيضًاالعديدمنأمثلةالمساراتالأقصرفيشبكاتالاتصال،والشبكاتالاجتماعية。علىسبيلالمثال،لنفترضأنكلشخصفيالشبكةالاجتماعيةيُمثلعقدة،وأنكلحافةتمثلالصداقة。حينئذٍ،يُمكنكاستنتاجطريقةالتواصلمعشخصٍخارجمجموعاتصداقاتك؛بواسطة الاتصالات التي يقوم بها أصدقاؤك。إذإنالمساراتالأقصرللاتصالات(كماهوالحالفيالصداقات)بينشخصينعشوائيينفيالولاياتالمتحدةالأمريكية،أقصرمماقديعتقدهالمرء。وفيالمتوسط،توجدأقلمنستِخطواتبينالشخصالأول،والشخصالنهائيفيمثلهذاالمسار[3.] !ويوضحذلكالقِصَرالمثاليللمساراتالأقصرالموجودةبينالأشخاص”ظاهرةالعالمالصغير”،كماساعدتأطوالالمساراتالقصيرةهذهفيوجودمصطلح”ستدرجاتمنالتباعد”(1］．

فخلالجائحةكوفيد-19الأخيرة،كانالعثورعلىالمساراتالأقصرمُفيدًا؛لتقليل نسبة التعرُّض للفيروس كورونا。علىسبيلالمثال،عندالانتقالإلىمُجمعتُجاريعلىمدارالعامونصفالعامالماضيين،استفادالأشخاصمنالعثورعلىالمساراتالأقصر؛لشراءالموادالغذائيةالتيتوجدفيالبقالة(بمراعاةتفاديمُلامسةأشخاصآخرين،بواسطةالتباعُدالجسدي)(4，5］．

الخُلاصة

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

مسردللمصطلحات

الشبكة(网络)：↑هيمجموعةمنالأشياء(تُسمىالعُقَد)،والروابط(تُسمىالحواف)القائمةبينها。

العُقدة(节点)：↑هيالأشياءالموجودةفيالشبكة،والتيتتصلبأشياءأخرى。علىسبيلالمثال،تُمثلالأماكنوالطُرُقالموجودةفيالشكل1المعنى الحقيقي للعقدة。

الحافة(边缘)：↑هيعبارةعنأحدالأشياءالتيتربطعقدتينببعضهما。علىسبيلالمثال،الطريقمنمنزلكإلىالمدرسةيمثلحافة。

المسار(路径)：↑هوسلسلةمنالحوافالمُمتدةمنعقدةالبدايةإلىعقدةالوجهة。

التكلفة(成本)：↑هيقياسكميةالجهدالذييتطلبهالتنقلعلىطولإحدىالحوافعلىالشبكة。وفيالواقع،قدتُستخدمالتكلفةلقياسالمسافة،أوالوقت،أوأيشيءآخر。

المسار الأقصر(最短路径)：↑هوالمسارالمُمتدمنإحدىعقداتالبدايةإلىعقدةالوِجهة،بأقلتكلفةإجماليةمقارنةبجميعالمساراتالمُمتدةمنالبدايةحتىالوجهة。

شجرةامتدادالمسارالأقصر(最短路径生成树)：↑عبارةعنجزءمنشبكةمُتصلة،تبدأمنعقدةبدايةمُحددة،وتُحددالمسارالأقصرالمُمتدمنهاإلىالعُقدالأخرىالموجودةفيالشبكة。علىسبيلالمثال،إذااحتوتالشبكةعلى6عُقد،فسيُشيرذلكإلىوجود5منأقصرالمساراتفيشجرةامتدادالمسارالأقصر。وتحتوي شجرة امتداد الشبكة على جميع عُقد الشبكة。بالإضافةإلىذلك،نظرًالأنشجرةالامتدادهينوعمنالشبكاتيُعرفباسم”الشجرة”؛تمتلكأيعقدتينمنالعُقدالموجودةبهامسارًاواحدًافقطبينهما。

إقرار تضارب المصالح

يعلنالمؤلفونأنالبحثقدأُجريفيغيابأيعلاقاتتجاريةأوماليةيمكنتفسيرهاعلىأنهاتضاربمحتملفيالمصالح。

إقرار

نُعرِبُعنامتناناللقُراءالصِغارنياتشيو،وتارينتشيو،وزويتشيو،وتيخوإلينغ،وحكيمهانسنعلىتعليقاتهمالمُثمرة。ونشكُرأعضاءعائلاته——لمينديتشيو،وكريستيناتشاو،وتيمإلينغ،وستيرلينغهانسلن——جعلناعلىاتصالمعهم،والتماسآرائهم。ونُعربعنامتنانالكلٍمنلينديتشيو،وميشيللي،وتوماسريكسين،وأكراتيساكسيناعلىتعليقاتهمالمُثمرة。كما نشكُر مُراجعينا الصغار، ومُعلميهم؛على اقتراحاتهم الرائعة。地图كماتقدَّرالدعمالمُقدممنالمؤسسةالوطنيةللعلوم(رقمالمنح1922952)،بواسطةبرنامج威胁检测(ATD)算法。

---

المراجع

[1]↑纽曼，m.e.j. 2018。网络，第二版。牛津，英国:牛津大学出版社。

[２]↑克拉默，C.，波特，M. A.，早山，H.，希兹，L.，和乌佐，S.(编著)。2015.网络素养:基本概念和核心思想．网上订购地址:http://tinyurl.com/networkliteracy

[3]↑米尔格拉姆，1967。小世界问题。Psychol今天1:61-7。doi: 10.107 / e400002009 - 005

[4]↑布鲁克斯，H. Z.， Kanjanasaratool, U.，库雷，Y. H.和波特，M. A. 2021。疾病侦探:用数学来预测传染病的传播。前面。年轻人9:577741。doi: 10.3389 / frym.2020.577741

［5］↑Ying, F.和O 'Clery, N. 2021。使用基于代理的模型对COVID-19在超市中的传播进行建模。《公共科学图书馆•综合》16: e0249821。doi: 10.1371 / journal.pone.0249821

مُلحق

دليلالإجابة

النشاط1:(يُمثلالمسارالرئيسي،ومسارشجرةالدردار،ومسارالطالب)أحدالمساراتالمُمكنة。(ويُمثلالمسارالرئيسي،ومسارشجرةالبلوط،ومسارشجرةالنخيل،ومسارالطالب)أحدالمساراتالأخرىالمُمكنة。(ويُمثلمسارشجرةالصنوبر،ومسارشجرةالقيقب،ومسارالطالب)المسارالثالثالمُمكناتباعه。

النشاط2:يُعدهذاأحدأمثلةشجرةامتدادالمسارالأقصرالمُكتملة،للشبكةالموجودةفيالشكل3．تابع شرحنا فيالفيديو2．

---

الحواشي

[1]↑ويكيبيديا، الموسوعة الحرة。2020.مسألة إيجاد المسار الأقصر。مُتاحة على الإنترنت عبر:https://en.wikipedia.org/wiki/Shortest_path_problem(اِطُلِعَ عليها بتاريخ 20 أغسطس 2020)

[２]↑عندنُطقكلمةDIJKSTRAبالإنجليزية،لانلفظحرف“J”。

[3]↑موقعCode.org．2020.دليلالأنشطةU2L07——خوارزميةديكسترالإيجادالمسارالأقصر。مُتاحة。على الإنترنت عبر:https://docs.google.com/document/d/15N7aHAoWG1_9VIcDHNZRygzFK0hle-EHlmHu0PZI8D4/view(اِطُلِعَ عليها بتاريخ 20 أغسطس 2020)

[4]↑ويكيبيديا، الموسوعة الحرة。2020.Edsger W. Dijkstra。مُتاحة على الإنترنت عبر:https://en.wikipedia.org/wiki/Edsger_W._Dijkstra(اِطُلِعَ عليها بتاريخ 20 أغسطس 2020)

［5］↑يُمكنك تنزيل نسخة قابلة للطباعة منالشكل3عبرhttps://drive.google.com/file/d/1rNONK-cmy4gq_aCJRnAYpe9Y2HSeq2A1/view．

[6]↑طالع الرابط التاليhttps://www.youtube.com/watch?v=q8nQTNvCrjE&t=35s．