خوارزمية الجار الأقرب
المحتويات

تعريفًا بالموضوع، تعد خوارزمية الجار الأقرب إحدى أولى الخوارزميات التي تم تقديمها لحل مشكلة البائع المتجول. حيث يبدأ البائع من مدينة عشوائية ثم يزور أقرب المدن له بشكل مستمر حتى يكمل زيارة جميع المدن. تكون الجولة الناتجة عن الخوارزمية قصيرة عادة، لكنها لا تمثل الحل المثالي لهذه المشكلة. وفيما يلي تفاصيل أوسع عن ذلك.
الخوارزمية
وفي هذا السياق، تهيئة جميع النقاط كنقاط لم تتم زيارتها. حدد نقطة عشوائية، قم بتعيينها بصفتها النقطة الحالية، أشر النقطة على أنها نقطة تمت زيارتها.
- حدد أقصر طريق مع النقط المجاورة. عين نقطة أخرى وقم بزيارتها بحسب الطريق الأقصر.
- قم بالإنهاء إذا كنت قد زرت جميع النقط، وإلا، فعد للخطوة الثالثة.
- تسلسل النقط التي تمت زيارتها هو ناتج الخوارزمية.
خطوات الخوارزمية تكون كالآتي:
وفي هذا السياق، في الحالات الاسوء، ينتج عن الخوارزمية جولة أطول بكثير من الجولة المثلى. لكل مسافر هناك تعيين مسافات بين المدن التي ينتج عنها اجراءات لخوارزمية الجار الأقرب يُمكن أن تنتج أسوء جولة ممكنة. وإذا تم تطبيق الخوارزمية على كل نقطة كنقطة البداية، فإن أفضل مسار يُمكن إيجاده سيكون أفضل من ن\2-1، حيث ن هو عدد النقاط.
وفي هذا السياق، إن خوارزمية الجار الأقرب سهلة التنفيذ وتنفذ بسرعة، لكنها قد تفوت في بعض الأحيان طرقًا أقصر يمكن ملاحظتها بسهولة من خلال بصيرة الإنسان ويرجع ذلك للطبيعة «الجشعة» للخوارزمية. لكن كقاعدة عامة، إذا كانت المراحل القليلة الأخيرة من الجولة قابلة للمقارنة من حيث الطول مع المراحل الأولى، فيُمكن القول أن الرحلة مجدية ومعقولة؛ أما إذا كانت أكبر بكثير، فمن المحتمل وجود احتمالات لجولات أخرى أفضل بكثير. تحقق آخر يُمكن القيام به لفحص جودة الخوارزمية، وهو استخدام خوارزمية مثل خوارزمية الحد الأدنى لتقدير ما إذا كانت هذه الجولة جيدة بما فيه الكفاية.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