أعلانات الحراج بيع اسهم يمن موبايل عدد 4000 سهم - Please contact me - Contact us for Family Visa (Parents ,wife or Childrens & Trade Lisence Tenancy - Contact Us For Trade License Family Visa Online - Just Contact by Call, WhatsApp and Email for FREE Building Demolition - Contact with us for Trade Licence and Family (Child,Wife,Parents) Visa with Tenancy Contract Simpl - Part time job needed contact me pls North Indian cook 052689 - CAR LIFT AVAILABLE (AL AIN TO DUBAI ) - بيت للبيع عرطه جدن محتاج بحي اليبي جوارجامعه الايمان - أرض للبيع بالسلوم بوفيشة قرب ياسمين الحمامات - تلفون CAT S60 - للبيع ارض بالمهبولة مرخصة فندق - بناية للبيع في دلهون 3 طوابق - للبيع قسيمة جديدة لم تأجر في هدية 12 شقة - للبيع عماره في المهبوله - مكاتب تجاريه للايجار بالسالميه وحولي بأسعار مناسبة - بيع ركشات بالتقسيط - ماذون شرعي طرابلس ليبيا - مدرسه للروضه والمراحل الاخرى ف اللغه الانجليزيه - موقع هبة لجميع الاغراض مجانا للمحتاجين - حلوى الكبش بسعر نار - جنبي دوريه موديل 2015 - Clank - FEMALE DRIVER AVAILABLE - مخطط جديد للبيع غرب حديقه الكلاكلات الكبرى - يتوفر بذور بونيكام بمباسا الامريكي - للبيع ارض زراعية في التواني - منحف لايبو 6 الاصلي - بيوت شعر+خيام ×مجالس تراثية+ دلال ونجور+ مستلزمات الرحلات كاملة+ إيجارات خشب - جهاز ايسر لاب وتاب بنفس الوقت - أفضل شركه نقل عفش بالمدينه المنورة مع الفك والتركيب - BUDGET CITY MOVERS AND PACKERS - منزل للبيع مساحة 170م والارض 1603م من المالك - طارمات محل مواد غذائية - للبيع شيشه الكترونيه مع نكهه ريد بول - فستان سهره - منزل للإيجار بجنزور شهداء عبدالجليل الشركة التركية - شقة جميلة في حدائق المنزه 2 بالقرب من مونوبري - عود كهربائي مميز جدا جدا والصور تتكلم عن العود - للبيع سعد العبدالله قظ،ظ، - ستوديو مفروش في حي الخضراء تونس - صندوق أطفاء حريق - شقق مفروشة للايجار في أمدرمان -المهندسين. - ارض 11 دونم في قاع خنا - ارض 500م في الحليس خلف شيل الجبو - مقراج كهربائي - الحليس - ارض للبيع في جريبا حوض قرقش - شقة للبيع اقامة ريحانة مراكش - شقة أمام مصحة الياسمين و قرطاجنة و باستور -
موقع الو كراج المساعيد - عثملي - Lailani Caponpon Bate - امل( البيلسان) - ضنينه النعمانيه - دكتور حسن قطب - د/ايمان عطوي - مصنع ابن شبنان قويعيه - رجل الاعمال بدر الخرافي - علي خضير الجهني. المدينه المنوره خط المئه (خلف القريه الحجازيه - شاورما كلاسيك - راجو طبيب - بشار رباح سكرتيره مريانا - د.فراس العجمي - فنجال الشيباني ابو سلطان - خالد امين العطاس - ميييييري - شاي ساره العجمي للتنحيف - صالون ايلاش/بيتي - سامي سامر نمنقاني - عبدالله السلمود الطوارئ - عبدالله السلبوت - نجم سهيل فقع - بشاير الخير كلينكس - Ghanaym_coll 18k T - مصبغه الماسه مجمع العاقول - فراس الحازمي - د-ابومحمد اكرم بريكيت - دكتور هشام النجيحي جلدية - معاذ أبانمي*شركة الخيول العربية - دكتور محمد مروان خجا - الشيخ ابو مهند - مساج تايلندي خايس - ياسر القعود - د. هبه - مطعم سمكمك الرقعي - معلم البلاك الحسينيه - بقاله توصيل بكبد - الدكتوره عبله - النقل الجماعي - رايد مسفر بن وافيه - بقالة حبايب العارضية - بزز - نوال الشغار - مكتب صفيه تراويلس - عبدالناصر للأستقدام - دكتور هشام الشراكي - دكتور غازي الصالح - Dr. Olivier de farahan in London - العبدلي مطعم بخاري احمد -
الجديد شركة القُصير السعودية لتأجير وبيع الخيـام الأوروبية ومولدات الكهرباء - الصلاة الصلاة - كيف ازرع النعناع في المنزل ؟ - فوائد التمر والحليب - كيف توفر العديد من المال على نفسك ؟ - كيف تبداء بمشروع صغير وناجح ؟ - كيف تصبح غنياً ؟ - كيف توفر المال ؟ -
آخر المشاهدات طريقة تحضير الكانيلوني من الشيف منال العالم - هاتف وعنوان مؤسسة عبد القادر صالح الغامدي - الباحه - قاعدة الوردة قصة اللعبة - نموذج طلب تجديد ترخيص لممارسة نشاط نقل البضائع والمهمات بأجر بالسعودية - صيد الريم (مسلسل) الممثلون - دوار كولومبوس (فيلم) القصة - طريقة عمل ومقادير البسكوت الساده من منال العالم - هواتف شركه بن تركي المحدودة ومعلومات عنها بالسعودية - الفنان مسلم علي عبدالكريم سيرته - مزايا وعيوب شركات التضامن وهل تصلح للمشروعات الصغيرة - لغز القبعات البيضاء والسوداء الحل - كمال مسعودي حياته - هاتف وعنوان مكتب الخالدي للإستقدام - الخبر, مدينة الخبر - [بحث جاهز للطباعة] بحث حول علم الكيمياء , كل ما يخص الكيمياء - - مزايا وعيوب شركات التوصية البسيطة وهل تصلح للمشروعات الصغيرة - مزايا وعيوب الشركات ذات المسئولية المحدودة وهل تصلح للمشروعات الصغيرة - صبر سقطري فوائد الصبر - إدارة الأسلحة والذخيرة للقوات المسلحة (مصر) مهام الإدارة - ولاية الأغواط الجغرافيا - صباح الخير يا وطنا (أغنية) كلمات الأغنية - جزيرة الكنز ملخص الرواية - جذر نبات أهم وظائف الجذر - طريقة تحضير فاهيتا الدجاج من الشيف منال العالم - طريقة عمل المق ،، كيك لا تفوتك - بريكاريا الطبقة الجديدة الخطرة - علاء الدين (حكاية) ملخص الحكاية - تعلم كيف تقرأ التحاليل الطبية - هاتف وعنوان البراك للأبواب الأتوماتيكية - ابها, مدينة ابها - مناخ الجزائر خصائص المناخ في الجزائر - المتممات المجرورة - هاتف ومعلومات عن فندق الحارثية بالمدينة المنورة - [بحث جاهز للطباعة] قائمة بعناوين مشاريع التخرج لتخصص الرياضيات - - سبارتاكوس (مسلسل) القصة - ميزانية و تكاليف ودراسة جدوى مشروع ثلاجات التخزين - هاتف وعنوان المستوصف السعودي الطبي - بريده 2, القصيم - المواطنة الرقمية - وصفة هائلة من الطب البديل لعلاج الروماتيزم أمراض العظام والمفاصل بالاعشاب - بولنت ارسوي طفولتها ونشأتها - طريقة تحضير الثريد (اكله بحرينيه) - هواتف وأرقام إدارة الفتوى والتشريع بالكويت - هواتف مستشفى أحد المسارحة و معلومات عنها فى بجــــــازان بالسعودية - تطور التصميم الداخلي - هاتف وعنوان مستودعات القصيبي الطبية - الحاير, مدينة الرياض - سور القران لكل شهر من شهور الحمل - موفق أراكيلي تاريخ موفق أراكيلي - هاتف وعنوان مستوصف الجزيرة - النسيم, مدينة الرياض - هاتف وعنوان مشغل ليلتي - بلجرشي, الباحة - طريقة عمل ومقادير الأ ندومي بالخضار والصويا من مطبخ منال العالم - وصفة تساعد على التئام الجروح: بسرعة بخلطات الاعشاب - وصفات تعمل بالمنزل - طريقة عمل وصفة الأرز بالكاري من اكلات منال العالم - لجنة زكاة القدس مشاريع - زين عبده باهارون - خصائص الوصف انواع الوصف - هاتف وعنوان ثلاجة السلطان - عنيزه, القصيم - هاتف و عنوان مستشفى رماح و معلومات عنها بالرياض بالسعودية - هاتف وعنوان مستشفى الملك فهد الجامعي - الخبر شمال, مدينة الخبر - [نسائيات] معلومات هامة عن عملية تنظيف الرحم - منوعات مفيدة - [مواضيع صحية] مستوصفات جدة لفحص العمالة , مستوصف فحص العمالة الوافدة بجدة - طب بديل وطب عام - إتمام إجراءات زواج السعودي من أجنبية بعد وصول الموافقة فى الاردن - هاتف وعنوان مطعم التابل - بريده, القصيم - هاتف وعنوان مصنع الخير لشبك الأسوار والأسلاك الشائكة - النزله, جدة - هاتف وعنوان مجموعة بن شيهون للإطارات - طريق مكه, جدة - هاتف وعنوان المستشفى الأهلي - خميس مشيط, عسير - هادي عكاشة هجاءه الخميني للخميني - هاتف وعنوان مستشفى الأمين - الطائف المركزي, الطائف - طريقة تحضير اقراص الكبه (كبة الاحساء ) كبة الهريس روعه بالصور - رايون كيف يُصنع الرايون - بسام جرار النشأة - هواتف مكتب مكافحة التسول بالدمام ومعلومات عنها بالسعودية - دايتونا يو إس أيه (لعبة فيديو) - وصفة هائلة من الطب البديل لعلاج النتؤات او الثؤلول او الثلول بالاعشاب - هواتف مكتب مكافحة التسول بالرياض ومعلومات عنها بالسعودية - وليم روان هاملتون - [بحث جاهز للطباعة] أهم بحث تاريخي عن نابليون بونابرت - - خليل هنداوي خليل الهنداوي المعلم والأديب - هاتف وعنوان البناء والعمار لصناعة الأثاث - خميس مشيط, عسير - كفر قاسم نبذة تاريخية - مؤمن حسن عن حياته - هاتف وعنوان مستوصف الأنصار الجديد- الصفا, جدة - عزبة ابوقتادة - هاتف وعنوان عيادة الدكتور أسعد محمد عبدالفتاح - باب مكه, جدة - هاتف وعنوان مطابخ القاضي - المرسلات, مدينة الرياض - هضبة الدبدبة - نظام التشغيل الشبكي الخصائص - [طب بديل ] طرق علاج تكيس المبايض بالأعشاب الطبية - مواضيع صحية - إمارة لبراكنة نسبهم - هاتف مركز حي المطار(بالمجمعة) الصحي بالرياض و معلومات عنه بالسعودية - هواتف مؤسسة الجلال التجارية المحدودة ومعلومات عنها بالسعودية - هاتف وعنوان مستشفى الدكتور محمد فخري - الخبر, مدينة الخبر - فلوريد الكالسيوم الخواص - سحر الغجريات (مسلسل) المزيد - هواتف مكتب مكافحة التسول ببريدة ومعلومات عنها بالسعودية - أبناء القهر (مسلسل) القصة - مرآة الممالك (كتاب) - طريقة تحضير كريمة الزبدة من الشيف منال العالم - اضطراب الحركة النظمية دلائل وأعراض - , تداوي , زيوت , الزعفران , الحلبة , البصل , الثوم , حبة البركة , بحة الصوت - ميزانية و تكاليف ودراسة جدوى مشروع إنتاج أحذية جلدية للتصدير - شروط نقل ملكية المؤسسات بالتنازل أو البيع بالسعودية - مخاطر صاعق الحشرات الكهربائي - هاتف وعنوان مطبخ شراف للولائم - حائل - طريقه تحضير الشهباية اللبناني - هاتف مركز جرول الصحي بمكة المكرمة و معلومات عنه بالسعودية - مقبرة رع موزا وصف المقبرة - هاتف وعنوان مستوصف آل مترك - المزاحميه, محافظات الرياض - طريقة عمل شاي القرفة او الدارسين لا تفوتك - ثماني أضلاع ثماني منتظم (مثمن) - هاتف و معلومات عن شركة مصر للطيران بالمدينة المنورة - وصفة هائلة من الطب البديل لعلاج الأكزيما بالاعشاب - هاتف وعنوان مستوصف السلام - عنيزه, القصيم - أحمد بن حنبل نسبه وأسرته - توشيح (شعر) بعض شعراء الموشحات - هاتف وعنوان مؤسسة الهدبانية للأدوات الصحية - السليمانيه, جدة - كاتدرائية طرابلس - هاتف وعنوان مجمع عيادات د/ جميل خطاب - الهفوف, الاحساء - تعيين المحتوى المائى للتربة الهدف من التجربة - يور سويت سكس سكس سكس يور سويت سكس سكس سكس - معركة هدان معلومات أخرى - هاتف وعنوان مستشفى الأهلي السعودي - العزيزيه, مكة المكرمة - خط الثلج الدائم - محمد حسين زيدان المولد والنشأة - وصفة هائلة من الطب البديل لعلاج النحافه و فقر الدم وضعف الجسم بالاعشاب - تنفس كوسماول الاصطلاح - امراض الدواجن ، اسبابها ، علاجها ، طرق الوقاية منها - هاتف وعنوان مستشفى الدكتور غسان نجيب فرعون - خميس مشيط, عسير - الليالي الطويلة (فيلم) فريق العمل - متطلبات تأشيرة العمل فى سفارة السعودية بالاردن - الشروط المطلوب استيفائها للحصول على ترخيص نقل البضائع والمهمات بأجر بالسعودية - خليج فندي المد والجزر - حساب الأبقطي تعريف حساب الأبقطي - عبد المحسن بن حشر بن حميد نشأته - قائمة مغنيات لبنانيات قائمة - مصباح الإضاءة المصابيح المتوهجة - هاتف وعنوان البناء والعمار للمفروشات - بريده 2, القصيم - والدة ويسلر (لوحة) قصة اللوحة - وصفة لعلاج التهاب المفاصل و آلام العضلات بخلطات الاعشاب - وصفات تعمل بالمنزل - متطلبات الحصول على تأشيرة العمرة فى سفارة السعودية بالاردن - حرب بني أصفهان معاركها - طريقة عمل القهوة العربية على طريقة منال العالم - نابروكسين التركيب والتفاصيل - طريقة اعداد بطاطا مرحية بيري بالذ طعم خطوة بخطوة - [بحث جاهز للطباعة] طرائق التدريس - - طرطرات الصوديوم والبوتاسيوم - دائرة جانت بلديات دائرة جانت - هاتف وعنوان مستوصف السلامة الطبي - خميس مشيط, عسير - هاتف وعنوان مستوصف الأسرة لطب الأسنان - محاسن, الاحساء - [بحث جاهز للطباعة] بحث علمي جاهز عن صعوبات التعلم واسبابها - - هاتف وعنوان مستوصف حي الريان الطبي - طريق خريص, مدينة الرياض - هاتف وعنوان مكتب الوسيط للإستقدام - بريده, القصيم - جيزيل حبيب أبو جودة المسيرة المهنية - الأمير عفاس بن محيا - هضبة حضرموت سطح الهضبة - [بحث جاهز للطباعة] بحث علمي جاهز عن الفيزياء - - طريقة تحضير كيكة الدخن بدون بيض بالذ طعم خطوة بخطوة - مفاتيح الجنان (كتاب) لمحة عن الكتاب - ازالة الاملاح من النفط الخام - الشروط المطلوب استيفاءها للحصول على رخصة تشغيل لشاحنة فردية بالسعودية - معلومات صادمه عن اكل الافوكادو ؟ - [بحث جاهز للطباعة] خاتمة بحث ديني علمي عربي قصيره - - عين بسام الموقع - رشاش بي كي مواصفات السلاح - هاتف وعنوان مؤسسة السديري التجارية للأجهزة الكهربائية والإلكترونية - حائل - ورم الخلايا الجرثومية أسباب المرض - الزي التقليدي السوري الأزياء - وصفة لعلاج سلس البراز بالاعشاب الطبيعية - دراسة جدوى مفصلة لاقامة مشروع محل تعبئة وبيع اسطوانات غاز بالسعودية - هاتف وعنوان مطاعم بالم بيتش - طريق المدينة, جدة - الطوق والإسورة (فيلم) قصة الفيلم - ملحمة خصائص الملحمة - نسطور القديس مار نسطورس - انسداد قناة فالوب الأنواع - هاتف وعنوان مستشفى السلامة - الخبر, مدينة الخبر - هاتف وعنوان مستوصف هجر - الجامعه, الاحساء - تمسكنت فتمكنت (مسرحية) - هواتف شركة النعيم للمقاولات المحدودة ومعلومات عنها بالسعودية - هاتف وعنوان مؤسسة خبراء طيبة للمصاعد - الحره الشرقيه, المدينة المنورة - [بحث جاهز للطباعة] أجدد بحث تربوي عن الهدر المدرسي - - طريقة عمل مرق روبيان مثل المطاعم - اكلات من المطبخ الكويتي - الجهاز الدوري المفتوح الجهاز الدوري المفتوح والجهاز الدوري المغلق - قلعة سيف الدولة الحمداني سيف الدولة الحمداني - ظاهرة كومبتون مقدمة - استخدام مركب لومينول في التحقيق الجينائي (يكشف عن الدم).. - فرجيوة الموقع الجغرافي - سداسي أضلاع السداسي المنتظم - جامع السنن والمسانيد لابن كثير أقوال العلماء على الكتاب - أسباب برودة القدمين - هاتف وعنوان مطعم الأرطاوية - الأرطاويه, محافظات الرياض - [بحث جاهز للطباعة] أجدد بحث عن كيفية كتابة تقرير ميداني - - مستصفرة مرجية - هواتف مكتب المتابعة الاجتماعية بمكة المكرمة ومعلومات عنها بالسعودية - مرقة صفاقسية طريقة الطهي - صبح البشكنجية حياتها - طريقة تحضير الكبة الدبابة السورية - طريقة عمل الرشوفة اكلة المرأة الوالده من البحرين - دراسة جدوى لمشروع صناعة خراطيم الري بالتنقيط من المطاط المعاد تدويره - عمر قتلني (فيلم) - [بحث جاهز للطباعة] بحث علمي عن مرض الايدز،معلومات عن مرض الايدز،الايدز،مرض الايدز - - مصباح نيون فكرة العمل - قائمة سدود اليمن سدود قديمة - طريقة تحضير وصفة لحم ناشف (دندن) خطوة بخطوة -
اليوم: الاثنين 21 يناير 2019 , الساعة: 5:21 م / اسعار صرف العملات ليوم الاثنين 21/01/2019


اعلانات
محرك البحث


مسألة حقيبة الظهر

نشر قبل 2 سنة و 4 شهر 371 مشاهدة


اعلانات
شاركنا رأيك بالموضوع

مشكلة نابساك

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

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

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


التطبيقات

أثبتت دراسة سجل الخوارزميات في جامعة ستوني بروك التي أجريت عام 1998 أنه من أصل 75 مشكلة حسابية، احتلت (النابساك) المرتبة الثامنة عشر كأكثر المشاكل شعبية والرابعة من حيث الأكثر حاجة بعد الkd-trees ومشكلة التعبئة بن.

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

من إحدى التطبيقات المبكرة التي استخدمت خوارزمية النابساك كانت في عملية بناء وتمرير الاختبارات. بحيث أن من يأخذ الاختبار له الحرية في اختيار الأسئلة التي يريد أن يجيب عليها. في أمثلة بسيطة كهذه يكون من السهل تزويد المتقدمين للاختبار بهذا الخيار. مثال إذا كان الاختبار يحتوي على 12 سؤالا، كل سؤال ب10 نقاط. للحصول على أعلى نتيجة يتوجب على من يأخذ الاختبار حل 10 أسئلة فقط للحصول على 100 نقطة، ولكن في الاختيارات التي لا تحتوي على توزيع متساوٍ للنقاط يصبح من الصعب التزويد بخيارات للحل. اقترح فيورمان ووايس نظاما يُعطى فيه الطالب اختبارا غير متجانس مع ما مجموعه 125 نقطة ممكنة. يطلب من الطلاب إجابة جميع الأسئلة باستخدام أفضل قدراتهم. فيما يتعلق بالمجموعات الفرعية المحتملة للمشاكل التي تصل قيمة نقاطها إلى 100، فإن خوارزمية الحقيبة (نابساك) ستحدد أي من المجموعات الفرعية ستقدم للطالب أعلى درجة ممكنة.




التعريف

المشكلة الأكثر شيوعا التي يتم حلها هي مشكلة نابساك 0-1، التي يتم فيها ترقيم عدد (xi) من النسخ من كل نوع ب 0أو 1. مع إعطاء مجموعة من المواد أرقاماً من 1إلى (n). كلٌ له وزنه (wi) وقيمته (vi)، بالإضافة إلى الحد الأقصى لسعة الوزن (W)،

maximize

subject to and .


نلاحظ أن (xi) تمثل عدد حالات وضع المادة (i) في الحقيبة. والمشكلة هي تحقيق أقصى قدر ممكن من مجموع قيم المواد الموجودة في الحقيبة، بحيث يكون مجموع الأوزان أقل من أو يساوي قدرة الحقيبة.

تزيل مشكلة الحقيبة المحدودة (BKP) القيد المتمثل بوجود قطعة واحدة من كل مادة، إلا أنها تحد العدد (xi) من النسخ لكل نوع من المواد بعدد صحيح ( )

maximize

subject to and



لا تضع مشكلة الحقيبة غير المحدودة حد أعلى لعدد النسخ من كل نوع من المواد. ويمكن صياغتها على النحو الوارد أعلاه، باستثناء أن القيد الوحيد على (xi)هو أنه عدد صحيح غير سالب.

Maximize

subject to and


هناك مثال على مشكلة الحقيبة غير المحدودة موضَّح من خلال الشكل المرفق في بداية هذه المقالة مع تسميته التوضيحية.



التعقيد الحسابي

تعتبر مشكلة الحقيبة (نابساك) مثيرة للاهتمام من وجهة نظر علم الحاسوب لأسباب عديدة

• إن قرار أخذ المادة أو عدمه يتم حسابه بصيغة متعدد الحدود؛ لذلك لا يوجد أي خوارزمية معروفة صحيحة وسريعة (بوقت متعدد الحدود) لكل الحالات.

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

هناك خوارزمية شبه متعددة الحدود باستخدام البرمجة الديناميكية.


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

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













الحل

مشكلة نابساك 0-1

إن حل مشكلة نابساك 0-1 يكمن في الوقت شبه متعدد الحدود. لنفترض أن هي مجموعة أعداد صحيحة موجبة، حدد لتكون أعلى قيمة يمكن الحصول عليها مع مراعاة أن يكون الوزن أقل من أو يساوي باستخدام مواد قد يصل عددها إلى .

بإمكاننا تحديد بشكا متكرر على النحو التالي



• if (تساوي المادة الجديدة أكثر من حد الوزن الحالي)

• if .

من الممكن إيجاد الحل عن طريق حساب . للقيام بذلك بكفاءة يمكننا استخدام جدول لتخزين العمليات الحسابية السابقة.

فيما يلي توضح البرمجية المبدئية للبرنامج الديناميكي

1. // Input

2. // Values (stored in array v)

3. // Weights (stored in array w)

4. // Number of distinct it s (n)


5. // Knapsack capacity (W)

6.

7. for j from 0 to W do

8. m[0, j] 0

9.

10. for i from 1 to n do

11. for j from 0 to W do

12. if w[i-1] > j then
13. m[i, j] m[i-1, j]

14. else

15. m[i, j] max(m[i-1, j], m[i-1, j-w[i-1 + v[i-1])


فإذن سيطبق هذا الحل في وقت ومساحة . بالإضافة إلى ذلك، إذا لم نستخدم سوى مجموعة أحادية الأبعاد لتخزين القيم المثلى الحالية والمرور على هذه المجموعة i+1 مرات، وإعادة الكتابة من ألى كل مرة، فإننا سنحصل على ذات النتيجة لمساحة فقط.

شريط بوابات برمجة الحاسوب معلوماتية رياضيات


تصنيف أبحاث العمليات

تصنيف استمثال توافقي

تصنيف بحوث عمليات

تصنيف برمجة خطية

تصنيف برمجة ديناميكية

تصنيف تعمية

تصنيف خوارزم

تصنيف مسائل NP كاملة
 
التعليقات

لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا

اعلانات
تصنيفات الموقع
شاهد الجديد لهذه المواقع
بئر السبع ميسوكسيمايد تل هشومير المرجة الزرقاء أسامة بن زيد الغاف خطة عمل روبرك الطاقة الداخلية مذكرات دورية نحو الشرق ايو جيما العياضي برباس العياضي شركة مكافحة حشرات خوارزمية ديكسترا مرفأ بيروت الكايد طاش ما طاش شركة كايد البسقلون كورونا سد حراض الفن البيزنطي عبد السلام بنعبد العالي رائد عودة مستشفى طيبة التخصصي غزوة خيبر شركة فواز لعامة للدراسات والمستندات كلوفيس الأول لمع قطع الغيار جميل خطاب ويلان نظم المعلومات المحاسبية محمود بن محمود البان باقادر مؤسسة بن شيهون الصحة الحقن المجهري الصين معلمات معلومات اتجاه البطولي أرضروم تنافسية محمد الحاج سالم تكرلي مبرهنة عدم الاكتمال علاج عرق النسا موقع سنهدريم التكامل العددي كهربا الحكومة الحكومة التونسية مسالك بولية معاهدة فاليتا مستشفي بدر مشاغل مراكز التجميل محمد حافظ الشريدة وديع سعادة مشغل جرافيزم شكا الربان حديقة التجارة نقليات الهباس بن دعجم بطباط حمود بوعلام حميدة معركة ثابسوس براتا البن الاخضر الزكاه ديدفورت تاريخ فواصل الكتب توسعة المسجد النبوي نادي الفتح telnet 1978 عصبام اللوزتين سبيكمان 213 الاقتصاد رمادي عادي فندق العليا تشويه سمعه اسماك الأسماك مؤسسة الجهاز القلبي الوعائي italia قراي
أخبار السعودية اليوم الاثنين 21/01/2019 - أخبار قطر اليوم الاثنين 21/01/2019 - أخبار الإمارات اليوم الاثنين 21/01/2019 - أخبار الكويت اليوم الاثنين 21/01/2019 - أخبار السياحة اليوم الاثنين 21/01/2019 - أخبار البحرين اليوم الاثنين 21/01/2019 - أخبار المغرب اليوم الاثنين 21/01/2019 - أخبار الاردن اليوم الاثنين 21/01/2019 - أخبار فلسطين اليوم الاثنين 21/01/2019 - أخبار عمان اليوم الاثنين 21/01/2019 - أخبار لبنان اليوم الاثنين 21/01/2019 - أخبار السودان اليوم الاثنين 21/01/2019 - أخبار الكورة اليوم الاثنين 21/01/2019 - اعلانات الحراج اليوم الاثنين 21/01/2019 - اسعار السيارات بالكويت الاثنين 21/01/2019 - اسعار العقارات بالكويت الاثنين 21/01/2019