حل مسألة البائع المتجول (الحل)?
حل مسالة البائع المتجول :
بإعتبار 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 , بحيث انه يوجد دالة تحويل او اختصار (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 سهلة
- اذا كانت مصفوفة الأطوال مصفوفة مثلثة عُلوية اي forall i ge j , c_ ij 0
- اذا كان المخطط , G , شجرة او مسار او دائرة او نجمة حينها أيضا يمكن حل المسألة بسهولة
- نعرف مصفوفة 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
- sum_ j 1 ^n x_ ij 1 ,i 1,...,n
- sum_ i 1 ^n x_ ij 1 ,j 1,...,n
- sum_ i,jin S ^n x_ ij leq S -1,Ssubset V ,2 le S le n-2
- x_ ij in 0,1 ,i,j 1,...,n,i
eq j
