مشاكل فرعية متداخلة

في علم الحاسوب ، يُقال إن للمسألة مسائل فرعية متداخلة إذا أمكن تقسيمها إلى مسائل فرعية يُعاد استخدامها عدة مرات، أو إذا كانت الخوارزمية التكرارية للمسألة تحل المسألة الفرعية نفسها مرارًا وتكرارًا بدلًا من توليد مسائل فرعية جديدة باستمرار. ^{[ 1 ] [ 2 ] [ 3 ]}

على سبيل المثال، تتضمن مسألة حساب متتالية فيبوناتشي مسائل فرعية متداخلة. يمكن تقسيم مسألة حساب العدد النوني في متتالية فيبوناتشي F ( n ) إلى مسألتين فرعيتين: حساب F ( n - 1) و F ( n - 2)، ثم جمعهما. ويمكن تقسيم المسألة الفرعية لحساب F ( n - 1) بدورها إلى مسألة فرعية تتضمن حساب F ( n - 2). وبالتالي، يُعاد استخدام حساب F ( n - 2)، ومن ثم تتضمن متتالية فيبوناتشي مسائل فرعية متداخلة.           

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

في التطبيقين التاليين لحساب متتالية فيبوناتشي ، fibonacciيستخدم أحدهما التكرار العادي والآخر fibonacci_memيستخدم التخزين المؤقت . يُعدّ التطبيق الأول أكثر كفاءة بكثير حيث يتم حساب fibonacci_memقيمة أي عدد معين مرة واحدة فقط.n

تعريف فيبوناتشي ( n ): إذا n <= 1 : إرجاع n إرجاع فيبوناتشي ( n - 1 ) + فيبوناتشي ( n - 2 )دالة fibonacci_mem ( n , cache ): إذا كان n <= 1 : أرجع n إذا كان n في cache : أرجع cache [ n ] cache [ n ] = fibonacci_mem ( n - 1 , cache ) + fibonacci_mem ( n - 2 , cache ) أرجع cache [ n ]print ( fibonacci_mem ( 5 , {})) # 5 print ( fibonacci ( 5 )) # 5

عند تنفيذ الدالة، fibonacciفإنها تحسب قيمة بعض الأرقام في التسلسل عدة مرات، بينما fibonacci_memتعيد استخدام القيمة nالتي تم حسابها مسبقًا:

f(5) = f(4) + f(3) = 5 | | | f(3) = f(2) + f(1) = 2 | | | | | f(1) = 1 | | | f(2) = 1 | f(4) = f(3) + f(2) = 3 | | | f(2) = 1 | f(3) = f(2) + f(1) = 2 | | | f(1) = 1 | f(2) = 1

f(5) = f(4) + f(3) = 5 | | f(4) = f(3) + f(2) = 3 | | f(3) = f(2) + f(1) = 2 | | | f(1) = 1 | f(2) = 1

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

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