البرمجة الديناميكية
دراسة شاملة لمفاهيم البرمجة الديناميكية وتطبيقاتها في تصميم وتحليل الخوارزميات، بما في ذلك مسألة حقيبة الظهر، خوارزمية وارشال، خوارزمية فلويد، وأشجار البحث الثنائية المثلى.
Dynamic Programming
A comprehensive study of Dynamic Programming concepts and applications in algorithm design and analysis, including the Knapsack Problem, Warshall's algorithm, Floyd's algorithm, and Optimal Binary Search Trees.
أهداف التعلم
- وصف البرمجة الديناميكية واستخداماتها.
- التعبير عن مسألة حقيبة الظهر ودوال الذاكرة.
- شرح أشجار البحث الثنائية المثلى.
- Describe Dynamic Programming and its usage.
- Express the Knapsack Problem and Memory Functions.
- Explain Optimal Binary Search Trees.
1 أساسيات البرمجة الديناميكية
1 Dynamic Programming Fundamentals
تقنية لتصميم الخوارزميات تعتمد على تقسيم المسألة إلى مشاكل فرعية متداخلة وحلها من الأسفل للأعلى. تخيل أنك تبني جداراً وتحتفظ بكل قالب جاهز بدلاً من إعادة صنعه.
An algorithm design technique based on dividing a problem into overlapping subproblems and solving them bottom-up. Imagine building a wall and keeping every ready-made brick instead of remaking it.
البرمجة الديناميكية (Dynamic Programming) هي تقنية عامة لتصميم الخوارزميات تُستخدم لحل المسائل التي يمكن تعريفها بعلاقات تكرارية (recurrences) مع وجود مشاكل فرعية متداخلة (overlapping subproblems).
تم اختراعها بواسطة عالم الرياضيات الأمريكي ريتشارد بيلمان في الخمسينيات.
الفكرة الأساسية هي إعداد علاقة تكرارية تربط حل المسألة الأكبر بحلول المسائل الأصغر، ثم حل المسائل الأصغر مرة واحدة فقط وتسجيل حلولها في جدول (Bottom-up fashion)، واستخراج الحل النهائي من هذا الجدول.
Dynamic Programming is a general algorithm design technique for solving problems defined by recurrences with overlapping subproblems.
Invented by American mathematician Richard Bellman in the 1950s.
The main idea is to set up a recurrence relating a solution to a larger instance to solutions of some smaller instances, solve smaller instances once, record solutions in a table, and extract the solution to the initial instance from that table.
تعتمد البرمجة الديناميكية على ثلاثة قواعد أساسية:
- مبدأ الأمثلية لبيلمان (Bellman's principle of optimality) والذي ينص على أن الحل الأمثل لأي مسألة يتكون من حلول أمثلة لمشاكلها الفرعية.
- وجود مشاكل فرعية متداخلة.
- الحساب يتم بطريقة من الأسفل إلى الأعلى (Bottom-up).
تختلف هذه التقنية عن 'فرق تسد' (Divide and Conquer) في أن الأخيرة تتعامل مع مشاكل فرعية مستقلة، بينما البرمجة الديناميكية تتعامل مع مشاكل متداخلة لتجنب الحساب المتكرر.
Dynamic programming relies on three rules:
- Bellman's principle of optimality states that an optimal solution to any instance of an optimization problem is composed of optimal solutions to its sub-instances.
- Problems have overlapping subproblems.
- Computes in a bottom-up fashion.
It differs from Divide and Conquer because D&C subproblems are independent, whereas DP subproblems overlap, making memoization or tabulation necessary to avoid redundant computations.
| Dynamic Programming | Divide and Conquer | |
|---|---|---|
| طبيعة المشاكل الفرعيةNature of Subproblems | متداخلة (Overlapping)Overlapping | مستقلة (Independent)Independent |
| اتجاه الحلDirection of Solution | من الأسفل للأعلى (Bottom-up)Bottom-up | من الأعلى للأسفل (Top-down)Top-down |
لماذا لا نستخدم تقنية 'فرق تسد' لحساب أرقام فيبوناتشي؟ Why don't we use the 'Divide and Conquer' technique to compute Fibonacci numbers?
لأن المشاكل الفرعية في فيبوناتشي غير مستقلة (متداخلة). استخدام 'فرق تسد' سيؤدي إلى إعادة حساب نفس القيم مراراً وتكراراً، مما يجعل التعقيد الزمني أسّياً، بينما البرمجة الديناميكية تحلها في وقت خطي.
Because the subproblems in Fibonacci are not independent (they overlap). Using Divide and Conquer would lead to recalculating the same values repeatedly, resulting in exponential time complexity, whereas DP solves it in linear time.
2 مسألة حقيبة الظهر باستخدام البرمجة الديناميكية
2 The Knapsack Problem using DP
إيجاد المجموعة الفرعية الأكثر قيمة من العناصر التي يمكن وضعها في حقيبة ذات سعة محدودة. مثل لص يحاول سرقة أثمن الأشياء دون تمزيق حقيبته.
Finding the most valuable subset of items that fit into a knapsack of limited capacity. Like a thief trying to steal the most valuable items without breaking their bag.
في مسألة حقيبة الظهر (Knapsack Problem)، يُعطى عدد n من العناصر، لكل عنصر وزن صحيح w وقيمة v، وحقيبة بسعة صحيحة W.
الهدف هو إيجاد المجموعة الفرعية الأكثر قيمة التي تتسع في الحقيبة.
باستخدام البرمجة الديناميكية، نعرّف F[i, j] كأقصى قيمة يمكن الحصول عليها باستخدام أول i عناصر وسعة j.
يتم بناء جدول حيث يتم ملؤه صفاً بصف أو عموداً بعمود.
In the Knapsack Problem, given n items with integer weights w and values v, and a knapsack of integer capacity W, the goal is to find the most valuable subset of items that fit into the knapsack.
Using DP, we define F[i, j] as the optimal value of an instance defined by the first i items and capacity j.
A table is constructed and filled either row by row or column by column.
العلاقة التكرارية هي: إذا كان وزن العنصر الحالي أكبر من السعة المتاحة (j < w_i)، فإن القيمة هي نفس القيمة بدون هذا العنصر F(i-1, j).
أما إذا كان يتسع، فنأخذ القيمة القصوى بين عدم تضمين العنصر F(i-1, j) وتضمينه v_i + F(i-1, j-w_i).
الشروط الابتدائية هي F(0, j) = 0 و F(i, 0) = 0.
The recurrence relation is: if the current item's weight is greater than the available capacity (j < w_i), the value is F(i-1, j).
If it fits, we take the maximum of not including the item F(i-1, j) and including it v_i + F(i-1, j-w_i).
Initial conditions are F(0, j) = 0 for j >= 0 and F(i, 0) = 0 for i >= 0.
ماذا يحدث إذا كانت أوزان العناصر أرقاماً كسرية (غير صحيحة)؟ What happens if the item weights are fractional (non-integer) numbers?
لا يمكن استخدام البرمجة الديناميكية المعتمدة على مصفوفة ثنائية الأبعاد بشكل مباشر لأن الفهارس (السعة j) يجب أن تكون أعداداً صحيحة. سيتطلب الأمر تقنيات أخرى أو تحويل الأوزان إلى أعداد صحيحة بالضرب في معامل.
The standard 2D array DP approach cannot be used directly because array indices (capacity j) must be integers. It would require other techniques or scaling the weights to integers by multiplying by a factor.
3 خوارزمية وارشال (الانغلاق المتعدي)
3 Warshall’s Algorithm (Transitive Closure)
خوارزمية لمعرفة ما إذا كان هناك أي مسار بين كل زوج من العقد في رسم بياني موجه. مثل معرفة ما إذا كان يمكنك الطيران من مدينة إلى أخرى، حتى لو تطلب الأمر عدة محطات توقف.
An algorithm to determine if there is any path between every pair of vertices in a directed graph. Like knowing if you can fly from one city to another, even if it requires multiple layovers.
تقوم خوارزمية وارشال بحساب الانغلاق المتعدي (Transitive Closure) لعلاقة، وهو ما يعادل إيجاد جميع المسارات غير التافهة في رسم بياني موجه (Digraph).
تبني الخوارزمية الحل من خلال سلسلة من المصفوفات R(0), ..., R(n).
المصفوفة R(k)[i,j] تكون 1 إذا وفقط إذا كان هناك مسار من العقدة i إلى العقدة j باستخدام العقد من 1 إلى k فقط كعقد وسيطة.
Warshall's algorithm computes the transitive closure of a relation, which is equivalent to finding the existence of all nontrivial paths in a digraph.
The algorithm constructs the solution through a sequence of matrices R(0), ..., R(n).
The matrix element R(k)[i,j] = 1 if and only if there is a nontrivial path from i to j with only the first k vertices allowed as intermediate.
القاعدة التكرارية: R(k)[i,j] = R(k-1)[i,j] أو (R(k-1)[i,k] و R(k-1)[k,j]).
هذا يعني أن المسار موجود إما لأنه كان موجوداً بدون استخدام العقدة k، أو يوجد مسار من i إلى k ومن k إلى j.
الكفاءة الزمنية هي Θ(n^3)، وكفاءة المساحة ممتازة حيث يمكن كتابة المصفوفات فوق سابقاتها.
The recurrence rule: R(k)[i,j] = R(k-1)[i,j] OR (R(k-1)[i,k] AND R(k-1)[k,j]).
This means a path exists either because it existed without using vertex k, or there is a path from i to k and from k to j.
Time efficiency is Θ(n^3), and space efficiency is optimal as matrices can be written over their predecessors.
لماذا تعتبر خوارزمية وارشال أفضل من تشغيل خوارزمية البحث في العمق (DFS) من كل عقدة؟ Why is Warshall's algorithm considered better than running DFS from every vertex?
رغم أن كلاهما قد يمتلك تعقيداً زمنياً متقارباً للرسوم البيانية الكثيفة، إلا أن خوارزمية وارشال تعتمد على عمليات منطقية بسيطة (AND/OR) وحلقات متداخلة بسيطة، مما يجعلها سريعة جداً في التنفيذ الفعلي (Low constant factors) وسهلة البرمجة.
Although both might have similar time complexities for dense graphs, Warshall's algorithm relies on simple bitwise logical operations (AND/OR) and tight nested loops, making it extremely fast in practice (low constant factors) and easy to implement.
4 خوارزمية فلويد (أقصر المسارات)
4 Floyd’s Algorithm (All-pairs shortest paths)
خوارزمية لإيجاد أقصر مسافة بين كل زوج من العقد في رسم بياني موزون. تشبه تطبيق خرائط جوجل الذي يحسب أسرع طريق بين أي مدينتين.
An algorithm to find the shortest path between every pair of vertices in a weighted graph. Like a Google Maps app calculating the fastest route between any two cities.
تحل خوارزمية فلويد مسألة أقصر المسارات بين جميع الأزواج (All-pairs shortest paths) في رسم بياني موزون (بدون دورات ذات وزن سالب).
تستخدم نفس فكرة وارشال: بناء الحل عبر سلسلة من المصفوفات D(0), ..., D(n) باستخدام مجموعات متزايدة من العقد المسموح بها كعقد وسيطة.
Floyd's algorithm solves the all-pairs shortest paths problem in a weighted (di)graph (with no negative-length cycle).
It uses the same idea as Warshall's: constructing the solution through a series of matrices D(0), ..., D(n) using increasing subsets of the vertices allowed as intermediate.
في التكرار k، تحدد الخوارزمية أقصر المسارات التي تستخدم فقط العقد من 1 إلى k كعقد وسيطة.
العلاقة التكرارية هي: D(k)[i,j] = min(D(k-1)[i,j], D(k-1)[i,k] + D(k-1)[k,j]).
الكفاءة الزمنية هي Θ(n^3).
يمكن أيضاً إيجاد المسارات نفسها وليس فقط أطوالها عن طريق مصفوفة إضافية لتتبع العقد.
On the k-th iteration, the algorithm determines shortest paths that use only vertices among 1,...,k as intermediate.
The recurrence is: D(k)[i,j] = min(D(k-1)[i,j], D(k-1)[i,k] + D(k-1)[k,j]).
Time efficiency is Θ(n^3).
The shortest paths themselves can also be found by keeping an additional predecessor matrix.
| Warshall's Algorithm | Floyd's Algorithm | |
|---|---|---|
| الهدف الأساسيPrimary Goal | الانغلاق المتعدي (وجود مسار)Transitive Closure (Path existence) | أقصر المسارات بين جميع الأزواجAll-pairs shortest paths |
| العمليات المستخدمةOperations Used | منطقية (AND / OR)Logical (AND / OR) | حسابية (Min / +)Arithmetic (Min / +) |
لماذا تفشل خوارزمية فلويد إذا كان هناك دورة ذات وزن سالب في الرسم البياني؟ Why does Floyd's algorithm fail if there is a negative-weight cycle in the graph?
لأنه في وجود دورة سالبة، يمكن تقليل طول المسار إلى ما لا نهاية بالدوران حول تلك الدورة مراراً وتكراراً، مما يجعل مفهوم 'أقصر مسار' غير معرّف رياضياً.
Because with a negative cycle, the path length can be decreased infinitely by looping through the cycle over and over, making the concept of a 'shortest path' mathematically undefined.
5 أشجار البحث الثنائية المثلى (OBST)
5 Optimal Binary Search Trees (OBST)
بناء شجرة بحث ثنائية بحيث تكون العناصر الأكثر بحثاً قريبة من الجذر، لتقليل متوسط وقت البحث. مثل ترتيب تطبيقات هاتفك بحيث تكون التطبيقات الأكثر استخداماً في الصفحة الأولى.
Constructing a BST so that the most frequently searched items are near the root, minimizing average search time. Like arranging your phone apps so the most used ones are on the first page.
أحد التطبيقات الرئيسية لـ OBST هو تنفيذ قاموس (Dictionary).
المشكلة: بالنظر إلى n مفاتيح مرتبة واحتمالات البحث عنها، أوجد شجرة بحث ثنائية (BST) بمتوسط عدد مقارنات أدنى في البحث الناجح.
نظراً لأن عدد الأشجار الممكنة ينمو بشكل أسي (أرقام كاتالان)، فإن القوة الغاشمة غير فعالة.
نستخدم البرمجة الديناميكية لحلها.
One of its principal applications is to implement a dictionary.
Problem: Given n sorted keys and probabilities of searching for them, find a BST with a minimum average number of comparisons in a successful search.
Since the total number of BSTs with n nodes grows exponentially (Catalan numbers), brute force is not efficient.
We use DP to solve it.
نعرّف C[i,j] كمتوسط عدد المقارنات الأدنى للأشجار التي تحتوي على المفاتيح من i إلى j.
يتم حسابها بتجربة كل مفتاح k كجذر، وجمع تكلفة الشجرة الفرعية اليسرى C[i, k-1]، واليمنى C[k+1, j]، ومجموع احتمالات كل المفاتيح في هذه الشجرة الفرعية (لأن كل عقدة تنزل مستوى واحداً).
الكفاءة الزمنية الأساسية هي Θ(n^3) ولكن يمكن تقليلها إلى Θ(n^2) بالاستفادة من رتابة المدخلات في جدول الجذور.
كفاءة المساحة هي Θ(n^2).
Let C[i,j] be the minimum average number of comparisons for keys i to j.
It is computed by trying every key k as the root, summing the cost of the left subtree C[i, k-1], the right subtree C[k+1, j], and the sum of probabilities of all keys in this subtree (since every node goes down one level).
Time efficiency is Θ(n^3) but can be reduced to Θ(n^2) by taking advantage of the monotonicity of entries in the root table.
Space efficiency is Θ(n^2).
كيف يتم ملء الجداول في خوارزمية أشجار البحث الثنائية المثلى؟ How are the tables filled in the Optimal BST algorithm?
يتم ملء الجداول قطرياً (Diagonal by diagonal)، حيث نبدأ بالأشجار التي تحتوي على مفتاح واحد، ثم مفتاحين، وهكذا حتى نصل إلى الشجرة التي تحتوي على جميع المفاتيح n.
The tables are filled diagonal by diagonal, starting with trees containing a single key, then two keys, and so on until reaching the tree containing all n keys.