الرسوم البيانية والشبكاتSalesman

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

تتمثل إحدى الطرق البسيطة في تجربة جميع المسارات الممكنة ، والعثور على طول كل منها ، ثم اختيار أقصر مسار. لكننا أظهرنا للتو أنه حتى مع ${tsn2} مدينة فقط هناك ${tsn2}! = ${factorial(tsn2)} من المسارات الممكنة. بمجرد حصولك على مئات أو آلاف الرؤوس ، يصبح من المستحيل تجربة جميع المسارات الممكنة ، حتى باستخدام أجهزة كمبيوتر قوية.