خوارزمية فرق تسد

Divide and conquer is a powerful tool for solving conceptually difficult problems: all it requires is a way of breaking the problem into sub-problems, of solving the trivial cases, and of combining sub-problems to the original problem. Similarly, decrease and conquer only requires reducing the problem to a single smaller problem, such as the classic Tower of Hanoi puzzle, which reduces moving a tower of height ${\displaystyle n}$ to move a tower of height ${\displaystyle n-1}$.

The divide-and-conquer paradigm often helps in the discovery of efficient algorithms. It was the key, for example, to Karatsuba's fast multiplication method, the quicksort and mergesort algorithms, the Strassen algorithm for matrix multiplication, and fast Fourier transforms.

في جميع هذه الأمثلة، أدى أسلوب D&C إلى تحسين التكلفة التقاربية للحل. على سبيل المثال، إذا كانت (أ) الحالات الأساسية ذات حجم ثابت ومحدود، فإن جهد تقسيم المسألة ودمج الحلول الجزئية يتناسب طرديًا مع حجم المسألة.${\displaystyle n}$و(ب) يوجد عدد محدود${\displaystyle p}$من المشكلات الفرعية ذات الحجم ~${\displaystyle {\frac {n}{p}}}$في كل مرحلة، ستكون تكلفة خوارزمية فرق تسد${\displaystyle O(n\log _{p}n)}$.

بالنسبة لأنواع أخرى من أساليب فرق تسد، يمكن تعميم أوقات التشغيل أيضًا. على سبيل المثال، عندما يستغرق (أ) عمل تقسيم المشكلة ودمج الحلول الجزئية${\displaystyle cn}$الوقت، أين${\displaystyle n}$حجم الإدخال و${\displaystyle c}$ب) عندما يكون ثابتًا ما؛ ب) عندما${\displaystyle n<2}$، يستغرق تنفيذ الخوارزمية وقتًا محدودًا بـ${\displaystyle c}$ج) هناك${\displaystyle q}$مسائل فرعية حيث يكون حجم كل مسألة فرعية ~${\displaystyle {\frac {n}{2}}}$ثم، تكون أوقات التشغيل كما يلي:

• إذا كان عدد المسائل الفرعية${\displaystyle q>2}$إذاً، فإن وقت تشغيل خوارزمية فرق تسد يكون محدوداً بـ${\displaystyle O(n^{\log _{2}q})}$.
• إذا كان عدد المسائل الفرعية واحدًا بالضبط، فإن وقت تشغيل خوارزمية فرق تسد يكون محدودًا بـ${\displaystyle O(n)}$[ ^{10 ]​}

أما إذا استغرق الأمر بدلاً من ذلك عملية تقسيم المشكلة ودمج الحلول الجزئية${\displaystyle cn^{2}}$الوقت، وهناك مشكلتان فرعيتان لكل منهما حجم${\displaystyle {\frac {n}{2}}}$إذاً، فإن وقت تشغيل خوارزمية فرق تسد يكون محدوداً بـ${\displaystyle O(n^{2})}$[ ^{10 ]​}

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

تميل خوارزميات فرق تسد بطبيعتها إلى الاستخدام الأمثل لذاكرة التخزين المؤقت . والسبب هو أنه بمجرد أن تصبح المسألة الفرعية صغيرة بما يكفي، يمكن، من حيث المبدأ، حلها وجميع مسائلها الفرعية داخل ذاكرة التخزين المؤقت ، دون الحاجة إلى الوصول إلى الذاكرة الرئيسية الأبطأ . تُسمى الخوارزمية المصممة لاستغلال ذاكرة التخزين المؤقت بهذه الطريقة " خوارزمية غير معتمدة على ذاكرة التخزين المؤقت" ، لأنها لا تتضمن حجم ذاكرة التخزين المؤقت كمعامل صريح . [ ^{11 ] علاوة} على ذلك، يمكن تصميم خوارزميات فرق تسد للخوارزميات المهمة (مثل الفرز، وتحويل فورييه السريع، وضرب المصفوفات) لتكون خوارزميات مثالية غير معتمدة على ذاكرة التخزين المؤقت - فهي تستخدم ذاكرة التخزين المؤقت بطريقة مثالية على الأرجح، بمعنى تقاربي، بغض النظر عن حجم ذاكرة التخزين المؤقت. في المقابل، فإن النهج التقليدي لاستغلال ذاكرة التخزين المؤقت هو الحجب ، كما هو الحال في تحسين تداخل الحلقات ، حيث يتم تقسيم المسألة صراحةً إلى أجزاء ذات حجم مناسب - وهذا أيضًا يمكن أن يستخدم ذاكرة التخزين المؤقت على النحو الأمثل، ولكن فقط عندما يتم ضبط الخوارزمية لأحجام ذاكرة التخزين المؤقت المحددة لجهاز معين.

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

في العمليات الحسابية التي تتضمن تقريبًا، كالأعداد العشرية ، قد تُعطي خوارزمية فرق تسد نتائج أكثر دقة من طريقة تكرارية تبدو مكافئة لها ظاهريًا. على سبيل المثال، يمكن جمع N عددًا إما بحلقة بسيطة تُضيف كل قيمة إلى متغير واحد، أو بخوارزمية فرق تسد تُسمى الجمع الثنائي ، والتي تُقسّم مجموعة البيانات إلى نصفين، وتحسب مجموع كل نصف بشكل تكراري، ثم تجمع المجموعين. مع أن الطريقة الثانية تُجري نفس عدد عمليات الجمع التي تُجريها الأولى وتتحمل عبء الاستدعاءات التكرارية، إلا أنها عادةً ما تكون أكثر دقة. ^{[ 12 ]}

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

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

