القوة الغاشمة مقابل البرمجة الديناميكية: الفرق والمقارنة

هناك الكثير من المشاكل التي تظهر في حياتنا اليومية. وبالمثل ، هناك الكثير من المشاكل في مجال البرمجة.

هناك الكثير من الطرق لحل مشكلة معينة تتعلق بالخوارزميات والبرمجة. كل من القوة الغاشمة والبرمجة الديناميكية هما نوعان من التقنيات لحل مشكلة وإيجاد حل.

الوجبات السريعة الرئيسية

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

القوة الغاشمة مقابل البرمجة الديناميكية

الفرق بين القوة الغاشمة والبرمجة الديناميكية هي الكفاءة. كلتا التقنيتين لهما كفاءتهما. ال القوة الغاشمة تتكرر الطريقة على مجموعة البيانات المحددة عدة مرات مما يؤدي إلى ضعف الكفاءة ، بينما تتكرر طريقة البرمجة الديناميكية على مجموعة البيانات مرة واحدة فقط وبالتالي تؤدي إلى كفاءة جيدة. لكن نعم ، كلا الطريقتين مفيدتان في مواقف مختلفة.

يجد نهج القوة الغاشمة جميع الحلول الممكنة المتعلقة بمشكلة معينة حتى تجد حلاً مرضيًا. إنها دائمًا أسهل طريقة لتنفيذ وضمان حل إذا كان موجودًا.

هذه الطبيعة لتقنية القوة الغاشمة تؤدي إلى إبطاء عملها. نهج القوة الغاشمة هو دائمًا أبسط طريقة للحصول على حل.

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

جدول المقارنة

معلمات المقارنة	القوة الغاشمة	البرمجة الديناميكية
آلية العمل	يجد كل الحلول الممكنة لمشكلة معينة.	تجد فقط حلاً أمثلًا واحدًا.
تعقيد الوقت	O (mn) ، حيث m هو عدد الحرف المطلوب إيجاده و n هو حجم الإدخال.	O (n) ، حيث n هو عدد المشاكل الفرعية الفريدة
مثال	اختيار نوع	فلويد وارشيل
التكرارات	عدد التكرارات أكثر	عدد التكرارات أقل
الكفاءة	أقل كفاءة	أكثر فعالية

ما هي القوة الغاشمة؟

في مجال ال علوم الكمبيوتر، القوة الغاشمة هي تقنية شائعة لإيجاد حل. تضمن طريقة القوة الغاشمة حلاً لمشكلة معينة ، ولكنها تستغرق الكثير من الوقت للتشغيل وهي غير فعالة.

يبدأ بتعداد جميع الحالات بشكل منهجي والتحقق مما إذا كانت تستوفي الشرط أم لا.

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

هذا هو سبب تسميته مضيعة للوقت.

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

العيب الرئيسي للقوة الغاشمة لحل مشاكل العالم الحقيقي هو أنها تزيد من عدد الحالات التي يجب فحصها. على سبيل المثال ، إذا أردنا إيجاد مقسوم على رقم ، ولنفترض أن القاسم عليه هو 16 ، فإن القوة الغاشمة ستجري حسابات 10 ^ 15 لإيجاد الحل.

ما هي البرمجة الديناميكية؟

البرمجة الديناميكية هي طريقة محسّنة لحل المشاكل الرياضية وكذلك علوم الكمبيوتر. تم تطويره من قبل ريتشارد بيلمان في الخمسينيات من القرن الماضي.

اليوم لديها تطبيقات في مختلف المجالات بسبب قدرتها على التحسين.

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

النقطة الأساسية هي أنه في حالة حدوث حرف فرعي "أ" 4 مرات في مشكلة معقدة ، فإن البرمجة الديناميكية ستحلها مرة واحدة فقط ، في حين أن التكرار سيحلها 4 مرات.

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

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

تعني البنية التحتية المثلى أن حل مشكلة التحسين يتم الحصول عليه من خلال الجمع بين الحل الأمثل لجميع المشاكل الفرعية. المشاكل الفرعية المتداخلة تعني أن مساحة المشاكل الفرعية يجب أن تكون صغيرة.

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

الاختلافات الرئيسية بين القوة الغاشمة والبرمجة الديناميكية

1. نهج القوة الغاشمة يحل المشكلة عن طريق التكرار على مجموعة البيانات عددًا كبيرًا من المرات. في حين أن البرمجة الديناميكية تتكرر مرة واحدة فقط وتعطي الحل الأمثل.
2. الحل الذي تقدمه Brute Force ليس مضمونًا ليكون هو الأمثل لأنه يوفر جميع الحلول الممكنة. في حين أن الحل الذي توفره البرمجة الديناميكية سيكون دائمًا هو الأمثل.
3. تحل طريقة القوة الغاشمة من خلال النظر في جميع مجموعة البيانات في وقت واحد ، بينما تحل البرمجة الديناميكية مشكلة عن طريق تقسيم المشكلة المحددة إلى عدة مشاكل فرعية.
4. لا يستخدم نهج القوة الغاشمة مفهوم البنية التحتية المثلى والمشكلات الفرعية المتداخلة. تستخدم البرمجة الديناميكية هذه المفاهيم.
5. طريقة القوة الغاشمة ليست مثالية وفعالة. يحل نفس الحساب عدة مرات ، في حين أن برمجة Dynamin هي الأمثل والفعالة لأنها تحل حسابًا واحدًا فقط مرة واحدة وتستخدم الحفظ.

مراجع حسابات

1. https://www.science.org/doi/abs/10.1126/science.153.3731.34
2. https://dl.acm.org/doi/fullHtml/10.1145/3107239

آخر تحديث: 14 يوليو 2023