خوارزميات تحديد المسار

الخوارزميات الاستطلاعية أو خوارزميات تحديد المسار هي خوارزميات مستخدمة في التطبيقات من أجل إيجاد أقصر طريق بين نقطتين. تستخدم العديد من الخوارزميات في هذا المجال، مثل: خوارزمية ديكسترا وخوارزمية البحث بأولوية الأفضل.

مثال لطريقين من النقطة A إلى النقطة B. حيث تكمن مهمة هذه الخوارزميات في إيجاد أقرب طريق بين النقطتين.

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

نطاق الخوارزمية

مثال إيجاد أقرب مسار بين المربع الأخضر والمربع الأزرق.

أخضر: نقطة البداية
أحمر: الطريق المُتَّبَعة
أزرق: النقطة الهدف
رمادي: عائق لا يمكن المرور من خلاله

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

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

الخوارزمية

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