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

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

الخوارزمية

خطوات الخوارزمية تكون كالآتي:

تهيئة جميع النقاط كنقاط لم تتم زيارتها. حدد نقطة عشوائية، قم بتعيينها بصفتها النقطة الحالية، أشر النقطة على أنها نقطة تمت زيارتها.

حدد أقصر طريق مع النقط المجاورة. عين نقطة أخرى وقم بزيارتها بحسب الطريق الأقصر.

قم بالإنهاء إذا كنت قد زرت جميع النقط، وإلا، فعد للخطوة الثالثة.

تسلسل النقط التي تمت زيارتها هو ناتج الخوارزمية.

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

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