الفرق بين المراجعتين لصفحة: «Algorithms/Brute force»
لا ملخص تعديل |
لا ملخص تعديل |
||
| سطر 4: | سطر 4: | ||
وتعدّ خوارزمية التاجر الرحالة Traveling salesman (TSP) أحدّ الأمثلة التقليدية عن هذا الأسلوب. فلو فرضنا أنّ تاجرًا يريد زيارة 10 مدن في دولة ما، فكيف يمكن تحديد ترتيب هذه المدن بشرط أن يقطع التاجر أقصر مسافة ممكنة مرورًا بجميع المدن؟ لو اعتمدنا أسلوب القوة الغاشمة في حلّ هذا المسألة فسنحسب المسافة الكلية لجميع الطرق الممكنة ثم اختيار الطريق الأقصر؛ ولكنّ هذا الأسلوب غير فعالٍ على الإطلاق، إذ يمكن تجنّب العديد من المسارات المحتملة باستخدام بعض الخوارزميات الذكية. | وتعدّ خوارزمية التاجر الرحالة Traveling salesman (TSP) أحدّ الأمثلة التقليدية عن هذا الأسلوب. فلو فرضنا أنّ تاجرًا يريد زيارة 10 مدن في دولة ما، فكيف يمكن تحديد ترتيب هذه المدن بشرط أن يقطع التاجر أقصر مسافة ممكنة مرورًا بجميع المدن؟ لو اعتمدنا أسلوب القوة الغاشمة في حلّ هذا المسألة فسنحسب المسافة الكلية لجميع الطرق الممكنة ثم اختيار الطريق الأقصر؛ ولكنّ هذا الأسلوب غير فعالٍ على الإطلاق، إذ يمكن تجنّب العديد من المسارات المحتملة باستخدام بعض الخوارزميات الذكية. | ||
كذلك الأمر بالنسبة إلى مسألة إيجاد كلمة مرور مؤلفة من 5 أرقام، ففي أسوأ الحالات سيتطلب إيجاد كلمة المرور | كذلك الأمر بالنسبة إلى مسألة إيجاد كلمة مرور مؤلفة من 5 أرقام، ففي أسوأ الحالات سيتطلب إيجاد كلمة المرور تنفيذ 10<sup>5</sup> محاولة. | ||
يبلغ التعقيد الزمني لأسلوب القوة الغاشمة المقدار <code>O(n*m)</code>، وذلك لأنّنا لو أردنا مثلًا البحث في سلسلة نصية ذات <code>n</code> من الحروف في سلسلة نصية أخرى ذات <code>m</code> من الحروف فإنّ عدد المحاولات التي ستُجرى باستخدام أسلوب القوة الغاشمة سيبلغ <code>n*m</code> محاولة. | يبلغ التعقيد الزمني لأسلوب القوة الغاشمة المقدار <code>O(n*m)</code>، وذلك لأنّنا لو أردنا مثلًا البحث في سلسلة نصية ذات <code>n</code> من الحروف في سلسلة نصية أخرى ذات <code>m</code> من الحروف فإنّ عدد المحاولات التي ستُجرى باستخدام أسلوب القوة الغاشمة سيبلغ <code>n*m</code> محاولة. | ||
المراجعة الحالية بتاريخ 08:12، 21 ديسمبر 2019
يشير مصطلح (القوة الغاشمة Brute Force) إلى الأسلوب المتّبع في كتابة الخوارزميات والذي لا يتضمّن أي وسيلة لتحسين أداء تلك الخوارزمية، ولكنّه يعتمد اعتمادًا كاملًا على القوة الحوسبة لتجربة جميع الاحتمالات الممكنة إلى حين الوصول إلى الحل المنشود.
وتعدّ خوارزمية التاجر الرحالة Traveling salesman (TSP) أحدّ الأمثلة التقليدية عن هذا الأسلوب. فلو فرضنا أنّ تاجرًا يريد زيارة 10 مدن في دولة ما، فكيف يمكن تحديد ترتيب هذه المدن بشرط أن يقطع التاجر أقصر مسافة ممكنة مرورًا بجميع المدن؟ لو اعتمدنا أسلوب القوة الغاشمة في حلّ هذا المسألة فسنحسب المسافة الكلية لجميع الطرق الممكنة ثم اختيار الطريق الأقصر؛ ولكنّ هذا الأسلوب غير فعالٍ على الإطلاق، إذ يمكن تجنّب العديد من المسارات المحتملة باستخدام بعض الخوارزميات الذكية.
كذلك الأمر بالنسبة إلى مسألة إيجاد كلمة مرور مؤلفة من 5 أرقام، ففي أسوأ الحالات سيتطلب إيجاد كلمة المرور تنفيذ 105 محاولة.
يبلغ التعقيد الزمني لأسلوب القوة الغاشمة المقدار O(n*m)، وذلك لأنّنا لو أردنا مثلًا البحث في سلسلة نصية ذات n من الحروف في سلسلة نصية أخرى ذات m من الحروف فإنّ عدد المحاولات التي ستُجرى باستخدام أسلوب القوة الغاشمة سيبلغ n*m محاولة.
مصادر
- صفحة Brute Force Algorithms في توثيق الخوارزميات في موقع FreeCodeCamp.