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

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

تُعدّ مسألة البائع المتجول (TSP) مسألةً كلاسيكيةً في مجال التحسين التوافقي في علوم الحاسوب النظرية. وبإعطاء رسم بياني للمدن، تطلب مسألة البائع المتجول إيجاد أقصر مسار يمر بكل عقدة مرة واحدة فقط ويعود إلى مدينة البداية.

تتضمن صياغة المسألة قائمة بالمدن بالإضافة إلى المسافات بين كل زوج من المدن.

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

مثال على TSP

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

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

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

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

تُصنّف مسألة البائع المتجول ضمن المسائل الصعبة من نوع NP-hard، إذ لا توجد خوارزمية معروفة ذات زمن متعدد الحدود لحلها بدقة. ويتزايد تعقيدها بشكل أُسّي مع ازدياد عدد المدن.

توجد طرق متعددة لمهاجمة برنامج TSP. وأكثر الطرق شيوعًا هي:

أسلوب القوة الغاشمة: تعتمد الطريقة البسيطة على حساب جميع المسارات الممكنة ومقارنتها. عدد المسارات في رسم بياني يحتوي على n مدينة هو n!مما يجعل استخدام القوة الغاشمة مكلفًا للغاية من الناحية الحسابية لأي شيء يتجاوز حوالي عشر مدن.

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

يشرح هذا البرنامج التعليمي نهج البرمجة الديناميكية، وهو النسخة المخزنة من خوارزمية التفرع والتقييد ويتطابق مع خوارزمية بيلمان-هيلد-كارب.

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

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

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

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

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

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

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

على سبيل المثال، cost(1, {2, 3, 4}, 1) يشير إلى أقصر مسار حيث:

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

التكرار في البرمجة الديناميكية هو:

• بكج cost(i, {}, i) = 0وهذا يعني أننا نبدأ وننتهي عند النقطة i بتكلفة صفرية.
• متى |S| > 1، يُعرِّف cost(i, S, 1) = ∞ لـ i ≠ 1لأن التكلفة الحقيقية للجولة غير معروفة حتى الآن.
• ابدأ من المدينة رقم 1، ثم اختر المدينة التالية بحيث cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ] لـ i ∈ S و i ≠ j.

بالنسبة للرسم البياني أعلاه، فإن مصفوفة التجاور هي كالتالي:

إليك كيفية عمل الخوارزمية:

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

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

cost(2, {3, 4}, 1) = ∞ يعني ذلك أننا نبدأ من المدينة 2، ونمر بالمدينتين 3 و4، ونصل إلى المدينة 1، بتكلفة غير معروفة. وبالمثل:

cost(3, {2, 4}, 1) = ∞

cost(4, {2, 3}, 1) = ∞

الخطوة 3) لكل مجموعة جزئية من S، احسب:

cost(i, S, j) = min [ cost(i, S − {i}, j) + dist(i, j) ]، حيث j ∈ S و i ≠ j.

هذه هي الجولة ذات التكلفة الأقل التي تبدأ من المدينة i، وتزور مجموعة المدن الفرعية مرة واحدة، ثم تعود إلى المدينة j. ولأن الجولة تبدأ من المدينة 1، فإن التكلفة المثلى هي cost(1, {other cities}, 1).

العمل على التكرار خطوة بخطوة

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

1) |س| = 0: {Φ}

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:

• cost(2, {3, 4}, 1) = min [ dist(2, 3) + cost(3, {4}, 1) = 35 + 50 = 85, dist(2, 4) + cost(4, {3}, 1) = 25 + 45 = 70 ] = 70
• cost(3, {2, 4}, 1) = min [ dist(3, 2) + cost(2, {4}, 1) = 35 + 45 = 80, dist(3, 4) + cost(4, {2}, 1) = 30 + 35 = 65 ] = 65
• cost(4, {2, 3}, 1) = min [ dist(4, 2) + cost(2, {3}, 1) = 25 + 50 = 75, dist(4, 3) + cost(3, {2}, 1) = 30 + 45 = 75 ] = 75

4) |س| = 3:

• cost(1, {2, 3, 4}, 1) = min [ 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 in S and i != 1
        Cost (i, S, j) = min {Cost (i, S - {i}, j) + dist(i, j) for j in S and i != j}
Return min(i) Cost (i, {1, 2, 3, ..., n}, j) + d(j, i)

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

إليكم طريقة التنفيذ في C++الإصدار أدناه يُصلح المشكلة المبكرة في المصدر return خطأ برمجي، حيث تم إرجاع النتيجة بعد التبديل الأول بدلاً من تعداد جميع الجولات.

#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;
    do {
        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);
    } while (next_permutation(vertex.begin(), vertex.end()));

    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

التنفيذ في Python

استخدم Python يعكس التنفيذ C++ نسخة. وهي تُصحح المصدر from itertools, import خطأ مطبعي في الفاصلة، الفاصلة في غير موضعها return داخل الحلقة الداخلية، والخدش العرضي على s = 0.

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
    for perm in permutations(vertex):
        current_cost = 0
        k = s
        for j in perm:
            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).

تُقلل العديد من التقنيات المنشورة من التعقيد العملي لأنواع محددة من مسائل البائع المتجول:

• يتم حل مسألة البائع المتجول المتناظرة الكلاسيكية بواسطة طريقة اللاحقة الصفرية.
• استخدم خوارزمية التحسين القائمة على الجغرافيا الحيوية يستخدم استراتيجيات الهجرة لحل مشاكل التحسين التي تتوافق مع مسألة البائع المتجول.
• استخدم خوارزمية تطورية متعددة الأهداف تم تصميمه لحل مشكلة البائع المتجول متعددة الأهداف ويعتمد على خوارزمية NSGA-II.
• استخدم نظام متعدد الوكلاء هذا النهج يحل مسألة البائع المتجول لعدد N من المدن بموارد حسابية ثابتة.
• استخدم أسلوب لين-كيرنيغان الاستدلالي وخليفته LKH تقديم جولات سياحية ضمن نطاق 2-3% من المستوى الأمثل في حالات تضم ملايين المدن.
• الوفاق يستخدم هذا الأسلوب مستويات القطع والتفرع والقطع لحساب القيم المثلى الدقيقة لحالات قياسية تضم عشرات الآلاف من المدن.

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

تظهر مسألة البائع المتجول في العالم الحقيقي بصورتين: الأصلية والمعدلة. ومن أبرز تطبيقاتها:

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

تحليل تعقيد TSP

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

بعد ذلك، تعرف على غربال خوارزمية إراتوستينس.

الأسئلة الشائعة