كتب accurate problem solving algorithms
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
خوارزميات دقيقة لحل المسألة (معلومة)
الحل المفهوم ضمنا وهو انتاج كل المسارات الدائرية ثم اختيار الأفضل هو حل غير قابل للتشغيل بسرعة إذ ان تعقيده وإذا كان فقط n=60 حينها سيكون هنالك احتمالات أكثر من ان نستطيع ان ننتجها(حدود الطاقة الحسابية للبشر على مر العصور هو وهذا العدد اصغر بكثير من ) ولان الحل الجشع لا يمكن انتاجه بجودة عالية وسرعة ملائمة تم تطوير الكثير من الوسائل لحل المسألة وسنعدد بعضها :
البرمجة الخطية
طور فلكرسون وجونسون ودانتزيج هذه الطريقة وهي : لكل ضلع في المخطط نخصص متغير وهو 1 إذا وفقط إذا الضلع من ضمن الحل الأفضل للمسألة وقد كان تعريف مسألة البرمجة الخطية كالتالي :
: Minimize
: Subject to
توضيحات :
- من الواضح ان دالة الهدف هي مقياس لوزن الدائرة التي نريد ايجادها، وذلك لان كل يمكن ان يكون 1 أو 0 , اي ان ضلع يمكن ان تكون بالحل وبالتالي نضيف وزنها (وحينها ) أو يمكن الا يكون بالحل ثم بالتالي اي انه لن نحسب وزن الضلع .
- القيود(Constraints) في السطر 1+2 هي تحدد ان كل رأس (vertex) نستخدمه مرة واحدة في الحل اي ان لكل رأس درجة الخروج ودرجة الدخول اليه على الأكثر 1 .
- اما القيد 3 فهو يدعى "إلغاء المسارات الدائرية القصيرة" اي مسارات دائرية بطول اقل من n , وذلك لانه إذا كان هناك مسار دائري أقصر من n على مجموعة جزئية S من الرؤوس حينها سيحوي هذا المسار الدائري على اضلاع، وحينها القيد 3 لن يتحقق لذا لا يمكن ان نجد حلا أقصر من المرغوب به، وانتبه أيضا ان مسار دائري بطول 1 لا يمكن ان يكون حلا وذلك حسب قيود 1+2 (وبالتالي كذلك ل-n-1) لذا فانه مسموح وضع القيد :
- اما القيد الأخير فهو لبيان ان كل ضلع يمكن ان تكون بالحل الأمثل أو لا : إذا كان الضلع في الحل حينها يكون قيمة المتغير 1 وخلاف ذلك 0 .
- يمكن استبدال قيد 3 بالقيد التالي :
لحل هذه المسألة الخطية يمكن استخدام اي وسيلة لحل المسائل الخطية على الاعداد الكاملة ولكن هذه الخوارزمية لا يمكن ان تحله بوقت حدودي إذ انه يوجد متغيرات و- قيود درجة (1+2) و قيود على طول المسارات (3) لذا فانه لا يمكن حلها بشكل مباشر ما يحتم علينا استخدام طرق اخرى .
لتخفيف كمية القيود كانت هناك حاجة لتغيير هذه البرمجة الخطية واستبدالها بمسألة خطية اخرى مع كمية قيود اقل وقد كان هذا وسميت البرمجة الخطية MTZ على أسماء كاتبيها . وكان الحل باضافة متغيرات اضافية :
توضيح :
- القيد الأول منهما لضمان انه لا يوجد مسار دائري جزئي على المجموعات الجزئية : لذا فانه لا يوجد مسارات دائرية جزئية طولها اقل من n
- القيد الثاني يضمن ان كل معرف بشكل واحد ووحيد لكل حل ممكن .
ملاحظات :
- تبين ان البرمجة الخطية MTZ اضعف من البرمجة الاولى لانه تم برهنة انه في بعض الحالات القيمة التي يمكن ان ينتجها MTZ تكون اقل منها في البرمجة الاولى .
- يمكن تقوية MTZ باضافة : بدل القيد الأول .
التفريع والتحديد(Branch and Bound)
يمكن استخدام هذه الوسيلة لحل مسألة البائع المتجول (TSP) . في مجال البرمجة الرياضياتية يمكن النظر إلى هذه الوسيلة من الجهة التالية: اولا تخفيف بعض القيود ثم اخذ الناتج وحله بطريقة سريعة وجيدة . حينها جودة وسيلة فرق تسد تكون من كمية الحد الأقصى لكل مجموعة قيود نقصيها . اما بالنسبة لمسألة TSP بداية يمكن تخفيف قيود 3 وارجاء باقي القيود والتي تشكل معا مسألة التلائم(assignment problem) والتي يمكن حلها بشكل دقيق بوقت لذا فان القيمة السفلى لمسألة البائع المتجول هي مسألة التلائم سوف نستخدم هذه المسألة لنركب خوارزمية بطريقة فرق تسد : سوف نستخدم الامور التالية :
- : أفضل قيمة ل TSP وجدناها حتى اللحظة .
- : قيمة دالة الهدف لمسألة التلائم(AP) في الرأس h في شجرة البحث ,
- : قيمة سُفلى ل-
- مجموعة الأضلاع ضمن الحل في الرأس h من شجرة البحث
- مجموعة الأضلاع التي ليست ضمن الحل في الرأس h من شجرة البحث
الخوارزمية :
الخطوة 1 : (الابتداء) حصِّل على قيمة اولية ل- بمعنى ان نستخدم طريقة الحدس المهني (Heuristic) توصلنا للحل، ابدأ في الرأس 1 من شجرة البحث و: واحصل على بحل المسألة AP , إذا توقف: الحدس المهني يعطي الحل الأمثل . وإذا حل AP لا يحوي مسارات جزئية دائرية توقف لانه يعطي الحل الأمثل . خلاف هذا : ضع 1 في طابور
الخطوة 2 : (اختيار الرأس (vertex)) إذا الطابور فارغ، توقف . خلاف هذا اختر رأس (vertex) من الطابور .
الخطوة 3 : (تقسيم المسألة الجزئية) الحل الموجود في الرأس h هو حل غير جائز ويجب ازالته بتقسيم المسألة الحالية لمسائل متجاورة التي تتميز بالمجموعتين و- . وحتى نُنتج هذه التقسيمات، فليكن مسار دائري جزئي يحيث انه على الاقل s اضلاع لا تحويها لنفرض ان هذه الأضلاع هي : حسب الترتيب التي تظهر في المسار الجزئي وحينها انتج s مسائل جزئية عندما :
نفذ الخطوات 4 حتى 6 لكل r=1,...,s
الخطوة 4 : احسب حد اسفل ل- عن طريق تخفيض عامود وسطر من مصفوفة الأوزان وإذا اكمل للخطوة 5 خلاف هذا اعد الخطوة 4 عندما r=r+1 .
الخطوة 5 : حل المسألة الجزئية التي في وإذا عد إلى 4 عندما r=r+1 .
الخطوة 6 : افحص إذا ما الحل الحالي يحوي على مسائل جزئية إذا كان كذلك ضع في الطابور خلاف هذا : احفظ المسار وإذا اذهب إلى 2 .
