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

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

هذه هي خطوات الخوارزمية:

1. قم بتهيئة جميع الرؤوس على أنها غير مُزارة.
2. حدد رأسًا عشوائيًا، واجعله الرأس الحالي u . ضع علامة على u بأنه تمت زيارته.
3. أوجد أقصر حافة تربط الرأس الحالي u برأس لم تتم زيارته v .
4. قم بتعيين v كرأس حالي u . ضع علامة على v بأنه تمت زيارته.
5. إذا تمت زيارة جميع الرؤوس في المجال، فقم بالإنهاء. وإلا، فانتقل إلى الخطوة 3.

يمثل تسلسل الرؤوس التي تمت زيارتها ناتج الخوارزمية.

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

في أسوأ الأحوال، ينتج عن الخوارزمية مسار أطول بكثير من المسار الأمثل. تحديدًا، لكل قيمة ثابتة r، توجد حالة من مسألة البائع المتجول يكون فيها طول المسار المحسوب بواسطة خوارزمية أقرب جار أكبر من r ضعف طول المسار الأمثل. علاوة على ذلك، لكل عدد من المدن، توجد قيمة للمسافات بين المدن ينتج عنها أسوأ مسار ممكن باستخدام خوارزمية أقرب جار. (إذا طُبقت الخوارزمية على كل رأس كنقطة بداية، فسيكون أفضل مسار مُكتشف أفضل من N/2-1 مسارًا آخر على الأقل، حيث N هو عدد الرؤوس). ^{[ 1 ]}

قد لا تجد خوارزمية أقرب جار مسارًا ممكنًا على الإطلاق، حتى عندما يكون موجودًا.

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

• G. Gutin, A. Yeo and A. Zverovitch, Exponential Neighborhoods and Domination Analysis for the TSP, in The Traveling Salesman Problem and Its Variations, G. Gutin and AP Punnen (eds.), Kluwer (2002) and Springer (2007).
• جي. جوتين، أ. يو وأ. زفيروفيتش، البائع المتجول لا ينبغي أن يكون جشعاً: تحليل الهيمنة للأساليب الاستدلالية من النوع الجشع لمسألة البائع المتجول . الرياضيات التطبيقية المنفصلة 117 (2002)، 81-86.
• J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails . Discrete Optimization 1 (2004), 121–127.
• G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems , Discrete Optimization 3 (2006), 288–298.