أعلانات الحراج الموتوليز - شارع القطر - السالمية - بجانب فندق لاغونا - مطلوب عمال تحميل وتنزيل في مصنع اسفنج - ستوديو مفروش في حي الخضراء تونس - مكينة ازبري hosk تركية نضيفة - متشي كانتر خمسة دادو - طاوله من ايكيا مستعمله حالتها ممتازه - Toyota Yaris (ref. 1705611) - شارع هايل - لكزس 2005 امريكيه ارغب في البدل ب اكورد 2012 او 2011 او 2010 - شركة سدين للالمنيوم - بطاقة تكافل العربية (خصومات هائلة للمستشفيات) - للبيع بيت - عسل بلدي سدر يمني من صاحب المزرعه - قطع بي ئم بوز نمر - سيارة لانسر 2010 بحالة ممتازة للبيع - العدان ق ظ، شظ¤ظ¤ مظ،ظ§ - ستائر شبه جديدة استخدام 3 سهور - نصراء لتنظيم توزيعات افراح و جلسات رومنسية - زير المدينه الأصلي المضمون حياة الماء الطبيعي - للبيع سيارة تويوتا شاص بالكويت - بيع ركشات بالتقسيط - قولف 3جي تي اي - منقرة كوسا كهربائية - عمارة 3 طوابق مع تسوية - تصفيه كاميرا ارلو الشهيرة للمراقبه جديده البيع بنصف للسعر - للبيع كروزر تنكر - بيع بهارات مبكته - دينمو مرسيدس - دابو كاتم للمولدات الكهربائية 800 ك ف Volvo Cummins Perkins Deutz - Upholsterd Bench Made In Italy M006 - ستانلس ستيل ماركة بونيرا التركي 2017 - مستودع مساحة 499 متر مع 5 غرف تبريد بالإضافة إلى مكتبين للإيجار - All Contracting Maintenance Working Making New&Old All Works Reparing - قطعى ارض للبيع في بوعطني - محرك غسالة و عصارة LG بنت وأمها - مطلوب للبيع عمارات استثمارى - الفروانيه -خيطان - الفنطاس - الفحيحيل - المنقف - المهبوله - ابوحليفه - شاليه للبيع في الريف الاوروبى ك 58 - زير فخار المدينه ومكه الأصلي الفاخر لماء صحي - أجهزة خلوية بالاقساط - تابلت - لاب توب - خلويات اقساط - خلوي بالاقساط - محرك دايو سيلو - Samsung dishwasher 12 place setting, silver color---- - سنس غاليري جيزان امام ساكو - صابونة الافكادوو السحريه ...ومعجوون الممتاز ولفعال100% - للبيع رميثيه - مشرف -الزهراء -الصديق - حطين -السلام - - مفهوم عائلي متكامل للباحثين عن فرصة لتملك شقة في اسطنبول - صباح الناصر - للبيع شقة في حولي موقع مميز موافق لقرض المرأة - بطاقة تكافل العربية للخصم الطبي - ارض للبيع في الجنوب83 المساحة 74دونوم و متر 83$ - Avast! Internet Security 2017 1 year license for PC -
موقع الو بومبارك جابر - مطعم هندي في آخن تندوري انديان - بنك ساب البريطاني - دكتور غازي الصالح - محمد حسونه - الحرس المقدم مطلق المالكي - عطار الحكمه اعشاب - بقاله ق1 - ناصر الحميداني - طبيب محمد الصيدي الإدريسي - خلود الياقوت 7 - خلود الياقوت البنك الوطني فرع شرق - خلود الياقوت الوطني الجابريه - عيادة الدكتور اسامه البكر - لميس - بقالة حبايب العارضية - صيدلية الحياة - بقاله ابرار - مكتب المحامي محمد - ام عبد العزيز البرجس ( عواطف الحوطي) - مكتب خدم .. الفحيحيل - ام صالح تعالج - شاي ساره العجمي للتنحيف - مركز دار لوشي للمساج والتدليك بغداد - دكتور عمر باطوق جده - صدليه حبوب التخسيس - ناجي نمشان - دنبلو - D. Sevn Hass - المحاميه عبير غازي الحداد - د/ سالم خالد القلب - إبراهيم رشيد المفكر التربوي - رشا عنايه - مثنى بامرحول - ضيا الحق افغاني - خيام مضحي النمران - عيادة الدكتور ميثم الصددي - مستشفى است اثيكا بتركيا - د عصام توفيق سلطان - سامي ابو ريان - صيدلية - جمال عطوي - ابو ناصر مكيفات غسان - مكتب خدم - ضياء - ام نايف الفلسطينيه - جراره الرياض - مشعل الغييثات بيت - مصبغة فابرك - نوف البسام الدوام -
الجديد شركة القُصير السعودية لتأجير وبيع الخيـام الأوروبية ومولدات الكهرباء - الصلاة الصلاة - كيف ازرع النعناع في المنزل ؟ - فوائد التمر والحليب - كيف توفر العديد من المال على نفسك ؟ - كيف تبداء بمشروع صغير وناجح ؟ - كيف تصبح غنياً ؟ - كيف توفر المال ؟ -
آخر المشاهدات معاهدة بورتسموث الخلفية - ميزانية و تكاليف ودراسة جدوى مشروع إنتاج عيش الغراب - هاتف و معلومات عن بلدية محافظة المزاحمية بالمملكة العربية السعودية - الحمى المالطيه Brucillosis مرض معدى يتميز بارتفاع في درجة الحرارة - قصة رائعة عن تنمية مهارات اتعبير التحريري لدي الطلاب ذوي صعوبات التعلم - إيرتابينيم الزمرة الدوائية - تقرح حول ظفري أنواع داحس الظفر - كيف تحصل علي المتعة في الحياة الجنسية - بني اسحاق - دافنى روزن - ملف شامل عن البنسلين وفوائده واستخداماته الطبية - هاتف وعنوان الشركة السعودية للأسماك - الحره الشرقيه, المدينة المنورة - هواتف مكتب الضمان الاجتماعى النسوي بالرياض ومعلومات عنها بالسعودية - سدوم ولد انجرتو حياته - طريقة عمل طبخة دجاج محشى بالارز من مطبخ منال العالم - ابن رشيق القيرواني حياته - هاتف وعنوان مكتب عبد الرحمن حمد المقري لإستقدام الأيدي العاملة - البريد, الدمام - [بحث جاهز للطباعة] بحوث تربوية - - [بحث جاهز للطباعة] بحث علمي عن علم الذكاء الصناعي - - هاتف وعنوان مستوصف هجر - الجامعه, الاحساء - رجز (شعر) خصائصه - القليل من الرجال الفاضلين (فيلم) القصة - رافع دحام التكريتي روابط خارجية - هاتف وعنوان مستوصف حسين العلي - الهفوف, الاحساء - مصادر الأفعال الثلاثية وغير الثلاثية والخماسية والسداسية كيفية صياغة المصدر - [بحث جاهز للطباعة] بحث عن حرب 6 اكتوبر 1973 بالصور pdf doc - - مورستان - مصعب بن سعود بن عبد العزيز آل سعود والدته - هاتف وعنوان شركة بن لادن السعودية للإستثمار - الرويس, جدة - الصالون المغربي مكونات الصالون المغربي - لهجة بحرانية لمحة تاريخية - ميزانية و تكاليف ودراسة جدوى مشروع فرز وتدريج الخضار والفاكهة - عدم التوازن بين الدخل و الانفاق - أدولف لوس أشهر اعماله - هاتف وعنوان مكتب الزهير للإستقدام - خميس مشيط, عسير - سنابس (القطيف) أصل التسمية - هواتف مؤسسة عبدالله عطيه زيادي الزهراني للمقاولات ومعلومات عنها بالسعودية - قطب كهربائي القطب الموجب والسالب في الخلية الكهربائية - يا حلوة مع السلامة (أغنية) Bella Ciao - هواتف مستشفى الوجـــه و معلومات عنها فى بتبــــوك بالسعودية - الاعشاب والطب البديل فى علاج علاج قصر القامة وضعف النمو - جسور الهوى - حب في الهند عن المسلسل - هواتف مكتب شركة كايد الإنجاز للتخلص من النفايات الخطرة ومعلومات عنه بالسعودية - عمار بن ياسر نسبه - نظرية القيادة الظرفية أساليب القيادة - تخت شرقي (مسلسل) قصة المسلسل - جيمس دين (ممثل إباحي) حياته المبكرة - الشروط الواجب توفرها للحصول على تأشيرة العمرة من السفارة السعودية بالمغرب - رعاية تجارية بعض أنواع الرعاية - عنوان و هواتف سفارة السعودية فى جمهورية السودان ومعلومات شاملة عنها - قائمة أحياء الدار البيضاء القائمة - غاز التنفس غازات تنفس شائعة للغوص - وصفة هائلة من الطب البديل لعلاج الأكزيما بالاعشاب - جمع كثرة بعض أوزان جمع الكثرة - كيسة الفلح الخيشومي الفيسيولوجيا المرضية - هاتف وعنوان مستشفى رعاية الرياض - طريق خريص, مدينة الرياض - طريقة تحضير الدجاج المكسيكي (المكسيكانو) من الشيف منال العالم - عمارة فائقة التكنولوجيا التأسيس - جون بولبي نظرية التعلق - هواتف مكتب الضمان الاجتماعى ب أبها ومعلومات عنها بالسعودية - ميزانية و تكاليف ودراسة جدوى مشروع ثلاجات التخزين - سيدي عمر (ولاية البيض) أصل التسمية - وصفة من الاعشاب لعلاج مرض الشرى (الارتيكاريا) - هاتف وعنوان شركة الجفالي واخوانه ميشلان - البريد, الدمام - وصفة هائلة من الطب البديل لعلاج القولون بالاعشاب - هواتف مؤسسة بناء الجزيرة للمقاولات ومعلومات عنها بالسعودية - جرائم ذوي الياقات البيضاء قضايا تعريفية - طريقة اعداد الدجاج الملوكي بالذ طعم خطوة بخطوة - وصفة طبيعية من الطب البديل لعلاج قرحة المعدة وحموضة المعده بالاعشاب - اهمية اضافة بذور حبة البركة و الشيح و الزعتر لعلائق الدواجن ودوره في تحسين الانتاج - يحيى العسيري حياته و نشأته و أسرته - نظريات السلوك السياسي المؤثرات طويلة المدى على التوجه السياسي - معلومات هامة عن سلالة دجاج الجميزة - التهاب المريء الفطري بالمبيضات البيض - فحص وظائف الرئة دواعي اختبار وظائف الرئة - نظرية هوفستد للأبعاد الثقافية تاريخ ومنهجية البحث - اختبار دائرة القصر الطريقة - هاتف وعنوان المستشفى الأهلي - خميس مشيط, عسير - هانسل وغريتل ملخص القصة - ابن سهل الأندلسي حياته - هاتف ومعلومات عن مستشفي الأنصار بالمدينة المنورة - محمود غازان الطفولة - تصميم غرفة الصف - قائمة حلقات هجوم العمالقة قائمة الحلقات - روتانا تسجيلات روتانا - نوجاي - طلب تقدير احتياج عمالة بالكويت - طريقة تحضير المحلى بطريقة سهلة - فريديريك فروبل لمحة عن حياته - ميتاميزول كيمياء الميتاميزول - هاتف وعنوان مستوصف دار العلاج - السويدي, مدينة الرياض - قائمة الأسماء المنقوشة على برج إيفل الواجهات الأربع - هاتف وعنوان مطاعم شواية الخليج - المجمع, الدمام - اشهى الشوربات للريجيم والدايت وانقاص الوزن قليلة الدسم والسعرات - قائمة شخصيات سيف النار أهم الشخصيات - الأيدي الناعمة (كتاب) - طريقة تحضير عجينة الكلاج من الشيف منال العالم - طريقة عمل خبز البطاطا الحلوه من مطبخ الشيف منال - علاج القوبــــــاء بالاعشاب - مسافر عبد الكريم تعريف - طريقة عمل الزيتون الاسود على طريقة مدام منال - طريقة عمل وصفة الكيك الاسفنجى على طريقة منال العالم - طريقة طبخ الجريش البحريني بطعم لذيذ لا تفوتك - سور القران لكل شهر من شهور الحمل - أبو بكر غاييغو حياته - الشروط المطلوب استيفاءها للحصول على رخصة تشغيل لشاحنة فردية بالسعودية - مرض وردنج هوفمان - هاتف وعنوان مكتب الباحة للإستقدام - الباحه, الباحة - هاتف وعنوان مستشفى الملك فهد - ابو عريش, جازان - طريقة عمل مرق القرنبيط ولحم الغنم بطريقة سهلة - إدارة المشتريات عملية الشراء - طريقة تنظيف مفاتيح الكهرباء بالصور - تسقية (صناعة) تقسية المعدن بالتسقية - هاتف وعنوان مكتب محمد العبد اللطيف للإستقدام - طريق الملك فهد, محافظات الرياض - طريقة تحضير فاهيتا الدجاج من الشيف منال العالم - طريقة طبخ ايدام الزهره محضر على الطريقة ا لهندية بطعم لذيذ لا تفوتك - مخالفة عودة الوافد المبعد بالمملكة العربية السعودية - طريقة عمل حلى السيجارة لا تفوتك - هواتف مستشفى الملك فهد و معلومات عنها فى بجــــــازان بالسعودية - مبارك الكواري أبنائة - طريقة عمل الكبدة الاسكندرانى من مطبخ منال العالم - مايكوب التاريخ - [مواضيع صحية] افضل دكتور اطفال في الرياض , أفضل طبيب اطفال بالرياض - طب بديل وطب عام - رشيد العبيدي ولادته ونشاته - بانشي (مسلسل) القصة - هاتف و عنوان مستشفى الجبر للعيون والأنف و معلومات عنها بالسعودية - غادة مصلي مشوارها المهني - هاتف وعنوان مركز الدكتور سليمان الغلاييني - السلامه, جدة - سيسبان كبيرة الأزهار أنظر أيضاً - ملف شامل عن الأميبا Amebiasis - نزع الكبريت المهدرج التاريخ - هاتف و عنوان مدرسة ابو بكر بن العربي ثانوي و معلومات عنها بالرياض - [بحث جاهز للطباعة] أروع بحث أدبي عن الشاعر المتنبي - - هاتف وعنوان مطاعم أنعام الإحساء للحفلات - المبرز, الاحساء - هواتف و عناوين وزارة الخارجية - الرياض بالمملكة العربية السعودية - موفق أراكيلي تاريخ موفق أراكيلي - تنميط الجاني تعريفات - إراتوستينس حياته - هواتف مؤسسة بيت الفنون للمقاولات ومعلومات عنها بالسعودية - هاتف ومعلومات عن منتزه السلام الترفيهي (الرياض) بالرياض - [بحث] الأدلة الفائضة ... من ملك الفزلكة ... في فضح الشيعة الرافضة ... (صور كثيرة) و (وثائق) و (ف - ملخصات وتقارير جاهزة للطباعة - فحص سريري خطوات الفحص السريري - ماكينة سحب الهواء (فاكيوم ) - طريقة عمل رز بالتونة يجنن بطعم لذيذ لا تفوتك - هواتف شركة العيوني للإستثمار و المقاولات ومعلومات عنها بالسعودية - أبو حفص الكبير الاسم - [بحث جاهز للطباعة] نموذج مقدمة بحث ادبي , نماذج بحوث ادبية - - طريقة عمل دجاج كندو الصيني بطعم لذيذ لا تفوتكم - هاتف وعنوان مصنع مناديل المعالي - بريده, القصيم - إيريني فادي أعمالها - هيئة تسليح القوات المسلحة (مصر) النشأة - عدد السعرات الحرارية في سمك الشعري والطاقة والقيمة الغذائية - سيارات الأجرة في المغرب النقل الحضري - سونلغاز تاريخها - جودي ستارلينغ الحلقات التي ظهرت فيها - طريقه معرفة نوع الجنين وترجيح المولود القادم بأذن الله - هاتف وعنوان مطعم البيت العربي للمندي - خميس مشيط, عسير - وصفة لعلاج التهاب المفاصل و آلام العضلات بخلطات الاعشاب - وصفات تعمل بالمنزل - هاتف وعنوان مستوصف مستشاري الطبي - بيشه, عسير - طريقة عمل ساندويش الزنجر من مطعم كنتاكي لا تفوتك - هواتف مؤسسة القداح للمقاولات ومعلومات عنها بالسعودية - سليمان الياسين عن حياته - دراسة جدوى مفصلة لمشروع صناعة الطوب الأسمنتي من المخلفات - هاتف وعنوان البراك للأبواب الأتوماتيكية - خميس مشيط, عسير - كيف توفر المال ؟ - وصفة لعلاج التهاب المثانة ومشاكل المجاري البولية بالاعشاب الطبيعية - مؤشرات ميلر البلورية تعريف المستويات - هواتف مستشفى ابن سيناء بحداء و معلومات عنها فى مكة المكرمة بالسعودية - ظاهرية تعريف بالمدرسة الظاهرية - هاتف مركز العريجاء الغربي الصحي بالرياض و معلومات عنه بالسعودية - هاتف وعنوان مستشفى العميس الأهلي - صبيا, جازان - قائمة المخترعين الروس القائمة - تشارلز بيكر المسيرة الفنية - وصفة هائلة من الطب البديل لعلاج النتؤات او الثؤلول او الثلول بالاعشاب - مستذئبو تيارسوليو وصف - هاتف وعنوان مستشفى الوفاء - عنيزه, القصيم - طريقة عمل دبس التمر بالصور - تعريف النص الوصفي - هاتف مركز المعابدة الصحي بمكة المكرمة و معلومات عنه بالسعودية - اشرف سيد احمد الكاردينال مولده ونشاته - متحف السويداء الوطني لمحة تاريخية - هواتف شركة بدون حفر للمقاولات ومعلومات عنها بالسعودية - البرتي أصل قبيلة البرتي - حق ارتفاق (أنواع حقوق الارتفاق ) - وصفة هائلة من الطب البديل لعلاج النحافه و فقر الدم وضعف الجسم بالاعشاب - طريقة عمل طبخة القدره الخليليه من مطبخ منال العالم - هواتف مؤسسة رفيق ابن عبدالقادر ابن سليم كريديه للمقاولات ومعلومات عنها بالسعودية - مزايا أن تكون خجولا (رواية) الأدب - هاتف وعنوان مستوصف دار الحكمة - منفوحه, مدينة الرياض - هاتف وعنوان مستوصف النجوم - الناصريه, مدينة الرياض - طريقة عمل وصفة حلو ست الحسن بطعم لذيذ لا تفوتك - صعود المطر (فيلم) - الأعشاب المستخدمة فى تضييق المهبل - هاتف وعنوان مطعم الرمال الشعبي - الفيصليه, نجران - الة المشي البشرية - مطار الملك خالد الدولي صالات السفر - باراسيتامول التاريخ - تحدب قطني زائد السبب - اسباب الاستسقاء الكلوي و تضخم الكليتين عند الجنين و عند الطفل - قضيب (عضو ذكري) في الحيوانات المختلفة -
اليوم: الثلاثاء 23 اكتوبر 2018 , الساعة: 1:19 م / اسعار صرف العملات ليوم الثلاثاء 23/10/2018


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


مسألة البائع المتجول تعريف

نشر قبل 2 سنة و 1 شهر 256 مشاهدة


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

تعريف


ليكن G (V,A) مبيان مخطوطا حيث تمثل V مجموعة الرؤوس (vertices) و-A مجموعة الأضلاع (edges). ولتكن C (c_ ij ) مصفوفة الأوزان أو الأطوال أي أنه c_ ij هو الوزن الذي على الضلع الذي بين i و- j أو طول الضلع. ومسألة البائع المتجول حينها تسأل اذا ما هناك دائرة تعبر في كل رأس مرة واحدة فقط حيث أن وزن الدائرة اقل ما يمكن ؟

ملاحظات



  • تسمى الدائرة التي نريدها دائرة هاملتونية

  • في بعض المسائل سيتعين علينا أن نميز بين مصفوفة أطوال متناظرة اي forall i,j in V, c_ ij c_ ji وبين مصفوفة غير متناظرة

  • خاصية غير الزامية للمصفوفة C هي خاصية متباينة المثلث وهي forall i,j,k in V , c_ ij +c_ jk ge c_ ik


وهذه الخاصية تتبين في مسألة البائع المتجول الاقليدية اي عندما تكون الرؤوس نقاط في mathbb R ^2 والاطوال بين الرؤوس اي اطوال الأضلاع هو البعد الاقليدي اي انه اذا v (x_1,y_1) , u (x_2,y_2) حينها طول الضلع uv هو d_ uv sqrt (x_1-x_2)^2+(y_1-y_2)^2

NP كاملة


لقد تبين ان مسألة البائع المتجول هي مسألة كاملة بالنسبة ل-NP , بحيث انه يوجد دالة تحويل او اختصار (reduction function) بين الحد الأدنى للدائرة الهاملتونية وهذه المسألة

لنفرض انه معطى معنا مُدخل لمسألة الدائرة الهاملتونية(HC) نريد ان نبني اختصار بوقت حدودي والمُدخل لمسألة HC هو مُخطط G (V,A) بحيث ان V 1,...,n ,A (i,j) نبني مُدخل لمسألة TSP بالشكل التالي نبني مُخطط G , بحيث ان مجموعة الرؤوس هي V اما مجموعة الأضلاع هي A' (i,j) i,j 1,...,n,i
eq j و c_ ij 1 اذا (i,j) in A و- c_ ij infty
في سائر الأحوال , وحينها المخطط G يحوي دائرة هاملتونية اذا وفقط اذا قيمة مُدخل TSP هي n

مسائل TSP سهلة



  1. اذا كانت مصفوفة الأطوال مصفوفة مثلثة عُلوية اي forall i ge j , c_ ij 0

  2. اذا كان المخطط , G , شجرة او مسار او دائرة او نجمة حينها أيضا يمكن حل المسألة بسهولة

  3. نعرف مصفوفة C ان تكون صغيرة اذا forall i in 1,...,n ,exists a_i,b_i c_ ij min a_i,b_j forall i,j in [n] حينها اذا كانت مصفوفة الأطوال صغيرة يمكن حل المسألة بوقت O(n)


خوارزميات دقيقة لحل المسألة


الحل المفهوم ضمنا وهو انتاج كل المسارات الدائرية ثم اختيار الأفضل هو حل غير قابل للتشغيل بسرعة إذ ان تعقيده O(n!) واذا كان فقط n 60 حينها سيكون هنالك احتمالات اكثر من ان نستطيع ان ننتجها(حدود الطاقة الحسابية للبشر على مر العصور هو 2^ 80 وهذا العدد اصغر بكثير من 60! ) ولان الحل الجشع لا يمكن انتاجه بجودة عالية وسرعة ملائمة تم تطوير الكثير من الوسائل لحل المسألة وسنعدد بعضها

البرمجة الخطية


طور فلكرسون وجونسون ودانتزيج هذه الطريقة وهي لكل ضلع في المخطط نخصص متغير x_ ij وهو 1 اذا وفقط اذا الضلع من ضمن الحل الأفضل للمسألة وقد كان تعريف مسألة البرمجة الخطية كالتالي

sum_ i
eq j c_ ij x_ ij Minimize



Subject to





  1. sum_ j 1 ^n x_ ij 1 ,i 1,...,n


  2. sum_ i 1 ^n x_ ij 1 ,j 1,...,n


  3. sum_ i,jin S ^n x_ ij leq S -1,Ssubset V ,2 le S le n-2


  4. x_ ij in 0,1 ,i,j 1,...,n,i
    eq j



توضيحات



  1. من الواضح ان دالة الهدف هي مقياس لوزن الدائرة التي نريد ايجادها , وذلك لان كل x_ ij يمكن ان يكون 1 او 0 , اي ان ضلع يمكن ان تكون بالحل وبالتالي نضيف وزنها (وحينها x_ ij 1 ) او يمكن الا يكون بالحل ثم بالتالي x_ ij 0 اي انه لن نحسب وزن الضلع .

  2. القيود(Constraints) في السطر 1+2 هي تحدد ان كل رأس (vertex) نستخدمه مرة واحدة في الحل اي ان لكل رأس درجة الخروج ودرجة الدخول اليه على الاكثر 1 .

  3. اما القيد 3 فهو يدعى الغاء المسارات الدائرية القصيرة اي مسارات دائرية بطول اقل من n , وذلك لانه اذا كان هناك مسار دائري أقصر من n على مجموعة جزئية S من الرؤوس حينها سيحوي هذا المسار الدائري على S اضلاع , وحينها القيد 3 لن يتحقق لذا لا يمكن ان نجد حلا أقصر من المرغوب به , وانتبه أيضا ان مسار دائري بطول 1 لا يمكن ان يكون حلا وذلك حسب قيود 1+2 (وبالتالي كذلك ل-n-1) لذا فانه مسموح وضع القيد 2 le S le n-2

  4. اما القيد الأخير فهو لبيان ان كل ضلع يمكن ان تكون بالحل الأمثل او لا اذا كان الضلع في الحل حينها يكون قيمة المتغير 1 وخلاف ذلك 0 .

  5. يمكن استبدال قيد 3 بالقيد التالي sum_ i in S sum_ j in overline S x_ ij ge 1 , S subset V,2 le S le n-2



لحل هذه المسألة الخطية يمكن استخدام اي وسيلة لحل المسائل الخطية على الاعداد الكاملة ولكن هذه الخوارزمية لا يمكن ان تحله بوقت حدودي إذ انه يوجد n(n-1) متغيرات و- 2n قيود درجة (1+2) و 2^n-2n-2 قيود على طول المسارات (3) لذا فانه لا يمكن حلها بشكل مباشر ما يحتم علينا استخدام طرق اخرى .

لتخفيف كمية القيود كانت هناك حاجة لتغيير هذه البرمجة الخطية واستبدالها بمسألة خطية اخرى مع كمية قيود اقل وقد كان هذا وسميت البرمجة الخطية MTZ على أسماء كاتبيها . وكان الحل باضافة متغيرات اضافية




  1. u_i-u_j+(n-1)x_ ij le n-2 , forall i,j in 2,...,n ,i
    eq j

  2. 1 le u_i le n-1 , forall i in 2,...,n



توضيح



  1. القيد الأول منهما لضمان انه لا يوجد مسار دائري جزئي على المجموعات الجزئية S subseteq V setminus 1 لذا فانه لا يوجد مسارات دائرية جزئية طولها اقل من n

  2. القيد الثاني يضمن ان كل u_i معرف بشكل واحد ووحيد لكل حل ممكن .



ملاحظات



  1. تبين ان البرمجة الخطية MTZ اضعف من البرمجة الاولى لانه تم برهنة انه في بعض الحالات القيمة التي يمكن ان ينتجها MTZ تكون اقل منها في البرمجة الاولى .

  2. يمكن تقوية MTZ باضافة u_i-u_j+(n-1)x_ ij +(n-3)x_ ij le n-2 , forall i,j in 2,...,n ,i
    eq j بدل القيد الأول .



فرق تسد(Branch and Bound)


يمكن استخدام هذه الوسيلة لحل مسألة البائع المتجول (TSP) . في مجال البرمجة الرياضياتية يمكن النظر إلى هذه الوسيلة من الجهة التالية اولا تخفيف بعض القيود ثم اخذ الناتج وحله بطريقة سريعة وجيدة . حينها جودة وسيلة فرق تسد تكون من كمية الحد الأقصى لكل مجموعة قيود نقصيها . اما بالنسبة لمسألة TSP بداية يمكن تخفيف قيود 3 وارجاء باقي القيود والتي تشكل معا مسألة التلائم(assignment probl ) والتي يمكن حلها بشكل دقيق بوقت O(n^3) لذا فان القيمة السفلى لمسألة البائع المتجول هي مسألة التلائم سوف نستخدم هذه المسألة لنركب خوارزمية بطريقة فرق تسد


سوف نستخدم الامور التالية



  1. z^* أفضل قيمة ل TSP وجدناها حتى اللحظة .

  2. z_h قيمة دالة الهدف لمسألة التلائم(AP) في الرأس h في شجرة البحث ,

  3. underline z_h قيمة سُفلى ل- z_h

  4. I_h مجموعة الأضلاع ضمن الحل في الرأس h من شجرة البحث

  5. E_h مجموعة الأضلاع التي ليست ضمن الحل في الرأس h من شجرة البحث



الخوارزمية


الخطوة 1 (الابتداء) حصِّل على قيمة اولية ل- z^* بمعنى ان نستخدم طريقة حدس مهني الحدس المهني (Heuristic) توصلنا للحل , ابدأ في الرأس 1 من شجرة البحث و I_h E_h ptyset واحصل على z_1 بحل المسألة AP , اذا z_1 ge z^* توقف الحدس المهني يعطي الحل الأمثل . واذا حل AP لا يحوي مسارات جزئية دائرية توقف لانه يعطي الحل الأمثل . خلاف هذا ضع 1 في طابور



الخطوة 2 (اختيار الرأس (vertex)) اذا الطابور فارغ , توقف . خلاف هذا اختر رأس (vertex) من الطابور .



الخطوة 3 (تقسيم المسألة الجزئية) الحل الموجود في الرأس h هو حل غير جائز ويجب ازالته بتقسيم المسألة الحالية لمسائل متجاورة h_r التي تتميز بالمجموعتين I_ h_r و- E_ h_r . وحتى نُنتج هذه التقسيمات , فليكن مسار دائري جزئي يحيث انه على الاقل s اضلاع لا تحويها I_ h لنفرض ان هذه الأضلاع هي (i_1,j_1),...,(i_s,j_s) حسب الترتيب التي تظهر في المسار الجزئي وحينها انتج s مسائل جزئية عندما



I_ h_r
egin cases


I_ h_r ,mbox r 1 \


I_h cup (i_u,j_u) u 1,...,r-1 ,r 2,...,s

end cases



E_ h_r E_h cup (i_r,j_r) , r 1,...,s


نفذ الخطوات 4 حتى 6 لكل r 1,...,s


الخطوة 4 احسب حد اسفل underline z_h ل-z_h عن طريق تخفيض عامود وسطر من مصفوفة الأوزان واذا underline z_h le z^* اكمل للخطوة 5 خلاف هذا اعد الخطوة 4 عندما r r+1 .



الخطوة 5 حل المسألة الجزئية التي في h_r واذا z_ h_r ge z^* عد إلى 4 عندما r r+1 .



الخطوة 6 افحص اذا ما الحل الحالي يحوي على مسائل جزئية اذا كان كذلك ضع h_r في الطابور خلاف هذا z^* z_ h_r احفظ المسار واذا z^* z_h اذهب إلى 2 .



خوارزميات تقريب


وهي خوارزميات لا تعطي جواب دقيق ولكنها تعطينا جواب لنفرض انه S ونفرض انه *S هو الحل الأمثل حينها alpha frac S S^* ,هو البعد عن الجواب الأمثل . للاسف لمسألة البائع المتجول لا يوجد خوارزميات تقريب سريعة الا اذا NP P , وهذا لانه اذا كان هناك واحدا كهذا فهو حتما سوف يحل مسألة المسار الدائري الهاملتوني , والأسوأ من هذا انه حتى اذا alpha O(2^n) سينتج عن هذا ان NP P !
بالرغم من هذا فان مسألة البائع المتجول مع خاصية متباينة المثلثات (او مسألة البائع المتجول المترية) يوجد لها خوارزميات تقرب الاجابة المثلى لذا سوف ننظر اولا لم لا يمكن تقريب TSP بشكل عام ثم نقرب TSP مع خاصية متباينة المثلثات

صعوبة تقريب TSP


نظرية لكل دالة يمكن حسابها بوقت حدودي alpha(n) , مسألة البائع المتجول لا يمكن تقريبها بمعامل alpha(n) الا اذا NP P .



برهان لنفرض من اجل التناقض ان هناك خوارزمية حدودية تقرب TSP بمعامل alpha(n) سنسميه mathcal A سوف نُري انه يمكن استخدام mathcal A لكي نقرر مسألة المسار الدائري الهاملتوني ( حينها NP P ) .



الفكرة المركزية هي اختصار مسألة المسار الهاملتوني الدائري لمسألة البائع المتجول اي انه باعطائنا G نريد بناء مخطط كامل مع اوزان 'G بحيث أنَّ


1- اذا G يوجد فيه مسار دائري هاملتوني حينها في 'G وزن حل مسألة البائع المتجول الأمثل هو n .


2- اذا G لا يوجد فيه مسار دائري هاملتوني حينها في 'G وزن حل مسألة البائع المتجول الأمثل هو اكثر من alpha(n) n

لاحظ انه عندما نشعل الخوارزمية mathcal A على المخطط 'G على الخوارزمية ان تعطينا جوابا على الاكثر alpha(n) n في الحالة الاولى وفي الحالة الثانية جواب قيمته أكبر من alpha(n) n لذا يمكن تقرير مسألة المسار الدائري الهاملتوني .

والاختصار هو كالتالي لكل ضلع من اضلاع G ضع وزن 1 , وكل الأضلاع ليست اضلاع ل-G وزنها هو alpha(n) n وهذا سوف يكون 'G .

يمكن ان نرى انه اذا في G يوجد مسار دائري هاملتوني حينها وزن TSP في 'G هو n , اما اذا G لم يحوِ مسار دائري هاملتوني فعليه استخدام ضلع واحدة على الاقل وزنها alpha(n) n لذا فان وزن TSP يكون اكثر من alpha(n) n

تقريب مسألة البائع المتجول المترية


الخوارزمية




  1. جد الشجرة الممتدة ذات الحد الأدنى (MST) ولنسمها T .

  2. ضاعف كل ضلع في T واحصل على مخطط اويلراني

  3. جد مسار اويلراني mathcal T

  4. اخرج المسار الذي رؤوس G حسب ترتيب ظهورها في mathcal T . فلنسم المسائر الدائري الناتج C .



يمكن البرهنة بأن معامل هذه الخوارزمية هو 2 . يمكن تحسين هذه النتيجة ل-frac32 باستخدام مسألة التلائم في المخططات والخوارزمية الناتجة تكون جدا مشابهة للموصفة اعلاه.

GLPK solution of a travelling salesman probl .svg حلحلة لمعضلة البائع المتجول



مسألة البائع المتجول إنك Travelling salesman probl هي إحدى أهم المسائل في علم التعقيد الحسابي و نظرية المخططات ، ونص المسألة هو وصل تاجر إلى دولة فيها n مدينة ويريد البائع أن يزور كل مدينة في الدولة مرة واحدة فقط وبأقل وقت سفر بين المدن. بالرغم من بساطة عرض المسألة فقد تبين أن هذه المسألة هي أحد المسائل التي لا يُعرف لها خوارزمية تحلها بسرعة, أي أنه اذا كان هناك فقط 50 مدينة حينها يتطلب الأمر أكثر من ألف عام لايجاد الحل ! وقد وجدت هذه المسألة طريقها لنظرية التعقيد الحسابي حين أدرجها ريتشارد كارب كارب في قائمته ال-21 لمسائل NP كاملة.



تاريخ

تم الاشارة للمسألة للمرة الأولى في ألمانيا عام 1832 في كتاب البائع المتجول الناجح وكان كارل منجر هو أول رياضياتي كتب عن المسألة حيث أنه أراد l(C) حيث ان C هو مسطح بسيط في الفضاء المتري S وحسب التعريف هو
l(C) supsum_ i 1 ^ n-1 dist(x_i,x_ i+1 )
عندما القيم العُلية(supr um) نأخذها على كل اختيار x_1,x_2,...,x_ n-1 على C حسب < >الترتيب الذي يضعه C, وما بينه منجر لحل هذه المسألة هو أننا نستطيع أن نفحص كل المجموعات الجزئية النهائية X ل-C اي exists n in mathbb N Xsubset C, X n وعندها نأخذ القيمة الدنيا لكل الترتيبات X . لذا عرف لكل مجموعة جزئية X, لفضاء متري S lambda(X) وهو طول المسار الأقصر الذي يمر من خلال , وقد برهن التالي


l(c) sup_ X lambda(X)
كما حاول أن يبرهن أن forall epsilon > 0, exists Xsubset C lambda(X) ge l(C)
ونجح ببرهنة ميرهنة أقوى

l(c) sup_ X kappa(X)
عندما kappa(X) هو الحد الأدنى شجرة (بنية بيانات) للشجرة المتتدة في X .
نرى أأن lambda(X) قريب جدا من مسألة البائع المتجول, وقد ذكر منجر هذه الصلة في عام 1930 في أحد محاضراته وحسب الوثائق في البداية سأل منجر اذا ما نستطيع أن نستبدل kappa(X) بالحد الأدنى لشجرة ستاينير التي توصل X. وللمسألة الاقليدية تم ايجاد الحل في عام 1933 .
بين الأعوام 1930-1931 امضى منجر في هارفرد كمحاضر زائر وفي أحد محاضراته بيَّن نتاجه التي عرضناها واحد الاقتراحات كانت من هاسلر ويتني وبعدها بعام ذكر هاسلر مسألة العبور على ال48 ولاية .

وفي عام 1940 ظهرت مقالات تدرس مسألة البائع المتجول في سياق مُختلف , ميلجرام في عام 1940 درس مسألة المسار الاقصر خلال مجموعة من النقاط في الفضاء المتري وقد درس هذه المسألة على مسطح جوردان الأدنى والتي تُغطي اي مجموعة من النقاط في الفضاء المتري وليست بالضرورة مجموعة نهائية والتي حينها المسار الاقصر قد لا يكون موجودا . اما فيجيس في نفس العام درس المسألة في مربع الوحدة وقد توصل فيربولونسكي إلى ان طوله اقل من 2+sqrt 2.8 n
وقد اعطى ماهلانوبيس حدود دنيا للطول المتوقع ل-n نقاط عشوائية وقد اكمل هذا البحث جيسين عام 1942 .

وفي اخر الاربعينات وبداية الخمسينات ميلر فلود وقد كان في مؤسسة راند وهي مؤسسة بُحوث علمية حاول حلها بمساعدة علماء المؤسسة ولكن عبثا , وتم رصد جائزة لمن يساعد في حل المسألة(المسألة قد لا يوجد لها خوارزمية سريعة )

في عام 1954 اصدر فولكرسون وجونسون ودانتزيج مقال مهم في هذه المسألة وقد تطرقوا لخوارزميات لحل المسألة وقد اصبحت اساسية لاحقا في مسائل الاستمثال (combinatorial optimization )وقد استخدموا فيها المستويات القاطعة وبمساعدة البرمجة الخطية وطريقة السيمبلكس نجحوا في حل المسألة ل-49 ولاية . ولاحقا برهن كارب ان المسألة هي NP كاملة ومن حينها طور العلماء كثير من الطرق لحل المسألة بشكل مباشر مثل البرمجة الخطية المختلطة وخوارزميات جينية ...
 
التعليقات

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

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