مشكلة بائع السفر: Python, C++ خوارزمية

ما هي مشكلة البائع المتجول (TSP)؟

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

يقدم بيان المشكلة قائمة بالمدن بالإضافة إلى المسافات بين كل مدينة.

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

مثال على TSP

يتم هنا تقديم رسم بياني حيث تمثل 1 و2 و3 و4 المدن، ويمثل الوزن المرتبط بكل حافة المسافة بين تلك المدن.

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

بالنسبة للرسم البياني أعلاه، فإن المسار الأمثل هو اتباع مسار الحد الأدنى للتكلفة: 1-2-4-3-1. وهذا الطريق الأقصر سيكلف 10+25+30+15 =80

حلول مختلفة لمشكلة البائع المتجول

تُصنف مشكلة بائع السفر (TSP) على أنها مشكلة صعبة من نوع NP نظرًا لعدم وجود خوارزمية زمنية متعددة الحدود. تزداد التعقيدات بشكل كبير مع زيادة عدد المدن.

هناك طرق متعددة لحل مشكلة البائع المتجول (tsp). بعض الحلول الشائعة هي:

نهج القوة الغاشمة هو الأسلوب الساذج لحل مشاكل البائع المتجول. في هذا النهج، نقوم أولاً بحساب جميع المسارات الممكنة ومن ثم مقارنتها. عدد المسارات في الرسم البياني الذي يتكون من n المدن هو n! يعد حل مشكلة البائع المتجول باتباع نهج القوة الغاشمة هذا أمرًا مكلفًا للغاية من الناحية الحسابية.

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

سيوضح هذا البرنامج التعليمي أسلوب البرمجة الديناميكي، وهو الإصدار المتكرر لأسلوب التفرع والربط، لحل مشكلة البائع المتجول.

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

التعقيد الحسابي لهذا النهج هو يا(ن^2*2^ن) والتي سيتم مناقشتها لاحقًا في هذه المقالة.

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

خوارزمية لمشكلة البائع المتجول

سوف نستخدم منهج البرمجة الديناميكية لحل مشكلة البائع المتجول (TSP).

قبل البدء في الخوارزمية، دعونا نتعرف على بعض المصطلحات:

رسم بياني G=(V, E)، وهو عبارة عن مجموعة من القمم والحواف.
V هي مجموعة القمم.
E هي مجموعة الحواف.
ترتبط القمم من خلال الحواف.
يشير Dist(i,j) إلى المسافة غير السالبة بين قمتين، i وj.

لنفترض أن S هي مجموعة فرعية من المدن وتنتمي إلى {1، 2، 3، …، n} حيث 1، 2، 3…n هي المدن وi، j مدينتان في تلك المجموعة الفرعية. الآن يتم تعريف التكلفة (i، S، j) بطريقة مثل طول أقصر مسار لزيارة العقدة في S، والتي تكون بالضبط ذات نقطة البداية والنهاية مثل i و j على التوالي.

على سبيل المثال، تشير التكلفة (1، {2، 3، 4}، 1) إلى طول أقصر مسار حيث:

مدينة البداية هي 1
تتم زيارة المدن 2 و3 و4 مرة واحدة فقط
نقطة النهاية هي 1

خوارزمية البرمجة الديناميكية ستكون:

حدد التكلفة (i, , i) = 0، مما يعني أننا نبدأ وننتهي عند i، والتكلفة هي 0.
عندما |س| > 1، نحدد التكلفة(i, S, 1) = ∝ حيث i !=1 . لأننا في البداية لا نعرف التكلفة الدقيقة للوصول من المدينة i إلى المدينة 1 عبر مدن أخرى.
الآن، علينا أن نبدأ من الساعة 1 ونكمل الجولة. نحن بحاجة إلى اختيار المدينة القادمة بهذه الطريقة-

التكلفة (i، S، j) = التكلفة الدنيا (i، S− {i}، j)+dist(i,j) حيث i∈S وi≠j

بالنسبة للشكل المعطى، ستكون مصفوفة التجاور على النحو التالي:

حي (ط، ي)	1	2	3	4
1	0	10	15	20
2	10	0	35	25
3	15	35	0	30
4	20	25	30	0

دعونا نرى كيف تعمل الخوارزمية لدينا:

الخطوة 1) نحن نفكر في أن تبدأ رحلتنا من المدينة رقم 1، ونقوم بزيارة مدن أخرى مرة واحدة ثم نعود إلى المدينة رقم 1.

