البنية الفرعية المثلى

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

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

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

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

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

يمكن تقديم تعريف أكثر رسمية للبنية الفرعية المثلى. لنفترض أن "المشكلة" عبارة عن مجموعة من "البدائل"، وأن لكل بديل تكلفة مرتبطة به، c ( a ). المهمة هي إيجاد مجموعة من البدائل التي تُقلل c ( a ). لنفترض أن البدائل قابلة للتقسيم إلى مجموعات فرعية، أي أن كل بديل ينتمي إلى مجموعة فرعية واحدة فقط. ولنفترض أن لكل مجموعة فرعية دالة تكلفة خاصة بها. يمكن إيجاد القيم الدنيا لكل من دوال التكلفة هذه، وكذلك القيم الدنيا لدالة التكلفة الكلية، عند تقييدها بنفس المجموعات الفرعية . إذا تطابقت هذه القيم الدنيا لكل مجموعة فرعية، فمن الواضح تقريبًا أنه يمكن اختيار قيمة دنيا كلية ليس من المجموعة الكاملة للبدائل، بل من المجموعة التي تتكون فقط من القيم الدنيا لدوال التكلفة المحلية الأصغر التي حددناها. إذا كان تقليل الدوال المحلية مشكلة من "رتبة أدنى"، وإذا أصبحت المشكلة تافهة (على وجه التحديد) بعد عدد محدود من هذه التخفيضات، فإن المشكلة تمتلك بنية فرعية مثلى.

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

• مشكلة المسار الأطول
• الأسس المتسلسلة
• أقل تكلفة لتذكرة طيران. باستخدام البحث عن الرحلات الجوية عبر الإنترنت، سنجد غالبًا أن أرخص رحلة من المطار أ إلى المطار ب تتضمن توقفًا واحدًا عبر المطار ج، بينما أرخص رحلة من المطار أ إلى المطار ج تتضمن توقفًا عبر مطار آخر د. مع ذلك، إذا أخذنا في الاعتبار الحد الأقصى لعدد فترات التوقف كمعامل، فإن المسألة تتضمن بنية فرعية مثلى. أرخص رحلة من أ إلى ب تتضمن k فترة توقف على الأكثر هي إما الرحلة المباشرة؛ أو أرخص رحلة من أ إلى مطار ج تتضمن t فترة توقف على الأكثر، حيث t عدد صحيح يتراوح بين 0 و k ، بالإضافة إلى أرخص رحلة من ج إلى ب تتضمن k-1-t فترة توقف على الأكثر .

• البرمجة الديناميكية
• مبدأ الأمثلية
• خوارزمية فرق تسد