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

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

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

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

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

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

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

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

المراجع 

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