توجيه المسار الأقصر k

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

تُعدّ مسألة توجيه أقصر k مسار تعميمًا لمسألة توجيه أقصر مسار في شبكة معينة . فهي لا تقتصر على البحث عن أقصر مسار فحسب، بل تتناول أيضًا أقصر k-1 مسارًا تالية (والتي قد تكون أطول من أقصر مسار). ومن بين صيغ هذه المسألة مسألة أقصر k مسارًا بدون حلقات .

يمكن إيجاد أقصر k مسار عن طريق توسيع خوارزمية ديكسترا أو خوارزمية بيلمان-فورد .

تاريخ

منذ عام 1957، نُشرت العديد من الأبحاث حول مسألة توجيه أقصر k مسار. أُنجزت معظم الأعمال الأساسية بين ستينيات القرن العشرين وعام 2001. ومنذ ذلك الحين، انصبّ معظم البحث على تطبيقات المسألة ومتغيراتها. في عام 2010، نشر مايكل غونتر وآخرون كتابًا بعنوان " الحساب الرمزي لأقصر k مسار والمقاييس ذات الصلة باستخدام أداة جبر العمليات العشوائية CASPA" . [ 1 ]

الخوارزمية

يمكن تعميم خوارزمية ديكسترا لإيجاد أقصر k مسار.

التعريفات :
  • G(V, E) : رسم بياني موجه مرجح، مع مجموعة من الرؤوس V ومجموعة من الحواف الموجهة E ،
  • w(u, v) : تكلفة الحافة الموجهة من العقدة u إلى العقدة v (التكاليف غير سالبة).
يتم حذف الروابط التي لا تستوفي قيود أقصر مسار من الرسم البياني
  • s : عقدة المصدر
  • t : عقدة الوجهة
  • K : عدد أقصر المسارات المطلوب إيجادها
  • p u : مسار من s إلى u
  • B عبارة عن بنية بيانات كومة تحتوي على مسارات
  • P : مجموعة أقصر المسارات من s إلى t
  • عدد المسارات الأقصر التي تم العثور عليها إلى العقدة u

الخوارزمية:

P = فارغ،
احسب u = 0، لكل u في V
أدخل المسار p s = {s} في B بتكلفة 0
طالما أن B ليست فارغة، احسب t < K :
- ليكن p u أقصر مسار تكلفة في B بتكلفة C
– B = B − {p u } ، count u = count u + 1
– إذا كانت u = t فإن P = P U {p u }
– إذا كان العدد u ≤ K فإن
  • لكل رأس v مجاور لـ u :
- ليكن p v مسارًا جديدًا بتكلفة C + w(u, v) يتكون من ربط الحافة (u, v) بالمسار p u
- أدخل p v في B
إرجاع P

الاختلافات

يوجد نوعان رئيسيان من مسألة توجيه أقصر k مسار. في النوع الأول، يُسمح للمسارات بزيارة العقدة نفسها أكثر من مرة، مما يُنشئ حلقات. أما في النوع الثاني، فيُشترط أن تكون المسارات بسيطة وخالية من الحلقات . يُمكن حل النوع الذي يحتوي على حلقات باستخدام خوارزمية إبشتاين [ 2 ] ، بينما يُمكن حل النوع الخالي من الحلقات باستخدام خوارزمية ين [ 3 ] [ 4 ] .

نسخة لووبي

في هذا الشكل، تُبسط المشكلة بعدم اشتراط أن تكون المسارات خالية من الحلقات. [ 4 ] قدم بي إل فوكس حلاً في عام 1975، حيث يتم تحديد أقصر k مسار في تعقيد زمني تقاربي قدره O ( m + kn log n ) (باستخدام ترميز Big O ). [ 5 ] في عام 1998، أبلغ ديفيد إبستين عن نهج يحافظ على تعقيد زمني تقاربي قدره O ( m + n log n + k ) عن طريق حساب تمثيل ضمني للمسارات، يمكن إخراج كل منها في O ( n ) من الوقت الإضافي. [ 2 ] [ 4 ] في عام 2015، ابتكر أكيبا وآخرون طريقة فهرسة كبديل أسرع بكثير لخوارزمية إبستين، حيث يتم إنشاء بنية بيانات تسمى فهرسًا من رسم بياني، ثم يمكن الحصول بسرعة على أعلى k مسافة بين أي زوج من الرؤوس. [ 6 ] 

نسخة بدون حلقات

في الصيغة الخالية من الحلقات، يُمنع احتواء المسارات على حلقات، مما يُضيف مستوى إضافيًا من التعقيد. [ 4 ] يُمكن حل هذه المشكلة باستخدام خوارزمية ين [ 3 ] [ 4 ] لإيجاد أطوال جميع أقصر المسارات من عقدة ثابتة إلى جميع العقد الأخرى في شبكة ذات n عقدة بمسافات غير سالبة، وهي تقنية تتطلب فقط 2^ n ^2 عملية جمع و n^ 2 عملية مقارنة، أي أقل مما تتطلبه خوارزميات أقصر المسارات الأخرى المتاحة . يُعد تعقيد وقت التشغيل شبه متعدد الحدود ، حيث يبلغ O ( kn ( m + n log n )) (حيث يُمثل m و n عدد الحواف والرؤوس، على التوالي). [ 3 ] [ 4 ] في عام 2007، اقترح جون هيرشبرغر وسوبهاش سوري خوارزمية مسارات الاستبدال، وهي تطبيق أكثر كفاءة لخوارزمية لولر [ 7 ] وخوارزمية ين، مع تحسين زمني قدره O ( n ) لعدد كبير من الرسوم البيانية، ولكن ليس جميعها (وبالتالي لا يغير الحد التقاربي لخوارزمية ين). [ 8 ]

