تغيير اللغة

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

سجّل الدخول إلى Mathigon

أو

حساب جديد     إعادة تعيين كلمة المرور     

الرسوم البيانية والشبكات
مقدمة
جسور كونيجسبيرج
المصافحة والتعارف
مخططات مستوية
تلوين الخريطة
مشكلة البائع المتجول
مشاكل الجدولة
الرسوم البيانية في الحياة اليومية

شارك

إعادة تعيين التقدم

سيؤدي هذا إلى حذف تقدمك وبيانات الدردشة لجميع الفصول في هذه الدورة التدريبية ، ولا يمكن التراجع عنها!

قائمة المصطلحات

حدد واحدة من الكلمات الرئيسية على اليسار ...

الرسوم البيانية والشبكاتمشكلة البائع المتجول

وقت القراءة: ~15 min

دعونا نفكر ، مرة أخرى ، في الشبكات والخرائط. تخيل أن على خدمة التوصيل زيارة ${tsn} مدن مختلفة لتوزيع الطرود. يمكننا التفكير في هذه المدن على أنها الرؤوس في الرسم البياني. إذا كانت جميع المدن متصلة بالطرق ، فهذا ، لذلك هناك ${tsn} × (${tsn} - 1) 2 = ${tsn*(tsn-1)/2} إجمالي الحواف.

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

هناك احتمالات مختلفة لا تعد ولا تحصى لدورات هاميلتون في الرسوم البيانية الكاملة. في الواقع ، يمكننا اختيار أي روؤس كبداية ، ثم اختيار أي من المدن المتبقية بأي ترتيب:

رسم بياني قريبا

رسم بياني قريبا

في الرسم البياني مع ${tsn1} مدينة ، يجب أن تحتوي كل دورة هاميلتونية أيضًا على ${tsn1} مدينة. الآن،

    هذا يعني أنه يوجد إجمالي ${tsnPaths(tsn1)} مسارًا ممكنًا. الاختصار لهذا المنتج هو ${tsn1}! أو ${tsn1} عاملي.

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

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

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

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

    حاول إعادة ترتيب المدن على هذه الخريطة ، وشاهد كيف يتغير أقصر مسار بينهما. يمكنك إزالة المدن من خلال النقر عليها ، ويمكنك إضافة مدن عن طريق النقر في أي مكان على الخريطة (حتى 8):

    خوارزمية الجشع (أو خوارزمية الجوار الأقرب) بسيطة للغاية: تبدأ في مدينة عشوائية وتنتقل إلى أقرب مدينة لم تقم بزيارتها على التوالي. بمجرد زيارتك لجميع المدن ، تتوقف.

    الرسوم المتحركة قريبًا

    يمكنك أن تُظهر ، في المتوسط ، أن المسارات التي تم العثور عليها باستخدام خوارزمية الجشع أطول بنسبة 25% من أقصر مسار ممكن.

    تبدأ خوارزمية 2-Opt بمسار عشوائي عشوائي. ثم تقوم باختيار حافتين بشكل متكرر وتبديلهما حولهما إذا كان ذلك سيقلل من طول المسار. تتوقف عندما لا يمكنك تقليل الطول أكثر من خلال تبديل أي أزواج من الحواف.

    الرسوم المتحركة قريبًا

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

    يرغب النمل في العثور على أقصر الطرق الممكنة بين العش ومصادر الطعام الممكنة. يمكنهم التواصل مع بعضهم البعض من خلال المواد الكيميائية التي يتركونها على طول طريقهم ، والتي يمكن أن يتبعها النمل الآخر.

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

    رسم تخطيطي قريبًا

    تحاول خوارزميات نظام Ant Colony System (ACS) تكرار هذا السلوك على أجهزة الكمبيوتر ، وذلك باستخدام العديد من النمل "الافتراضي". يمكنهم العثور بسرعة على حلول جيدة جدًا لمشكلة البائع المتجول.

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

    مشكلة البائع المتجول هي NP-hard ، مما يعني أنه من الصعب جدًا حلها بواسطة أجهزة الكمبيوتر (على الأقل بالنسبة لعدد كبير من المدن).

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

    سيؤدي إيجاد خوارزمية سريعة لحل مشكلة البائع المتجول إلى حل إحدى أشهر المشكلات المفتوحة في الرياضيات وعلوم الكمبيوتر ، وهي مشكلة P vs NP. إنها واحدة من مشاكل جائزة الألفية السبع ، تحمل كل منها جائزة 1 مليون دولار.

    Archie