صياغة مشكلة البرمجة الديناميكية العامة

Question

وأتساءل عما إذا كان دالة الهدف من مشكلة البرمجة الديناميكية العامة يمكن دائما أن تصاغ كما هو الحال في ديناميكية البرمجة في ويكي ، حيث دالة الهدف هو مجموع العناصر للعمل والدولة في كل مرحلة؟ أو أن يكون مجرد حالة specical وما هي الصيغة العامة؟

---

وتحرير:

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

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

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

Answer 1

وهذا ليس كيف يمكنني أن أصف مشكلة الأمثل التعسفية (أو خوارزمية البرمجة الديناميكية). على وجه الخصوص، عامل β <سوب> ر تبدو مثل الهندسة الإختراق الكهربائية التي المبرمجين لن تريد عادة. أكثر بمهارة، يبدو أنها لن تكون دائما واضحة ما وظيفة <م> F هو لمشكلة معينة.

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

وإذا كان هذا هو الشيء المفيد أن تفعل أو لا يعتمد على المشكلة، وأفترض.

Answer 2

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

ومن تكرار عام F (ن) = F (ن 1) + F (ن 2) هل يمكن تنفيذ الخوارزمية التالية:

int fibonacci(n):
  if (n < 2): return 1
  else: return fibonacci(n-1) + fibonacci(n-2)

والآن هذه هي بالطبع ليست فعالة على الإطلاق، لأنه يخلق عددا هائلا من المكالمات متكررة، منها مثلا.

F(8) = F(7) + F(6) = [F(6) + F(5)] + [F(5) + F(4)] = ... 

وحتى هنا نحن نرى بالفعل أن فيبوناكسي (5) يتم حسابها مرتين من قبل التنفيذ. و<م> البرمجة الديناميكية النموذج هو الآن "memoize" أو "مخبأ" نتائج مثل هذا:

integer_map store;
int memofibo(n):
  if (n < 2) : return 1
  else if (store.find_key(n)): return store.find_value(n)
  else:
    int f = memofibo(n-1) + memofibo(n-2)
    store.set(n, f)
    return f

وهذا التطبيق ضمان أن الخطوة متكررة يتم تنفيذه على الأكثر مرة واحدة كل قيمة وسيطة ن، لذلك بحساب عدد فيبوناتشي الألف في O (ن تسجيل ن) الوقت (على افتراض O القياسية (سجل ن)) تنفيذ النقابي مجموعة "مخزن".

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

Answer 3

والناس،

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

المنبر الوقت:

وبالنسبة لأولئك الذين يهتمون لمناقشة على ما هو مناسب لتجاوز المكدس، دعونا نلاحظ أن الخوارزمية خوارزمية بغض النظر عمن يدعي أنها جزء من مجال عملهم. طريقة البسيط، Djikstra في الأسلوب، فرع وملزمة، والاسترخاء لاغرانج، كلها خوارزميات أو أساليب حل أنواع معينة من المشاكل. وتدرس العديد من هذه والمعمول بها في كل المجالات حتى الحدود بين OR وCS هو ضبابية جميلة في هذا المجال.

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

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