مشكلة البائع المتجول: خوارزمية بايثون، C++

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

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

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

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

مثال على TSP

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

مثال على TSP

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

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

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

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

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

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

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

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

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

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

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

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

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

سوف نستخدم منهج البرمجة الديناميكية لحل مشكلة البائع المتجول (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

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

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

حي (ط، ي) 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) = ∝. هنا التكلفة (i، S، j) تعني أننا نبدأ من المدينة i، ونزور مدن S مرة واحدة، والآن نحن في المدينة j. لقد حددنا تكلفة المسار هذه على أنها لا نهاية لأننا لا نعرف المسافة بعد. لذلك ستكون القيم هي المتابعةwing:

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

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

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

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

التكلفة (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, 2, 3, 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;
}

الإخراج:

80

التنفيذ في بايثون

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))

الإخراج:

80

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

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

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

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

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

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

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

معplexتحليل ity من TSP

  • الوقت كومplexإيتي: هناك ما مجموعه 2N المشاكل الفرعية لكل عقدة. وبالتالي فإن العدد الإجمالي للمسائل الفرعية سيكون N*2N. تتطلب كل مشكلة فرعية وقتًا خطيًا لحلها. إذا لم يتم تحديد العقدة الأصلية، فعلينا تشغيل حلقات للعقد N.

    وبالتالي فإن إجمالي الوقت كومplexإن أهمية الحل الأمثل هي عدد العقد * عدد المشكلات الفرعية * الوقت اللازم لحل كل مشكلة فرعية. الوقت كومplexيمكن تعريف ity بأنها O(N2 * 2^ن).

  • كوم الفضاءplexإيتي: يستخدم أسلوب البرمجة الديناميكية الذاكرة لتخزين C(S, i)، حيث S هي مجموعة فرعية من مجموعة القمم. هناك ما مجموعه 2N مجموعات فرعية لكل عقدة. لذلك، الفضاء كومplexالوحدة هي O(2^N).

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