الفرق بين المراجعتين لصفحة: «Algorithms/Divide And Conquer»
أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE:فرق تسد}}</noinclude> نموذج فرِّق تسُد هو من نماذج الخوارزميات الشائعة ويستند في عمل...' |
لا ملخص تعديل |
||
| (5 مراجعات متوسطة بواسطة نفس المستخدم غير معروضة) | |||
| سطر 1: | سطر 1: | ||
<noinclude>{{DISPLAYTITLE:فرق تسد}}</noinclude> | <noinclude>{{DISPLAYTITLE:فرق تسد}}</noinclude> | ||
أسلوب فرِّق تسُد هو من أساليب الخوارزميات الشائعة ويستند في عمله على [[Algorithms/Recursion|التعاود recursion]]. | |||
يقسِّم | يقسِّم أسلوب فرِّق تسد المسألة إلى مسائل فرعية تشبه المسألة الأصلية، ويقدّم حلولًا للمسائل الفرعية بطريقة تعاودية، ثم يدمج حلول المسائل الفرعية وذلك لتقديم حلٍّ للمسألة الأصلية. ولمّا كان أسلوب فرِّق تسد يعمل بطريقة تعاودية، فيلزم أن تكون كل مسألة فرعية أصغر من المسألة الأصلية، ويجب أن يكون هناك حالة أساس لجميع المسائل الفرعية. | ||
يمكن تقسيم طريقة عمل هذا | يمكن تقسيم طريقة عمل هذا الأسلوب إلى خطوات ثلاث: | ||
# تقسيم '''Divide''' المسألة إلى عدد من المسائل الفرعية التي تكون نسخًا أصغر من المسألة الأصلية. | # '''تقسيم''' '''Divide''' المسألة إلى عدد من المسائل الفرعية التي تكون نسخًا أصغر من المسألة الأصلية. | ||
# التغلب '''Conquer''' على المسائل الفرعية وذلك بحلّها بطريقة تعاودية، ويمكن حل المسائل الفرعية كحالات أساسية إن كانت صغيرة بما فيه الكفاية. | # '''التغلب''' '''Conquer''' على المسائل الفرعية وذلك بحلّها بطريقة تعاودية، ويمكن حل المسائل الفرعية كحالات أساسية إن كانت صغيرة بما فيه الكفاية. | ||
# دمج '''Combine''' حلول المسائل الفرعية لتشكيل الحل النهائي للمسألة الأصلية. | # '''دمج''' '''Combine''' حلول المسائل الفرعية لتشكيل الحل النهائي للمسألة الأصلية. | ||
== أسلوب فرّق تسد مقابل البرمجة الديناميكية == | |||
يقسّم كلا الأسلوبين (فرّق تسد و<nowiki/>[[Algorithms/Dynamic Programming|البرمجة الديناميكية]]) المسألة المعطاة إلى مسائل فرعية لتحلّها بعد ذلك. ولكن تستخدم منهجية فرّق تسد عندما لا تجري معالجة المسألة الفرعية نفسها مرات عديدة. أما في حال تكرار المسائل الفرعية فيجب حينئذ استخدام [[Algorithms/Dynamic Programming|البرمجة الديناميكية]] لحلّها. فعلى سبيل المثال لا تجري معالجة نفس المسائل الفرعية في خوارزمية [[Algorithms/binary search|البحث الثنائي]] بصورة متكررة؛ لذا تنتمي هذه الخوارزمية إلى منهج فرِّق تسد، أما خوارزمية [[Algorithms/Fibonacci numbers|متتالية فيبوناتشي]] فتعالج فيها نفس المسائل الفرعية عدة مرات؛ لذا يُفضل استخدام [[Algorithms/Dynamic Programming|البرمجة الديناميكية]] لحلّها. | |||
== [[Algorithms/binary search|البحث الثنائي]] == | |||
تقارن الخوارزمية في كل خطوة العنصر المدخل <code>x</code> مع قيمة العنصر الموجود في منتصف المصفوفة، وإن كانت القيمتان متطابقتين تعيد الخوارزمية موقع العنصر الموجود في منتصف المصفوفة، وإن لم تتطابق القيمتان وكانت قيمة <code>x</code> أقل من قيمة العنصر الموجود في منتصف المصفوفة، تعاود الخوارزمية العمل على الجانب الأيسر من العنصر المتوسط، وإن لم تتطابق القيم تنتقل إلى الجزء الأيمن من المصفوفة. | |||
== | == [[Algorithms/quick sort|الترتيب السريع]] == | ||
تختار الخوارزمية عنصرًا محوريًا، وتعيد ترتيب عناصر المصفوفة بطريقة تأخذ فيها العناصر التي تكون أصغر من العنصر المحوري الجانب الأيسر منه، والعناصر التي تكون أكبر من العنصر المحوري الجانب الأيمن. وترتب الخوارزمية في النهاية المصفوفات الفرعية بطريقة تعاودية على جانبي العنصر المحوري. | |||
تقسّم | == [[Algorithms/merge sort|الترتيب بالدمج]] == | ||
تقسّم الخوارزمية المصفوفة إلى نصفين وترتبهما تعاوديًا وتدمجمها النصفين المرتبين بعضهما ببعض. | |||
== | == [[Algorithms/closest pair of points|أقرب زوج من النقاط]] == | ||
تبحث الخوارزمية عن أقرب زوج من النقاط في مجموعة من النقاط التي تنتمي إلى السطح <code>x-y</code>. يمكن حل المسألة بتعقيد زمني قدره <code>O(n^2)</code> وذلك بحساب المسافات التي تفصل بين أزواج النقاط كلها ومقارنة المسافات لمعرفة المسافة الأقصر. يمكن تقليص التعقيد الزمني إلى المقدار <code>O(nLogn)</code> باستخدام أسلوب فرِّق تسد. | |||
== [[Algorithms/power x y|حساب ناتج رفع عدد إلى قوّة معينة]] == | |||
يمكن استخدام أسلوب فرِّق تسد في كتابة خوارزمية تحسب ناتج رفع عدد معين (ليكن <code>x</code>) إلى قوّة معينة (لتكن <code>y</code>)، مع افتراض أنّ قيمتي <code>x</code> و <code>y</code> صغيرتان نسبيًا ولن تتسببا في حدوث فيضان overflow. | |||
== [[Algorithms/median two equal sorted arrays|إيجاد الوسيط لمصفوفتين مرتبتين لهما الحجم نفسه]] == | |||
المطلوب في هذه الخوارزمية هو إيجاد الوسيط median للمصفوفة الناتجة عن دمج مصفوفتين مرتبتين ومتساويتين في الحجم. | |||
== [[Algorithms/longest common prefix|إيجاد البادئة المشتركة الطولى]] == | |||
تستخدم هذه الخوارزمية أسلوب فرق تسد في إيجاد البادئة المشتركة الطولى لمجموعة من السلاسل النصية. | |||
== [[Algorithms/floor sorted array|إيجاد أكبر عنصر في مصفوفة مرتبة يكون أصغر من العنصر المعطى]] == | |||
المطلوب في هذه المسألة هو إيجاد أكبر عنصر في مصفوفة مرتبة يكون أصغر من العنصر المعطى (ليكن <code>x</code>)، يسمّى هذا العنصر بأرضية العنصر <code>x</code>. | |||
== [[Algorithms/closest number|إيجاد أقرب عدد للعدد المعطى في مصفوفة مرتبة]] == | |||
المطلوب في هذه المسألة هو إيجاد أقرب عدد للعدد المعطى في مصفوفة مرتبة من الأعداد الصحيحة التي قد تحتوي على أعداد مكررة أو ذات إشارة سالبة. | |||
== [[Algorithms/peak element|إيجاد ذروة المصفوفة]] == | |||
ذروة المصفوفة هي عنصر في المصفوفة يكون أكبر من العنصرين المحيطين به. | |||
== [[Algorithms/majority element|إيجاد العنصر الغالب في مصفوفة مرتبة]] == | |||
العنصر الغالب Majority Element هو العنصر الذي يظهر أكثر من <code>n/2</code> مرة في مصفوفة مرتبة تحتوي على <code>n</code> من الأعداد الصحيحة. | |||
== [[Algorithms/repeating element|إيجاد العنصر المكرّر في المصفوفة]] == | |||
المطلوب في هذه المسألة هو إيجاد العنصر المكرّر في مصفوفة تحتوي على مجموعة من العناصر المرتّبة، ويتكرّر فيها عنصر واحد فقط. | |||
== [[Algorithms/local minima|إيجاد الصغرى المحلية في مصفوفة]] == | |||
تعرف الصغرى المحلية Local minima بأنّها النقطة التي تكون أصغر من النقطتين المجاورتين لها أو مساوية لهما. | |||
== مصادر == | == مصادر == | ||
* صفحة [https://www.geeksforgeeks.org/divide-and-conquer/ Divide and Conquer] في توثيق الخوارزميات في موقع GeeksforGeeks. | * صفحة [https://www.geeksforgeeks.org/divide-and-conquer/ Divide and Conquer] في توثيق الخوارزميات في موقع GeeksforGeeks. | ||
[[تصنيف: الخوارزميات]] | [[تصنيف: الخوارزميات]] | ||
[[تصنيف: فرق تسد]] | [[تصنيف: فرق تسد]] | ||
المراجعة الحالية بتاريخ 18:59، 24 ديسمبر 2019
أسلوب فرِّق تسُد هو من أساليب الخوارزميات الشائعة ويستند في عمله على التعاود recursion.
يقسِّم أسلوب فرِّق تسد المسألة إلى مسائل فرعية تشبه المسألة الأصلية، ويقدّم حلولًا للمسائل الفرعية بطريقة تعاودية، ثم يدمج حلول المسائل الفرعية وذلك لتقديم حلٍّ للمسألة الأصلية. ولمّا كان أسلوب فرِّق تسد يعمل بطريقة تعاودية، فيلزم أن تكون كل مسألة فرعية أصغر من المسألة الأصلية، ويجب أن يكون هناك حالة أساس لجميع المسائل الفرعية.
يمكن تقسيم طريقة عمل هذا الأسلوب إلى خطوات ثلاث:
- تقسيم Divide المسألة إلى عدد من المسائل الفرعية التي تكون نسخًا أصغر من المسألة الأصلية.
- التغلب Conquer على المسائل الفرعية وذلك بحلّها بطريقة تعاودية، ويمكن حل المسائل الفرعية كحالات أساسية إن كانت صغيرة بما فيه الكفاية.
- دمج Combine حلول المسائل الفرعية لتشكيل الحل النهائي للمسألة الأصلية.
أسلوب فرّق تسد مقابل البرمجة الديناميكية
يقسّم كلا الأسلوبين (فرّق تسد والبرمجة الديناميكية) المسألة المعطاة إلى مسائل فرعية لتحلّها بعد ذلك. ولكن تستخدم منهجية فرّق تسد عندما لا تجري معالجة المسألة الفرعية نفسها مرات عديدة. أما في حال تكرار المسائل الفرعية فيجب حينئذ استخدام البرمجة الديناميكية لحلّها. فعلى سبيل المثال لا تجري معالجة نفس المسائل الفرعية في خوارزمية البحث الثنائي بصورة متكررة؛ لذا تنتمي هذه الخوارزمية إلى منهج فرِّق تسد، أما خوارزمية متتالية فيبوناتشي فتعالج فيها نفس المسائل الفرعية عدة مرات؛ لذا يُفضل استخدام البرمجة الديناميكية لحلّها.
البحث الثنائي
تقارن الخوارزمية في كل خطوة العنصر المدخل x مع قيمة العنصر الموجود في منتصف المصفوفة، وإن كانت القيمتان متطابقتين تعيد الخوارزمية موقع العنصر الموجود في منتصف المصفوفة، وإن لم تتطابق القيمتان وكانت قيمة x أقل من قيمة العنصر الموجود في منتصف المصفوفة، تعاود الخوارزمية العمل على الجانب الأيسر من العنصر المتوسط، وإن لم تتطابق القيم تنتقل إلى الجزء الأيمن من المصفوفة.
الترتيب السريع
تختار الخوارزمية عنصرًا محوريًا، وتعيد ترتيب عناصر المصفوفة بطريقة تأخذ فيها العناصر التي تكون أصغر من العنصر المحوري الجانب الأيسر منه، والعناصر التي تكون أكبر من العنصر المحوري الجانب الأيمن. وترتب الخوارزمية في النهاية المصفوفات الفرعية بطريقة تعاودية على جانبي العنصر المحوري.
الترتيب بالدمج
تقسّم الخوارزمية المصفوفة إلى نصفين وترتبهما تعاوديًا وتدمجمها النصفين المرتبين بعضهما ببعض.
أقرب زوج من النقاط
تبحث الخوارزمية عن أقرب زوج من النقاط في مجموعة من النقاط التي تنتمي إلى السطح x-y. يمكن حل المسألة بتعقيد زمني قدره O(n^2) وذلك بحساب المسافات التي تفصل بين أزواج النقاط كلها ومقارنة المسافات لمعرفة المسافة الأقصر. يمكن تقليص التعقيد الزمني إلى المقدار O(nLogn) باستخدام أسلوب فرِّق تسد.
حساب ناتج رفع عدد إلى قوّة معينة
يمكن استخدام أسلوب فرِّق تسد في كتابة خوارزمية تحسب ناتج رفع عدد معين (ليكن x) إلى قوّة معينة (لتكن y)، مع افتراض أنّ قيمتي x و y صغيرتان نسبيًا ولن تتسببا في حدوث فيضان overflow.
إيجاد الوسيط لمصفوفتين مرتبتين لهما الحجم نفسه
المطلوب في هذه الخوارزمية هو إيجاد الوسيط median للمصفوفة الناتجة عن دمج مصفوفتين مرتبتين ومتساويتين في الحجم.
إيجاد البادئة المشتركة الطولى
تستخدم هذه الخوارزمية أسلوب فرق تسد في إيجاد البادئة المشتركة الطولى لمجموعة من السلاسل النصية.
إيجاد أكبر عنصر في مصفوفة مرتبة يكون أصغر من العنصر المعطى
المطلوب في هذه المسألة هو إيجاد أكبر عنصر في مصفوفة مرتبة يكون أصغر من العنصر المعطى (ليكن x)، يسمّى هذا العنصر بأرضية العنصر x.
إيجاد أقرب عدد للعدد المعطى في مصفوفة مرتبة
المطلوب في هذه المسألة هو إيجاد أقرب عدد للعدد المعطى في مصفوفة مرتبة من الأعداد الصحيحة التي قد تحتوي على أعداد مكررة أو ذات إشارة سالبة.
إيجاد ذروة المصفوفة
ذروة المصفوفة هي عنصر في المصفوفة يكون أكبر من العنصرين المحيطين به.
إيجاد العنصر الغالب في مصفوفة مرتبة
العنصر الغالب Majority Element هو العنصر الذي يظهر أكثر من n/2 مرة في مصفوفة مرتبة تحتوي على n من الأعداد الصحيحة.
إيجاد العنصر المكرّر في المصفوفة
المطلوب في هذه المسألة هو إيجاد العنصر المكرّر في مصفوفة تحتوي على مجموعة من العناصر المرتّبة، ويتكرّر فيها عنصر واحد فقط.
إيجاد الصغرى المحلية في مصفوفة
تعرف الصغرى المحلية Local minima بأنّها النقطة التي تكون أصغر من النقطتين المجاورتين لها أو مساوية لهما.
مصادر
- صفحة Divide and Conquer في توثيق الخوارزميات في موقع GeeksforGeeks.