في علوم الحاسب، يتم إدراج مجموعة الخوارزميّات التي تعمل وفق النمط أو النموذج نفسه (paradigm) تحت تصنيف واحد، ومن أشهر التصنيفات ما يُعرَف بتصنيف "فَرِّق تَسُد" (divide and conquer)، فما أصل التسمية؟ ولماذا أُطلِق على ذلك الصنف من الخوارزميات؟ وما هي أشهر أمثلته؟
اشتهر مبدأ "فرّق تَسُد" في المجال العسكري والسياسي تحديدًا، ويقوم على فكرة تفريق أو تقسيم قوّة الخصم ليسهل التعامل مع كلّ قسم على حِدَة، وكذلك منع أيّ قوى متفرّقة من التحالف أو الاتحاد لتشكيل قوّة أكبر يصبح التعامل معها أصعب.
ولأنّ أحد أصناف الخوارزميّات يقوم على الفكرة نفسها، فقد سُمِّي بالتسمية نفسها (divide and conquer algorithm)، ووجه الشبه هو أنّ هذا النوع من الخوارزميّات لا يتعامل مع المشكلة في صورتها الكاملة، وإنّما يعمل على تقسيمها إلى مجموعة من المشكلات الأصغر..
ثم يقسّم تلك المشكلات الأصغر إلى مجموعة من المشكلات الأصغر، وهكذا حتى تتحلّل المشكلة الكبيرة إلى أصغر أجزائها الممكنة، ثم يبدأ العمل على حلّ المشكلة ابتداءً من أصغر أجزائها، ثم تُجمَع الأجزاء المتفرّقة بعد حلّها، حتى نصل في النهاية إلى حلّ المشكلة بالكامل.
تقوم خوارزميّة "فرّق تَسُد" (divide and conquer) على ثلاثة مفاهيم أساسيّة:
1- التفريق أو التقسيم (divide):
حيث يتم تقسيم المشكلة إلى مجموعة من المشكلات الأصغر أو الفرعيّة (subproblems)، ويستمر تقسيم المشكلات الأصغر إلى مشكلات أصغر منها ما دام ذلك ممكنًا.
1- التفريق أو التقسيم (divide):
حيث يتم تقسيم المشكلة إلى مجموعة من المشكلات الأصغر أو الفرعيّة (subproblems)، ويستمر تقسيم المشكلات الأصغر إلى مشكلات أصغر منها ما دام ذلك ممكنًا.
2- السيطرة على المشكلة وحلّها (conquer):
بعد عمليّة التقسيم، يبدأ العمل على حلّ كلّ مشكلة من المشكلات الفرعيّة (subproblems) على حِدَة، فكلّما كانت المشكلة أصغر، كان التعامل معها وحلّها أسهل.
بعد عمليّة التقسيم، يبدأ العمل على حلّ كلّ مشكلة من المشكلات الفرعيّة (subproblems) على حِدَة، فكلّما كانت المشكلة أصغر، كان التعامل معها وحلّها أسهل.
3- الجمع أو الضم (combine):
وهو ضدّ مفهوم "التقسيم" (divide) المذكور أعلاه، ففي هذه المرحلة، تكون المشكلات الفرعيّة محلولة، ويبقى فقط توحيدها لتعود إلى شكلها الأصلي قبل تقسيمها.
وهو ضدّ مفهوم "التقسيم" (divide) المذكور أعلاه، ففي هذه المرحلة، تكون المشكلات الفرعيّة محلولة، ويبقى فقط توحيدها لتعود إلى شكلها الأصلي قبل تقسيمها.
من أشهر الأمثلة على خوارزمية "فرّق تَسُد" (divide and conquer):
1- الترتيب بالدمج (merge sort).
2- الترتيب السريع (quick sort).
وبالمناسبة، ما أحوجنا إلى اتّباع هذا النهج مع كثير من مشكلات الحياة التي تواجهنا.
انتهى.
1- الترتيب بالدمج (merge sort).
2- الترتيب السريع (quick sort).
وبالمناسبة، ما أحوجنا إلى اتّباع هذا النهج مع كثير من مشكلات الحياة التي تواجهنا.
انتهى.
جاري تحميل الاقتراحات...