الخطوة 2) S هي مجموعة فرعية من المدن. وفقًا لخوارزميتنا، لجميع |S| > 1، سنضبط تكلفة المسافة (i, S, 1) = ∝. هنا تعني cost(i, S, j) أننا نبدأ من المدينة i، ونزور مدن S مرة واحدة، والآن نحن في المدينة j. نضبط تكلفة هذا المسار على أنها لا نهائية لأننا لا نعرف المسافة بعد. لذا ستكون القيم على النحو التالي:

التكلفة (2، {3، 4}، 1) = ∝ ؛ يشير الرمز إلى أننا نبدأ من المدينة 2، ونمر عبر المدن 3، 4، ونصل إلى 1. وتكلفة المسار هي ما لا نهاية. بصورة مماثلة-

التكلفة (3، {2، 4}، 1) = ∝

التكلفة (4، {2، 3}، 1) = ∝

الخطوة 3) الآن، بالنسبة لجميع المجموعات الفرعية من S، نحتاج إلى إيجاد ما يلي:

التكلفة (i، S، j) = التكلفة الدنيا (i، S− {i}، j)+dist(i,j)، حيث j∈S وi≠j

وهذا يعني الحد الأدنى لمسار التكلفة للبدء من i، والمرور عبر مجموعة المدن الفرعية مرة واحدة، والعودة إلى المدينة j. مع الأخذ في الاعتبار أن الرحلة تبدأ من المدينة 1، فإن تكلفة المسار الأمثل ستكون = التكلفة (1، {مدن أخرى}، 1).

فلنكتشف كيف يمكننا تحقيق ذلك:

الآن S = {1، 2، 3، 4}. هناك أربعة عناصر. وبالتالي فإن عدد المجموعات الفرعية سيكون 2^4 أو 16. هذه المجموعات الفرعية هي-

1) |س| = فارغة:

{Φ}

2) |س| = 1:

{{1}, {2}, {3}, {4}}

3) |س| = 2:

{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

4) |س| = 3:

{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}

5) |س| = 4:

وبما أننا نبدأ من 1، يمكننا تجاهل المجموعات الفرعية التي تحتوي على المدينة 1.

حساب الخوارزمية:

1) |س| = Φ:

التكلفة (2، Φ، 1) = التوزيعة (2، 1) = 10

التكلفة (3، Φ، 1) = التوزيعة (3، 1) = 15

التكلفة (4، Φ، 1) = التوزيعة (4، 1) = 20

2) |س| = 1:

التكلفة (2، {3}، 1) = التوزيعة (2، 3) + التكلفة (3، Φ، 1) = 35+15 = 50

التكلفة (2، {4}، 1) = التوزيعة (2، 4) + التكلفة (4، Φ، 1) = 25+20 = 45

التكلفة (3، {2}، 1) = التوزيعة (3، 2) + التكلفة (2، Φ، 1) = 35+10 = 45

التكلفة (3، {4}، 1) = التوزيعة (3، 4) + التكلفة (4، Φ، 1) = 30+20 = 50

التكلفة (4، {2}، 1) = التوزيعة (4، 2) + التكلفة (2، Φ، 1) = 25+10 = 35

التكلفة (4، {3}، 1) = التوزيعة (4، 3) + التكلفة (3، Φ، 1) = 30+15 = 45

3) |س| = 2:

التكلفة (2، {3، 4}، 1) = الحد الأدنى [ dist[2,3]+Cost(3,{4},1) = 35+50 = 85,

dist[2,4]+Cost(4,{3},1) = 25+45 = 70 ] = 70

التكلفة (3، {2، 4}، 1) = الحد الأدنى [ dist[3,2]+Cost(2,{4},1) = 35+45 = 80,

dist[3,4]+Cost(4,{2},1) = 30+35 = 65 ] = 65

التكلفة (4، {2، 3}، 1) = الحد الأدنى [ dist[4,2]+Cost(2,{3},1) = 25+50 = 75

dist[4,3]+Cost(3,{2},1) = 30+45 = 75 ] = 75

4) |س| = 3:

التكلفة (1، {2، 3، 4}، 1) = الحد الأدنى [ dist[1,2]+Cost(2,{3,4},1) = 10+70 = 80

dist[1,3]+Cost(3,{2,4},1) = 15+65 = 80

dist[1,4]+Cost(4,{2,3},1) = 20+75 = 95 ] = 80

