أصدقاء الأجانب

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

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

عرض مشكلة

من الخوارزمية التالية من أجل حل Mochila 0 / 1 عن طريق المتفرع والتقليم ، ولقد نفذ برنامج جيم # الذي يحل هذه المشكلة مع الاستراتيجيات التالية :

• يخرج أولا -- (أولا يخرج أولا) أولا و-- يخرج أولا
• LIFO -- (آخر يخرج أولا) الماضي في أول خارجا. (Piła)
• ش -- LIFO -- الماضي في صفيف يخرج أولا. (مجموعة من البطاريات)
• ش -- يخرج أولا -- صفيف أولا يخرج أولا. (مجموعة من الغراء)

قائمة العقد العيش (LNV) سيتم تشكيلها من قبل كائنات من الدرجة عقدة ، والتي تم تعريفها على النحو التالي :

قرار عملية

1. نواقل تصنف حسب الوزن ونسبة الاستفادة باء / P.
2. مرة واحدة هذه العقدة الجذر يتم إنشاؤها وإضافتها إلى قائمة العقد على قيد الحياة.
3. عند هذه النقطة تدخل حلقة الذي يتكرر حتى LNV فارغة ما يلي :
4. إذا كانت العقدة استخراج وعود أن تكون لمصلحة أن درسنا حتى الآن (تشذيب الأولى) النوع أطفالهم في عقدة y.
5. عن كل طفل إذا كان الوزن هو أنه يحتوي على> بكثير من الحد الأقصى المسموح به وزنا لا تحاول (أحقق شيئا) لأنه منشئ الفئة أنا تهيئة العقد ومرتفعات لقيم أرقام ضئيلة جدا.
6. على خلاف ذلك العلاج وعقدة الجنس التقديرات وفقا لذلك.
7. ثم فإنه يتحقق ما إذا كان الوضع الحالي هو التوصل إلى حل ، وإذا كان الأمر كذلك التحديثات في حل العقدة.
8. إذا لم يكن الحل هو معرفة ما اذا كان العلوي من العقدة التي نتعامل معها هي أكبر من أو يساوي إلى جيم أننا (تشذيب 2) يضاف إلى LNV إن لم يكن.

الهدف :

الهدف هو الحصول على الحل الأمثل لمشكلة حقيبة مع استراتيجيات مختلفة ومقارنة أعداد العقد ولدت في كل لمعرفة أيهما أكثر كفاءة في حالة العلاقات بين البلدين.

الحل المقترح

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