إيجاد المسار

الموسوعة الحرة
المسارات المتكافئة بين A و B في بيئة ثنائية الأبعاد

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

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

الخوارزميات

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

تتمثل المشكلتان الرئيسيتان في إيجاد المسار في: (1) إيجاد مسار بين عقدتين في الرسم البياني ؛ و(2) مشكلة أقصر مسار - أي إيجاد أقصر مسار أمثل . تعالج الخوارزميات الأساسية، مثل البحث بالعرض أولاً والبحث بالعمق أولاً، المشكلة الأولى من خلال استنفاد جميع الاحتمالات؛ بدءًا من العقدة المعطاة، تتكرر هذه الخوارزميات على جميع المسارات المحتملة حتى تصل إلى عقدة الوجهة. تعمل هذه الخوارزميات فييا(|V|+|هـ|){\displaystyle O(|V|+|E|)}، أو الوقت الخطي، حيث V هو عدد الرؤوس، و E هو عدد الحواف بين الرؤوس.

تكمن المشكلة الأكثر تعقيدًا في إيجاد المسار الأمثل. يُعرف النهج الشامل في هذه الحالة باسم خوارزمية بيلمان-فورد ، والتي ينتج عنها تعقيد زمني قدرهيا(|V||هـ|){\displaystyle O(|V||E|)}أو زمن تربيعي. مع ذلك، ليس من الضروري فحص جميع المسارات الممكنة للعثور على المسار الأمثل. تعمل خوارزميات مثل A* وخوارزمية ديكسترا على استبعاد المسارات بشكل استراتيجي، إما من خلال أساليب استدلالية أو من خلال البرمجة الديناميكية . وباستبعاد المسارات المستحيلة، يمكن لهذه الخوارزميات تحقيق تعقيد زمني منخفض يصل إلىيا(|هـ|سجل⁡(|V|)){\displaystyle O(|E|\log(|V|))}[ 1 ]​

تُعدّ الخوارزميات المذكورة أعلاه من بين أفضل الخوارزميات العامة التي تعمل على الرسم البياني دون معالجة مسبقة. مع ذلك، في أنظمة توجيه الرحلات العملية، يمكن تحقيق تعقيدات زمنية أفضل باستخدام خوارزميات تُجري معالجة مسبقة للرسم البياني لتحسين الأداء. [ 2 ] ومن هذه الخوارزميات خوارزمية التسلسل الهرمي الانكماشي .

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

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

تفشل خوارزمية ديكسترا في حال وجود وزن سالب للحافة . ​​في الحالة الافتراضية حيث تُشكّل العقد A وB وC رسمًا بيانيًا متصلًا غير موجه بحواف AB = 3 وAC = 4 وBC = -2، فإن المسار الأمثل من A إلى C يكلف 1، والمسار الأمثل من A إلى B يكلف 2. تبدأ خوارزمية ديكسترا من A بفحص B أولًا، لكونها الأقرب. ستُخصص لها تكلفة 3، وتُعلّمها كمغلقة، أي لن يُعاد تقييم تكلفتها أبدًا. لذلك، لا تستطيع خوارزمية ديكسترا تقييم الأوزان السالبة للحواف. مع ذلك، ولأنه في كثير من التطبيقات العملية لن يكون هناك وزن سالب للحافة، فإن خوارزمية ديكسترا مناسبة إلى حد كبير لغرض إيجاد المسار.

خوارزمية A*

خوارزمية A* هي نسخة معدلة من خوارزمية ديكسترا، ولها استخدامات متعددة. تُخصص A* وزنًا لكل عقدة مفتوحة يساوي وزن الحافة المؤدية إلى تلك العقدة مضافًا إليه المسافة التقريبية بين تلك العقدة ونقطة النهاية. تُحسب هذه المسافة التقريبية باستخدام دالة استدلالية ، وتمثل أقصر مسافة ممكنة بين تلك العقدة ونقطة النهاية. يسمح هذا للخوارزمية باستبعاد المسارات الأطول بمجرد العثور على مسار أولي. إذا كان هناك مسار بطول x بين نقطة البداية ونقطة النهاية، وكانت أقصر مسافة بين عقدة ونقطة النهاية أكبر من x، فلا داعي لفحص تلك العقدة. [ 5 ]

تستخدم خوارزمية A* هذه الطريقة الاستدلالية لتحسين أدائها مقارنةً بخوارزمية ديكسترا. عندما تكون قيمة الطريقة الاستدلالية صفرًا، تُصبح A* مُكافئة لخوارزمية ديكسترا. مع ازدياد قيمة الطريقة الاستدلالية واقترابها من المسافة الحقيقية، تستمر A* في إيجاد المسارات المثلى، ولكنها تعمل بشكل أسرع (بفضل فحص عدد أقل من العُقد). عندما تكون قيمة الطريقة الاستدلالية مساوية تمامًا للمسافة الحقيقية، تفحص A* أقل عدد ممكن من العُقد. (مع ذلك، من غير العملي عمومًا كتابة دالة استدلالية تُحسب دائمًا المسافة الحقيقية، حيث يُمكن غالبًا الوصول إلى نفس نتيجة المقارنة باستخدام حسابات أبسط - على سبيل المثال، استخدام مسافة تشيبيشيف بدلًا من المسافة الإقليدية في الفضاء ثنائي الأبعاد ). مع ازدياد قيمة الطريقة الاستدلالية، تفحص A* عددًا أقل من العُقد، ولكنها لم تعد تضمن مسارًا أمثل. في العديد من التطبيقات (مثل ألعاب الفيديو)، يُعد هذا مقبولًا، بل ومرغوبًا فيه، للحفاظ على سرعة تشغيل الخوارزمية.