بعض الأمثلة والوصف

المثال 1

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

شبكة مكونة من 15 عقدة تحتوي على مزيج من الروابط ثنائية الاتجاه وأحادية الاتجاه

المثال 2

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

يمكن الاطلاع على التفاصيل الكاملة في " مختبر رؤية الحاسوب - CVLAB".

المثال 3

يُستخدم خوارزميات أقصر k مسارًا أيضًا في تصميم شبكة نقل تُحسّن تجربة الركاب في أنظمة النقل العام. ويمكن إنشاء مثال على شبكة نقل كهذه مع مراعاة وقت السفر. بالإضافة إلى وقت السفر، يمكن أخذ شروط أخرى في الاعتبار بناءً على القيود الاقتصادية والجغرافية. وعلى الرغم من اختلاف المعايير، فإن خوارزميات أقصر k مسارًا تجد الحلول الأمثل التي تُلبي جميع احتياجات المستخدمين تقريبًا. وقد أصبحت هذه التطبيقات لخوارزميات أقصر k مسارًا شائعة، حيث درس كل من Xu وHe وSong وChaudhry (2012) مؤخرًا مشاكل أقصر k مسارًا في أنظمة شبكات النقل. [ 9 ]

التطبيقات

يُعدّ توجيه أقصر مسار k بديلاً جيداً لما يلي:

يقدم Cherkassky et al. [ 10 ] المزيد من الخوارزميات والتقييمات المرتبطة بها.

انظر أيضاً

ملحوظات

  1. ↑ غونتر، مايكل؛ شوستر، يوهان؛ سيغل، ماركوس (27-04-2010). "الحساب الرمزي لأقصر k مسارًا والمقاييس ذات الصلة باستخدام أداة جبر العمليات العشوائية CASPA". الحساب الرمزي لأقصر k مسارًا والمقاييس ذات الصلة باستخدام أداة جبر العمليات العشوائية CASPA . ACM. ص 13-18 . doi : 10.1145/1772630.1772635 . ISBN  978-1-60558-916-9.
  2. 1 2 إبستين، ديفيد (1998). "إيجاد أقصر k مسار" (ملف PDF) . مجلة SIAM للحوسبة 28 (2): 652-673 . doi : 10.1137/S0097539795290477 .
  3. 1 2 3 ين، جيه واي (1971). "إيجاد أقصر k مسار بدون حلقات في الشبكة". علوم الإدارة . 17 (11): 712-716 . doi : 10.1287/mnsc.17.11.712 ..
  4. 1 2 3 4 5 6 بوييه، إريك؛ إليناس، جورجيوس؛ لابورديه، جان فرانسوا؛ رامامورثي، رامو (2007). "توجيه المسار - الجزء 2: الاستدلالات" . توجيه المسار في الشبكات الضوئية المتشابكة . جون وايلي وأولاده . الصفحات 125-138 . ISBN  9780470015650.
  5. ↑ فوكس، بي إل (1975). " أقصر المسارات من الرتبة K وتطبيقاتها على الشبكات الاحتمالية". الاجتماع الوطني المشترك لجمعية أبحاث العمليات/جمعية نظم المعلومات الرياضية . 23 : B263.معرف المقالة الوطنية لـ CiNii : 10012857200.
  6. ↑ أكيبا، تاكويا؛ هاياشي، تاكانوري؛ نوري، نوزومي؛ إيواتا، يويتشي؛ يوشيدا، يويتشي (يناير 2015). "استعلامات فعّالة عن أقصر k مسار على الشبكات الكبيرة باستخدام تصنيف المعالم المُقَصَّر" . وقائع المؤتمر التاسع والعشرين لجمعية النهوض بالذكاء الاصطناعي (AAAI) . أوستن، تكساس: جمعية النهوض بالذكاء الاصطناعي . الصفحات 2-8 . 
  7. ↑ لولر، يوجين ل. (1972-03-01). "إجراء لحساب أفضل K حلول لمسائل التحسين المنفصلة وتطبيقه على مسألة أقصر مسار" . مجلة علوم الإدارة . 18 (7): 401-405 . doi : 10.1287/mnsc.18.7.401 . ISSN 0025-1909 . 
  8. ↑ هيرشبرغر، جون ؛ ماكسيل، ماثيو؛ سوري، سوبهاش (2007). "إيجاد أقصر k مسارًا بسيطًا: خوارزمية جديدة وتطبيقها" (ملف PDF) . معاملات ACM في الخوارزميات . 3 (4). المقالة 45 (19 صفحة). doi : 10.1145/1290672.1290682 . S2CID 10703503 . 
  9. ↑ شو، وانغتو؛ هي، شيوي؛ سونغ، روي؛ شودري، سهيل س. (2012). "إيجاد أقصر k مسار في شبكة نقل قائمة على الجدولة". الحوسبة وبحوث العمليات . 39 (8): 1812-1826 . doi : 10.1016/j.cor.2010.02.005 . S2CID 29232689 . 
  10. ↑ تشيركاسكي، بوريس ف.؛ غولدبيرغ، أندرو ف .؛ رادزيك، توماش (1996). "خوارزميات أقصر المسارات: النظرية والتقييم التجريبي". البرمجة الرياضية . 73 (2): 129-174 . Bibcode : 1996MatPr..73..129C . doi : 10.1007/BF02592101 . ISSN 0025-5610 . S2CID 414427 .