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

حقيقة تبدو ورقة قيمه ...

ما رأيك لو أنك وضعت محتواها هنا في الموضوع؟

__Unknown كتب:

حقيقة تبدو ورقة قيمه ...

ما رأيك لو أنك وضعت محتواها هنا في الموضوع؟

لا يوجد مانع

ولكن التنسيق متعب قليلا

البرمجة الديناميكية (Dynamic Programming)

البرمجة الديناميكية (Dynamic Programming): هي تقنية من تقنيات البرمجة التي تستخدم لحل المشاكل عن طريق وذلك بجعل المشكلة الأساسية يؤول إلى حل مشاكل فرعية (Subproblem), ثم نحصل على حل المشكلة الأساسية عن طريق مراكمة حلول هذه المشاكل الفرعية. خلافا لتقنية (فرق تسد Divide & Conquer) التي تعمل بكفاءة عندما تكون المسائل الفرعية مستقلة عن بعضها (independent), فإننا نحتاج إلى البرمجة الديناميكية عندما تكون المشاكل الفرعية متداخلة (Overlapping Subproblem) ولا نستطيع فصلها عن بعضها.

ملاحظة :

1. إن كل المشاكل التي تستخدم البرمجة الديناميكية من اجل حلها هي مشاكل تحتوي على استدعاء ذاتي بطبيعتها (Recursive Definition). ومعروف أن الاستدعاء الذاتي يستخدم عادة لحل مشكلة اصغر من المشكلة الأساسية.

2. إن التداخل (Overlap) بين المشاكل الفرعية يتسبب في تنفيذ عدد من الحسابات أكثر من مرة, وهذا يرفع تعقيد الخوارزمية بشكل أسّي (Exponential Growth). ولتجنب هذا نلجأ إلى حفظ هذه الحلول (Memoization) داخل مصفوفة (كي لا نقوم بحسابها مرة اخرى) اي نضحي بالقليل من الذاكرة مقابل الكثير الوقت (Space Complexity vs Time Complexity).

3. تستخدم البرمجة الديناميكية لحل كثير من مشاكل الأمثلية (Optimization problems). ولكنها يمكن ان تستخدم لحل مشكلات أخرى .

4. يبدأ العمل بإيجاد حلول المشاكل البدائية ثم الصعود حتى نصل إلى المشكلة الأساسية.

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

تعليق تاريخي : ان كلمة برمجة ( Programming) الموجودة في العبارة (Dynamic Programming) لا تعني كتابة شفرة بل تعني تخطيط (Planning) وقد ظهر مصطلح (Dynamic Programming) في وقت كان فيه الكلمة Programming شائعة بين الاقتصاديين أكثر من أي تخصص آخر وكان الحاسوب حديث العهد آنذاك (1950) وكانت تستخدم بمعنى Planning.

وضعت جزء من الموضوع هنا كي تعثر محركات البحث عليه

romanof كتب:

وضعت جزء من الموضوع هنا كي تعثر محركات البحث عليه

موضوع شيق وجذاب جدا

لقد بدات البحث فعلا

شكرا لك استاذنا romanof

لقد تشوقت فعلا لدراسة هذه التقنية

بارك الله فيك

من الجزء الذي وضعته شوقني الامر للمزيد

شكرا لك مقدما

MohamedIBrahim كتب:

من الجزء الذي وضعته شوقني الامر للمزيد

شكرا لك مقدما

لا شكر على واجب

وهنا ستجد شرحا لمشكلة حرامي الذهب Knapsack problem

هناك مشكلة مشهورة تعتمد في حلها على البرمجة الديناميكية وهي (Longest Common Subsequence).

وهي التي تستخدمها محركات البحث لتحديد اخطاءنا الاملائية.

ربما ساتحدث عنها في مشاركة قادمة

ولقد قمت انت يا صديقي MohamedIBrahim بذكر ذلك هنا

/index.php?showtopic=235619

Knapsack problem بالعربي.pdf

romanof كتب:

لا شكر على واجب

وهنا ستجد شرحا لمشكلة حرامي الذهب Knapsack problem

هناك مشكلة مشهورة تعتمد في حلها على البرمجة الديناميكية وهي (Longest Common Subsequence).

وهي التي تستخدمها محركات البحث لتحديد اخطاءنا الاملائية.

ربما ساتحدث عنها في مشاركة قادمة

ولقد قمت انت يا صديقي MohamedIBrahim بذكر ذلك هنا

/index.php?showtopic=235619

تعجبني افكارك وطريقة كتابتك واتمني ان تفيدنا ببعض مما لديك

بالمناسبة لماذا هذا الموضوع اخترت ان يكون نوعه سؤال :lol:

اقتباس

بالمناسبة لماذا هذا الموضوع اخترت ان يكون نوعه سؤال

لم اختر سؤالا لكني اخترت اقرب شيء مخالف للاستفتاء او الاستطلاع

ومشي الموضوع فقط

romanof كتب:

لم اختر سؤالا لكني اخترت اقرب شيء مخالف للاستفتاء او الاستطلاع

ومشي الموضوع فقط

علي الاقل كان النوع يمكن ان يكون رابط او مقال

تعجبني المواضيع المتعوب عليها :lol:

اول شي في الورقه في F0=0 وفي الكود if n==0 then return 1

بخصوص مشكلة Knapsack اتذكر انني حليتها ب Branch and Bound اي انها Optimization problem

هل حلك هنا مختلف؟ اذا نعم مالافضل ولماذا؟

لاتحرمنا من مشاركاتك ياعادل

هذا من ذوقك

سؤالك على انها أمثلية (Optimization ) ام لا..

ان الذي يجعل المشكلة امثلية (Optimization ) او غير امثلية هو طبيعة المسالة (البحث عن اكبر مكسب او اقل خسارة) ولا تؤثر طريقة الحل في ذلك

لذلك فهي مسالة امثلية لاني ابحث عن اكبر مكسب داخل حقيبة حجمها ثابت

اقتباس

F0=0 وفي الكود if n==0 then return 1

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

و لا اعرف طريقة BB فلا استطيع الحكم ولكن

كي تعرف ايهما افضل يجب ان تحسب التعقيد الزمني(Time Complexity) للطريقتين وبعد ذلك الطريقة ذات الزمن الاقل هي الافضل

بالنسبة لحل المشكل بالبرمجة الديناميكية فالحل يأخذ زمنا مقداه (VN) حيث V حجم الحقيبة N عدد القطع المسروقة