لذلك سيكون الحل الأمثل 1-2-4-3-1

كود مزيف

Algorithm: Traveling-Salesman-Problem 
Cost (1, {}, 1) = 0 
for s = 2 to n do 
   for all subsets S belongs to {1, 2, 3, … , n} of size s 
      Cost (s, S, 1) = Infinity
   for all i Є S and i ≠ 1 
      Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j} 
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)

التنفيذ في C/C++

وهنا التنفيذ في C++:

#include <bits/stdc++.h>
using namespace std;
#define V 4
#define MAX 1000000
int tsp(int graph[][V], int s)
{
    vector<int> vertex;
    for (int i = 0; i < V; i++)
        if (i != s)
            vertex.push_back(i);
    int min_cost = MAX;
    while(next_permutation(vertex.begin(), vertex.end()))
     {
        int current_cost = 0;
        int j = s;
        for (int i = 0; i < vertex.size(); i++) {
            current_cost += graph[j][vertex[i]];
            j = vertex[i];
        }
        current_cost += graph[j][s];
        min_cost = min(min_cost, current_cost);
        return min_cost;
	}
}
int main()
{
    int graph[][V] = { { 0, 10, 15, 20 },{ 10, 0, 35, 25 },{ 15, 35, 0, 30 },{ 20, 25, 30, 0 } };                      
    int s = 0;
    cout << tsp(graph, s) << endl;
    return 0;
}

الإخراج:

التنفيذ في Python

from sys import maxsize
from itertools, import permutations
V = 4
def tsp(graph, s):
	vertex = []
	for i in range(V):
		if i != s:
			vertex.append(i)
    min_cost = maxsize
	next_permutation=permutations(vertex)
	for i in next_permutation:
		current_cost = 0
		k = s
		for j in i:
			current_cost += graph[k][j]
			k = j
		current_cost += graph[k][s]
		min_cost = min(min_cost, current_cost)
		return min_cost
graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
		s = 0
print(tsp(graph, s))

الإخراج:

الحلول الأكاديمية لTSP

لقد أمضى علماء الكمبيوتر سنوات في البحث عن خوارزمية زمنية متعددة الحدود محسنة لمشكلة بائع متجول. وحتى الآن، لا تزال المشكلة صعبة من حيث NP.

على الرغم من أن بعض الحلول التالية تم نشرها في السنوات الأخيرة والتي قللت من التعقيد إلى حد ما:

يتم حل TSP المتماثل الكلاسيكي بواسطة طريقة Zero Suffix.
تعتمد خوارزمية التحسين المعتمدة على الجغرافيا الحيوية على استراتيجية الترحيل لحل مشكلات التحسين التي يمكن التخطيط لها كـ TSP.
تم تصميم الخوارزمية التطورية متعددة الأهداف لحل مشكلات TSP المتعددة بناءً على NSGA-II.
يعمل النظام متعدد الوكلاء على حل مشكلة TSP للمدن N بموارد ثابتة.

تطبيق مشكلة البائع المتجول

يتم تطبيق مشكلة البائع المتجول (TSP) في العالم الحقيقي في أنقى أشكالها والمعدلة. بعض هذه هي:

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

تحليل تعقيد TSP

تعقيد الوقت: هناك ما مجموعه 2^Nالمشاكل الفرعية لكل عقدة. وبالتالي فإن العدد الإجمالي للمسائل الفرعية سيكون N*2^N. تتطلب كل مشكلة فرعية وقتًا خطيًا لحلها. إذا لم يتم تحديد العقدة الأصلية، فعلينا تشغيل حلقات للعقد N.
لذا فإن التعقيد الزمني الإجمالي للحل الأمثل سيكون عدد العقد * عدد المشكلات الفرعية * الوقت اللازم لحل كل مشكلة فرعية. يمكن تعريف التعقيد الزمني على أنه O(N)² * 2^ن).
تعقيد الفضاء: يستخدم أسلوب البرمجة الديناميكية الذاكرة لتخزين C(S, i)، حيث S هي مجموعة فرعية من مجموعة القمم. هناك ما مجموعه 2^Nمجموعات فرعية لكل عقدة. لذا، فإن تعقيد الفضاء هو O(2^N).

التالي سوف تتعلم عن غربال خوارزمية إراتوستينس

قد ترغب: