ترغب بنشر مسار تعليمي؟ اضغط هنا

مسألة الحقيبة - البرمجة الديناميكية ومسائل الأمثلة

Optimization Problem - knapsack

2295   2   53   0 ( 0 )
 نشر من قبل جامعة تشرين محاضرة
 تاريخ النشر 2016
  مجال البحث الهندسة المعلوماتية
والبحث باللغة العربية
 تمت اﻹضافة من قبل Zein Shaheen




اسأل ChatGPT حول البحث

ﻻ يوجد ملخص باللغة العربية


ملخص البحث
تتناول الورقة البحثية مشكلة حقيبة الظهر (Knapsack Problem) وهي إحدى مسائل تحسين الموارد في نظرية التعقيد. تتضمن المشكلة وجود n عنصرًا في متجر، ولكل عنصر وزن wi وقيمة vi. يمكن للسارق حمل وزن أقصى قدره C في حقيبة الظهر. في النسخة المقدمة من المشكلة، يمكن تقسيم العناصر إلى قطع أصغر، بحيث يمكن للسارق أن يقرر حمل جزء xi من العنصر i، حيث 0 ≤ xi ≤ 1. تساهم العناصر xiwi في الوزن الإجمالي في حقيبة الظهر وxivi في قيمة الحمولة. تقدم الورقة البحثية خوارزمية جشعة لحل المشكلة، حيث يتم ترتيب العناصر بترتيب تنازلي لقيمتها النسبية (Di = vi/wi) ومن ثم تعبئة حقيبة الظهر بالوحدات بدءًا من الأعلى قيمة. كما تتناول الورقة أيضًا الحل باستخدام البرمجة الديناميكية، حيث يتم بناء الحلول الجزئية من الحلول السابقة باستخدام صيغة تكرارية.
قراءة نقدية
دراسة نقدية: الورقة البحثية تقدم شرحًا جيدًا لمشكلة حقيبة الظهر وحلولها باستخدام الخوارزميات الجشعة والبرمجة الديناميكية. ومع ذلك، يمكن تحسين الورقة من خلال تقديم أمثلة تطبيقية أكثر تعقيدًا لتوضيح الفروق بين الحلول المختلفة. كما أن الورقة تفتقر إلى تحليل شامل للأداء الزمني والفضائي لكل خوارزمية، مما يجعل من الصعب على القارئ تقييم الفعالية النسبية لكل منها. بالإضافة إلى ذلك، يمكن تحسين الورقة من خلال تضمين مقارنة بين الحلول الجشعة والبرمجة الديناميكية من حيث الكفاءة والدقة.
أسئلة حول البحث
  1. ما هي مشكلة حقيبة الظهر؟

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

  2. ما هي الخوارزمية الجشعة لحل مشكلة حقيبة الظهر؟

    الخوارزمية الجشعة لحل مشكلة حقيبة الظهر تتضمن ترتيب العناصر بترتيب تنازلي لقيمتها النسبية (Di = vi/wi) ومن ثم تعبئة حقيبة الظهر بالوحدات بدءًا من الأعلى قيمة حتى الوصول إلى الحد الأقصى للوزن.

  3. ما هو الفرق بين الحل الجشع والبرمجة الديناميكية في مشكلة حقيبة الظهر؟

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

  4. ما هي الفوائد والعيوب لكل من الخوارزمية الجشعة والبرمجة الديناميكية؟

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


المراجع المستخدمة
ﻻ يوجد مراجع
قيم البحث

اقرأ أيضاً

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

الأسئلة المقترحة

التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا