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

يولد المقطع البرمجي التالي 100 نسخة من مشكلة البائع المتجول تشمل 8 مواقع وتتراوح المسافات فيها بين 5 و 20. كما أنه يستخدم خوارزمية حل القوة المفرطة، وخوارزمية حل برمجة الأعداد الصحيحة المختلطة لحل كل حالة. ويظهر النسبة المئوية للأسلوبين اللذين أظهرا طريقتين لهما المسافة نفسها:

same_count = 0 for i in range(100): dist_matrix, location_ids, startstop=create_problem_instance(8, [5,20]) route1, dist1 = brute_force_solver(dist_matrix, location_ids, startstop) route2, dist2 = MIP_solver(dist_matrix, location_ids, startstop) # counts how many times the two solvers produce the same total distance if dist1 == dist2: same_count += 1 print(same_count / 100)

1.0

تؤكد النتائج أن خوارزمية حل برمجة الأعداد الصحيحة المختلطة تظهر الحل الأمثل بنسبة 100% لكل نسخ المشكلة. ويوضح المقطع البرمجي التالي سرعة خوارزمية حل برمجة الأعداد الصحيحة المختلطة من خلال استخدامها لحل 100 نسخة كبيرة تتضمن كل منها 20 موقعًا:

import time start = time.time() # starts timer for i in range(100): dist_matrix, location_ids, startstop = create_problem_instance(20, [5,20]) route, dist = MIP_solver(dist_matrix, location_ids, startstop) stop=time.time() # stops timer print(stop - start) # prints the elapsed time in seconds

188.90074133872986

على الرغم من أن وقت التنفيذ الدقيق سيعتمد على قوة معالجة الجهاز الذي تستخدمه لتنفيذ مفكرة جوبيتر، إلا أنه من المفترض أن يستغرق التنفيذ بضع دقائق لحساب الحل لجميع مجموعات البيانات المئة. وهذا بدوره مذهل إذا تم الأخذ في الاعتبار أن عدد الطرق الممكنة لكل نسخة من النسخ المئة هي: 121,645,100,000,000 = !19 طريقًا مختلفًا، ومثل هذا العدد الكبير من الطرق يفوق بكثير قدرات أسلوب القوة المفرطة. ومع ذلك، فإنه عن طريق البحث الفعال في هذه المساحة الهائلة الخاصة بجميع الحلول الممكنة يمكن لخوارزمية حل برمجة الأعداد الصحيحة المختلطة أن تجد الطريق الأمثل بسرعة.

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

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

يولد المقطع البرمجي التالي 100 نسخة من مشكلة البائع المتجول تشمل 8 مواقع وتتراوح المسافات فيها بين 5 و 20. كما أنه يستخدم خوارزمية حل القوة المفرطة، وخوارزمية حل برمجة الأعداد الصحيحة المختلطة لحل كل حالة. ويظهر النسبة المئوية للأسلوبين اللذين أظهرا طريقتين لهما المسافة نفسها:same_count = 0 for i in range(100): dist_matrix, location_ids, startstop=create_problem_instance(8, [5,20]) route1, dist1 = brute_force_solver(dist_matrix, location_ids, startstop) route2, dist2 = MIP_solver(dist_matrix, location_ids, startstop) # counts how many times the two solvers produce the same total distance if dist1 == dist2: same_count += 1 print(same_count / 100)1.0تؤكد النتائج أن خوارزمية حل برمجة الأعداد الصحيحة المختلطة تظهر الحل الأمثل بنسبة 100% لكل نسخ المشكلة. ويوضح المقطع البرمجي التالي سرعة خوارزمية حل برمجة الأعداد الصحيحة المختلطة من خلال استخدامها لحل 100 نسخة كبيرة تتضمن كل منها 20 موقعًا:import time start = time.time() # starts timer for i in range(100): dist_matrix, location_ids, startstop = create_problem_instance(20, [5,20]) route, dist = MIP_solver(dist_matrix, location_ids, startstop)stop=time.time() # stops timer print(stop - start) # prints the elapsed time in seconds188.90074133872986على الرغم من أن وقت التنفيذ الدقيق سيعتمد على قوة معالجة الجهاز الذي تستخدمه لتنفيذ مفكرة جوبيتر، إلا أنه من المفترض أن يستغرق التنفيذ بضع دقائق لحساب الحل لجميع مجموعات البيانات المئة. وهذا بدوره مذهل إذا تم الأخذ في الاعتبار أن عدد الطرق الممكنة لكل نسخة من النسخ المئة هي: 121,645,100,000,000 = !19 طريقًا مختلفًا، ومثل هذا العدد الكبير من الطرق يفوق بكثير قدرات أسلوب القوة المفرطة. ومع ذلك، فإنه عن طريق البحث الفعال في هذه المساحة الهائلة الخاصة بجميع الحلول الممكنة يمكن لخوارزمية حل برمجة الأعداد الصحيحة المختلطة أن تجد الطريق الأمثل بسرعة.وعلى الرغم من مزايا البرمجة الرياضية إلا أنها تملك قيودًا خاصة أيضًا. فهي تتطلب فهمًا قويًا للنمذجة الرياضية وقد لا تكون مناسبة للمشكلات المعقدة التي يصعب فيها التعبير عن الدالة الموضوعية والقيود بواسطة الصيغ الرياضية. وعلى الرغم من أن البرمجة الرياضية أسرع بكثير من أسلوب القوة المفرطة إلا أنها قد تظل بطيئة جدًا بالنسبة لمجموعات البيانات الكبيرة. وفي مثل هذه الحالات يقدم الأسلوب الاستدلالي الموضح في الدرسين السابقين بديلاً أكثر سرعة.2023 - 1447