في التطبيقات التكرارية لخوارزميات البحث والإنشاء، يجب التأكد من وجود ذاكرة كافية مخصصة لمكدس التكرار، وإلا فقد يفشل التنفيذ بسبب تجاوز سعة المكدس . تتميز خوارزميات البحث والإنشاء الموفرة للوقت عادةً بعمق تكرار صغير نسبيًا. على سبيل المثال، يمكن تنفيذ خوارزمية الفرز السريع بحيث لا تتطلب أبدًا أكثر من${\displaystyle \log _{2}n}$استدعاءات متكررة متداخلة للفرز${\displaystyle n}$أغراض.

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

في أي خوارزمية تكرارية، هناك حرية كبيرة في اختيار الحالات الأساسية ، وهي المشكلات الفرعية الصغيرة التي يتم حلها مباشرة من أجل إنهاء التكرار.

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

من ناحية أخرى، غالبًا ما تتحسن الكفاءة إذا توقف الاستدعاء التكراري عند حالات أساسية كبيرة نسبيًا، وتم حل هذه الحالات بطريقة غير تكرارية، مما ينتج عنه خوارزمية هجينة . تتجنب هذه الاستراتيجية عبء الاستدعاءات التكرارية التي لا تُنجز عملًا يُذكر، وقد تسمح أيضًا باستخدام خوارزميات غير تكرارية متخصصة، تكون في تلك الحالات الأساسية أكثر كفاءة من الاستدعاء التكراري الصريح. يتمثل الإجراء العام لخوارزمية تكرارية هجينة بسيطة في اختصار الحالة الأساسية ، والمعروف أيضًا بالتكرار غير المباشر . في هذه الحالة، يتم التحقق مما إذا كانت الخطوة التالية ستؤدي إلى الحالة الأساسية قبل استدعاء الدالة، مما يتجنب استدعاء دالة غير ضروري. على سبيل المثال، في شجرة، بدلًا من الاستدعاء التكراري إلى عقدة فرعية ثم التحقق مما إذا كانت فارغة، فإن التحقق من كونها فارغة قبل الاستدعاء التكراري يتجنب نصف استدعاءات الدالة في بعض الخوارزميات على الأشجار الثنائية. بما أن خوارزمية D&C تُختزل في نهاية المطاف كل مسألة أو مسألة فرعية إلى عدد كبير من المسائل الأساسية، فإن هذه المسائل غالبًا ما تُهيمن على التكلفة الإجمالية للخوارزمية، خاصةً عندما يكون عبء التقسيم/الدمج منخفضًا. تجدر الإشارة إلى أن هذه الاعتبارات لا تعتمد على ما إذا كان المُصرّف يُنفّذ الاستدعاء الذاتي أم باستخدام مكدس صريح.

لذا، على سبيل المثال، ستتحول العديد من تطبيقات المكتبات لخوارزمية الفرز السريع إلى خوارزمية فرز إدراج بسيطة تعتمد على الحلقات (أو ما شابهها) بمجرد أن يصبح عدد العناصر المراد فرزها صغيرًا بما فيه الكفاية. لاحظ أنه إذا كانت القائمة الفارغة هي الحالة الأساسية الوحيدة، فإن فرز قائمة باستخدام${\displaystyle n}$ستتضمن المشاركات الحد الأقصى${\displaystyle n}$استدعاءات خوارزمية الفرز السريع التي لا تفعل شيئًا سوى العودة فورًا. زيادة الحالات الأساسية إلى قوائم بحجم 2 أو أقل ستؤدي إلى التخلص من معظم هذه الاستدعاءات عديمة الفائدة، وبشكل عام، تُستخدم حالة أساسية أكبر من 2 عادةً لتقليل الوقت المُستغرق في تكلفة استدعاء الدوال أو معالجة المكدس.

بدلاً من ذلك، يمكن استخدام حالات أساسية كبيرة تستخدم خوارزمية فرق تسد، ولكن تُنفذ الخوارزمية لمجموعة محددة مسبقًا من الأحجام الثابتة، حيث يمكن فك الخوارزمية بالكامل إلى كود خالٍ من التكرار والحلقات والشروط (مرتبط بتقنية التقييم الجزئي ). على سبيل المثال، يُستخدم هذا النهج في بعض تطبيقات تحويل فورييه السريع (FFT) الفعالة، حيث تكون الحالات الأساسية عبارة عن تطبيقات مفككة لخوارزميات FFT التي تعتمد على فرق تسد لمجموعة من الأحجام الثابتة. ^{[ 13 ]} يمكن استخدام طرق توليد الكود المصدري لإنتاج العدد الكبير من الحالات الأساسية المنفصلة اللازمة لتنفيذ هذه الاستراتيجية بكفاءة. ^{[ 13 ]}

يُعرف الشكل المعمم لهذه الفكرة باسم "فك التكرار" أو "التوسيع"، وقد تم اقتراح تقنيات متنوعة لأتمتة عملية توسيع الحالة الأساسية. ^{[ 14 ]}

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