في ألعاب الفيديو

لطالما استُخدمت خوارزمية تحديد المسار في ألعاب الفيديو التي تحتوي على أجسام متحركة أو شخصيات غير قابلة للعب. وصف كريس كروفورد في عام 1982 كيف "أهدر الكثير من الوقت" في محاولة حل مشكلة في خوارزمية تحديد المسار في لعبة Tanktics ، حيث كانت الدبابات الحاسوبية تُحاصر على اليابسة داخل بحيرات على شكل حرف U. وقال: "بعد جهد كبير ضائع، اكتشفتُ حلاً أفضل: حذف البحيرات على شكل حرف U من الخريطة". [ 6 ]

البحث عن المسار الهرمي

يمكن استخدام الأشجار الرباعية لإيجاد المسار الهرمي

يسبق مفهوم البحث الهرمي عن المسار تبنيه في صناعة ألعاب الفيديو، ويعود بجذوره إلى أبحاث الذكاء الاصطناعي الكلاسيكية. يظهر أحد أقدم الأوصاف الرسمية في عمل ساكردوتي حول خوارزمية ABSTRIPS (خوارزمية STRIPS القائمة على التجريد ) عام 1974، [ 7 ] والذي استكشف استراتيجيات البحث الهرمي في التخطيط القائم على المنطق. وقد طورت أبحاث لاحقة، مثل خوارزمية A* الهرمية لهولت وآخرون، نظرية التسلسل الهرمي للتجريد في مسائل البحث. [ 8 ]

في سياق ألعاب الفيديو، أدت الحاجة إلى تخطيط فعال على خرائط كبيرة بوقت معالجة محدود إلى التطبيق العملي لخوارزميات البحث عن المسار الهرمي. وكان من أبرز التطورات تقديم خوارزمية البحث عن المسار الهرمي A* (HPA*) من قِبل بوتيا وآخرون عام 2004. [ 9 ] تقوم خوارزمية HPA* بتقسيم الخريطة إلى مجموعات وحساب المسارات المحلية المثلى مسبقًا بين نقاط دخول المجموعات المتجاورة. أثناء التشغيل، تخطط الخوارزمية مسارًا مجردًا عبر مخطط المجموعات، ثم تُحسّن هذا المسار داخل كل مجموعة. هذا يقلل بشكل كبير من مساحة البحث ويسمح بتخطيط شبه مثالي بأداء أسرع بكثير.

تعتمد خوارزمية التحسين الجزئي A* (PRA*)، التي طورها ستورتيفانت وبورو، نهجًا مشابهًا، لكنها تركز على التخطيط والتنفيذ المتداخلين. فبدلًا من تحسين المسار بأكمله دفعة واحدة، تُحسّن PRA* الخطوات القليلة الأولى فقط، ثم تُواصل تحسين الباقي حسب الحاجة أثناء التنفيذ. وهذا مفيدٌ للغاية في البيئات الديناميكية.

وتشمل التقنيات المماثلة شبكات الملاحة (navmesh)، المستخدمة في التخطيط الهندسي في الألعاب، وتخطيط النقل متعدد الوسائط ، كما هو الحال في اختلافات مشكلة البائع المتجول التي تتضمن أنواعًا متعددة من وسائل النقل.

تُجري خوارزمية التخطيط الهرمي عملية البحث عن المسار على مرحلتين: أولاً، بين المجموعات على مستوى عالٍ؛ ثم، داخل كل مجموعة على مستوى منخفض. [ 10 ] يُمكّن هذا الهيكل من إجراء بحث محلي مُوجّه باستخدام عدد أقل من العُقد ، مما يُؤدي إلى أداء عالٍ. أما العيب الرئيسي فيكمن في تعقيد تنفيذ صيانة طبقات التجريد والتحسينات.

مثال

تحتوي خريطة بحجم 3000×2000 عقدة على 6 ملايين مربع. يُعدّ تخطيط مسار مباشر على هذا النطاق، حتى مع استخدام خوارزمية مُحسّنة ، عمليةً مُرهقةً حسابيًا نظرًا للعدد الهائل من عقد الرسم البياني والمسارات المُحتملة. يقسم النهج الهرمي الخريطة إلى مجموعات من 300×200 عقدة، مُشكّلةً شبكة 10×10 (100 مجموعة إجمالًا). يحتوي الرسم البياني المُجرّد عالي المستوى الآن على 100 عقدة فقط. يتم تخطيط مسار بين هذه المجموعات، وهي عملية غير مُرهقة حسابيًا. بمجرد العثور على المسار المُجرّد، تتم معالجة كل مجموعة على المسار باستخدام مُخطّط A* عادي للعثور على المسار الدقيق منخفض المستوى داخلها. تُحسّن هذه العملية ذات المرحلتين الكفاءة بشكل كبير مع الحفاظ على جودة مسار شبه مثالية.

