حل مشكلة البائع المتجول باستخدام خوارزميات القوة المفرطة وبرمجة الأعداد الصحيحة المختلطة - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

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

brute_force_solver(dist_matrix, location_ids, startstop)

([3, 5, 2, 7, 1, 4, 0, 6, 3], 73.0)

على غرار خوارزميات حل القوة المفرطة التي تم توضيحها في الدروس السابقة، لا تُطبق هذه الخوارزمية إلا على نسخ مشكلة البائع المتجول الصغيرة؛ لأن عدد الطرق الممكنة يتزايد أضعافًا مضاعفة كلما زاد العدد N، ويساوي ! (N-1). وعلى سبيل المثال، عندما يكون 15 = N، فإن عدد الطرق الممكنة يساوي 87,178,291,200 = !14.

استخدام برمجة الأعداد الصحيحة المختلطة لحل مشكلة البائع المتجول

Using MIP to Solve the Traveling Salesman Problem

لاستخدام برمجة الأعداد الصحيحة المختلطة (MIP) لحل مشكلة البائع المتجول (TSP)، يجب إنشاء صيغة رياضية تغطي كلا من الدالة الموضوعية وقيود مشكلة البائع المتجول. تتطلب الصيغة متغير قرار ثنائي x_ij لكل انتقال محتمل i ← j من موقع i إلى موقع آخر j. وإذا كانت المشكلة بها عدد N من المواقع، فإن عدد الانتقالات الممكنة يساوي (N-1) × N. إذا كانت x_ij تساوي 1، فإن الحل يتضمن الانتقال من الموقع i إلى الموقع j، وخلاف ذلك إذا كانت x_ij تساوي 0، فلن يُدرج هذا الانتقال في الحل. يُمكن الوصول بسهولة إلى العناصر في مصفوفة numpy ثنائية الأبعاد عبر الصيغة البرمجية [i,j]. فعلى سبيل المثال:

arr = numpy.full(((4,4), 0) # creates a 4x4 array full of zeros

[[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]

print(arr) arr[0, 0] = 1 arr[3, 3] = 1 print() print(arr)

[[1 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 1]]

يستخدم المقطع البرمجي الأداة ()product من المكتبة itertools لحساب جميع انتقالات المواقع المحتملة، فعلى سبيل المثال:

ids = {0, 1, 2} for i, j in list(product(ids, ids)): print(i, j)

0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2

وزارة التعليم Ministry of Education 289 2023 - 1447

تحسب خوارزمية حل القوة المفرطة المسافة الإجمالية لكل طريق، وتُظهر في النهاية الطريق ذا المسافة الأقصر. يُطبق المقطع البرمجي التالي خوارزمية الحل على نسخة مشكلة البائع المتجول التي تم إنشاؤها سابقًا:brute_force_solver(dist_matrix, location_ids, startstop)([3, 5, 2, 7, 1, 4, 0, 6, 3], 73.0)على غرار خوارزميات حل القوة المفرطة التي تم توضيحها في الدروس السابقة، لا تُطبق هذه الخوارزمية إلا على نسخ مشكلة البائع المتجول الصغيرة؛ لأن عدد الطرق الممكنة يتزايد أضعافًا مضاعفة كلما زاد العدد N، ويساوي ! (N-1). وعلى سبيل المثال، عندما يكون 15 = N، فإن عدد الطرق الممكنة يساوي 87,178,291,200 = !14.استخدام برمجة الأعداد الصحيحة المختلطة لحل مشكلة البائع المتجولUsing MIP to Solve the Traveling Salesman Problemلاستخدام برمجة الأعداد الصحيحة المختلطة (MIP) لحل مشكلة البائع المتجول (TSP)، يجب إنشاء صيغة رياضية تغطي كلا من الدالة الموضوعية وقيود مشكلة البائع المتجول. تتطلب الصيغة متغير قرار ثنائي x_ij لكل انتقال محتمل i ← j من موقع i إلى موقع آخر j. وإذا كانت المشكلة بها عدد N من المواقع، فإن عدد الانتقالات الممكنة يساوي (N-1) × N. إذا كانت x_ij تساوي 1، فإن الحل يتضمن الانتقال من الموقع i إلى الموقع j، وخلاف ذلك إذا كانت x_ij تساوي 0، فلن يُدرج هذا الانتقال في الحل. يُمكن الوصول بسهولة إلى العناصر في مصفوفة numpy ثنائية الأبعاد عبر الصيغة البرمجية [i,j]. فعلى سبيل المثال:arr = numpy.full(((4,4), 0) # creates a 4x4 array full of zeros[[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]print(arr)arr[0, 0] = 1 arr[3, 3] = 1print() print(arr)[[1 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 1]]يستخدم المقطع البرمجي الأداة ()product من المكتبة itertools لحساب جميع انتقالات المواقع المحتملة، فعلى سبيل المثال:ids = {0, 1, 2} for i, j in list(product(ids, ids)): print(i, j)0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 22023 - 1447--- VISUAL CONTEXT ---Table Structure: Headers: N/A Data: N/A Context: Page footer/metadata