مثير للإعجاب

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

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


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

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

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

ذات صلة: تسمح الخوارزمية الجديدة للسيارات المستقلة بتغيير الحارات بشكل أكبر مثل البشر

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

مشكلة البائع المتجول ، التعقيد الزمني الأسي ، وما بعده

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

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

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

* 0 طيات: 1/250 بوصة سميكة.
* 10 طيات: ~ 2.05 بوصة سميكة.
* 25 طية: ~ 1 ميل سميكة.
* 43 طية: سطح القمر.
* 52 طية: داخل الشمس.
* 57 طية: تمرير ألتيما ثول
* 67 طية: يستغرق الضوء 1.5 سنة للسفر من طرف إلى آخر.
* 82 طية: بعرض مجرة ​​درب التبانة.
* 93 طية: ضمن مسافة القذف الفلكية للثقب الأسود الهائل في وسط ميسيه 87.
* 101 طية: لست متأكدًا مما هو موجود لأنه خارج الكون المرئي.

وهذا مع الأفضل خوارزمية لدينا الآن. كل واحدة من تلك "الأوراق" في تلك المجموعة هي طريق يمكن أن يسلكه البائع التي سنحتاج في النهاية إلى فحصها وقياسها مقابل جميع أطوال المسارات الأخرى وكل طية تعادل إضافة مدينة واحدة إضافية إلى قائمة المدن التي يحتاج إلى زيارتها. إذا أخفقنا للتو في محاولة حل مشكلة بائع متجول عن طريق التحقق من كل حل ممكن للعثور على أفضل حل ، فإننا نبحث في تعقيد مضروب الوقت. باستخدام 128 بت رقم من مثال تشفير RSA ، والذي كان 2128، في حين أن 101 طية هي 2 فقط101، 35! ضربات الماضي 2128 بمعامل 100 على الأقل. يزداد الأمر سوءًا مع كل زيادة إضافية في مدخلاتك ، وهذا ما يجعل مشكلة البائع المتجول مهمة جدًا ومثيرة للجنون أيضًا.

مشكلة خوارزميات التحسين

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

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

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

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

المقال السادس في سلسلتنا حول الخوارزميات والحساب ، ف مقابل. NP و NP-Complete وخوارزمية كل شيء، يمكن العثور عليها هنا.


شاهد الفيديو: P=NP مسألة بمليون دولار لمن يحلها وستطور الذكاء الاصطناعي بشكل رهيب (يوليو 2022).


تعليقات:

  1. Vujinn

    منحت ، عبارة مفيدة جدا

  2. Mikora

    الجدير بالذكر ، إنها المعلومات القيمة

  3. Glyn

    أوصي بالبحث على google.com

  4. Yozshugrel

    مرحبًا! شكرا على المشاعر الطيبة المقدمة ...



اكتب رسالة