الخوارزميات المستخدمة في البحث عن المسار

البحث عن المسار متعدد العوامل

يهدف البحث عن المسار متعدد العوامل إلى إيجاد مسارات لعدة عوامل من مواقعها الحالية إلى مواقعها المستهدفة دون تصادم، مع تحسين دالة التكلفة في الوقت نفسه، مثل مجموع أطوال مسارات جميع العوامل. وهو تعميم للبحث عن المسار. العديد من خوارزميات البحث عن المسار متعدد العوامل مُعممة من خوارزمية A*، أو مبنية على اختزالها إلى مسائل أخرى مدروسة جيدًا مثل البرمجة الخطية الصحيحة. [ 11 ] مع ذلك، عادةً ما تكون هذه الخوارزميات غير مكتملة؛ أي لم يُثبت أنها تُنتج حلًا في وقت متعدد الحدود. تعتمد بعض الأساليب المتوازية، مثل الانتشار التعاوني ، على خوارزميات متوازية بشكل كبير، حيث تُوزع البحث عن المسار متعدد العوامل في هياكل شبكية حسابية، مثل الخلايا المشابهة للأتمتة الخلوية . تُضحي فئة أخرى من الخوارزميات بالأمثلية من أجل الأداء، إما باستخدام أنماط الملاحة المعروفة (مثل تدفق حركة المرور) أو طوبولوجيا فضاء المسألة. [ 12 ]

انظر أيضاً

مراجع

  1. ↑ "7.2.1 مسألة أقصر المسارات من مصدر واحد: خوارزمية ديكسترا" . مؤرشف من الأصل بتاريخ 2016-03-04 . تم الاطلاع عليه بتاريخ 2012-05-18 .
  2. ↑ ديلينغ، د.؛ ساندرز، ب .؛ شولتس، د.؛ فاغنر، د. (2009). "هندسة خوارزميات تخطيط المسارات". خوارزميات الشبكات الكبيرة والمعقدة: التصميم والتحليل والمحاكاة . سلسلة محاضرات في علوم الحاسوب. المجلد 5515. سبرينغر. الصفحات 117-139 . CiteSeerX 10.1.1.164.8916 . doi : 10.1007/978-3-642-02094-0_7 . ISBN    978-3-642-02093-3.
  3. ^ ديكسترا ، إي دبليو (ديسمبر 1959). “ملاحظة حول مشكلتين فيما يتعلق بالرسوم البيانية”. الرياضيات الرقمية . 1 (1): 269-271 . دوى : 10.1007 / BF01386390 .
  4. ^ "5.7.1 خوارزمية ديكسترا" .
  5. ↑ "مقدمة في البحث عن المسار A*" .
  6. ↑ كروفورد، كريس (ديسمبر 1982). "تقنيات وأفكار تصميم ألعاب الكمبيوتر" . بايت . ص 96. تم الاطلاع عليه بتاريخ 19 أكتوبر 2013 . 
  7. ↑ ساكردوتي، إيرل د (1974). "التخطيط في تسلسل هرمي لمساحات التجريد" (ملف PDF) . الذكاء الاصطناعي . 5 (2): 115-135 . doi : 10.1016/0004-3702(74)90026-5 .
  8. ↑ هولت، روبرت سي وبيريز، إم بي وزيمر، آر إم وماكدونالد، إيه جيه (1995). الهرمي أ* . ندوة حول التجريد وإعادة الصياغة والتقريب.{{cite conference}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  9. ↑ بوتيا، آدي ومولر، مارتن وشيفر، جوناثان (2004). "إيجاد المسار الهرمي شبه الأمثل". مجلة تطوير الألعاب . 1 : 7-28 . CiteSeerX 10.1.1.479.4675 . {{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  10. ↑ بيليكانو، نوريا وفونتيس، كارلوس (2016). "البحث الهرمي عن المسار لشبكات الملاحة (HNA*)" (ملف PDF) . الحوسبة والرسومات . 59 : 68-78 . doi : 10.1016/j.cag.2016.05.023 . hdl : 2117/98738 .{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  11. ↑ هانغ ما، سفين كونيغ، نورا أيانيان، ليرون كوهين، وولفغانغ هونيغ، تي كي ساتيش كومار، تانسيل أوراس، هونغ شو، كريغ توفي، وغوني شارون. نظرة عامة: تعميمات لإيجاد المسار متعدد العوامل لسيناريوهات العالم الحقيقي. مؤرشف في 15 يوليو 2021 على موقع Wayback Machine. في ورشة عمل المؤتمر الدولي المشترك الخامس والعشرين حول الذكاء الاصطناعي (IJCAI) حول إيجاد المسار متعدد العوامل. 2016.
  12. ↑ خورشيد، مختار (2011). "خوارزمية زمنية متعددة الحدود لإيجاد المسار الأمثل متعدد العوامل" . SOCS .