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

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

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

problems_with_5_workers = [] # 5 workers problems_with_10_workers = [] # 10 workers problems_with_15_workers = [] # 15 workers problems_with_20_workers = [] # 20 workers for i in range(100): # repeat 100 times problems_with_5_workers.append(create_problem_instance(10, 5, 8, 5)) problems_with_10_workers.append(create_problem_instance(10, 10, 8, 5)) problems_with_15_workers.append(create_problem_instance(10, 15, 8, 5)) problems_with_20_workers.append(create_problem_instance(10, 20, 8, 5))

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

import time def gets_solutions(problems, solver): total_seconds = 0 # total seconds required to solve all problems with this solver total_solved = 0 # total number of problems for which the solver found a solution solutions = [] # solutions returned by the solver for problem in problems: start_time = time.time() # starts the timer best_team = solver(problem) # computes the solution end_time = time.time() # stops the timer solutions.append(best_team) # remembers the solution total_seconds += end_time-start_time # computes total elapsed time if best_team != None: # if the best team is a valid team total_solved += 1 print("Solved {} problems in {} seconds".format(total_solved, total_seconds)) return solutions

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

من المؤكد أن خوارزمية الحل بالقوة المفرطة ستجد أفضل حل ممكن، أي: أقل الفرق عددًا طالما أن هناك حل ممكن. ولكن كما تم مناقشته في بداية هذا الدرس فإن طبيعة الخوارزمية الشمولية تؤدي إلى زيادة هائلة في التكلفة الحاسوبية كلما زاد حجم المشكلة.يمكن توضيح ذلك من خلال إنشاء نسخ لمشكلات متعددة من حيث تزايد عدد العمال، ويمكن استخدام المقطع البرمجي التالي لتوليد نسخ متنوعة من مشكلة تكوين الفريق، حيث يتنوع عدد العمال ليكون: 5 و 10 و 15 و 20. ثم يتم توليد 100 نسخة بعدد العمال، وتشمل كل النسخ المهارات الإجمالية العشر، والمهارات الثمان المطلوبة، والخمس مهارات كحد أقصى لكل عامل:problems_with_5_workers = [] # 5 workers problems_with_10_workers = [] # 10 workers problems_with_15_workers = [] # 15 workers problems_with_20_workers = [] # 20 workers for i in range(100): # repeat 100 times problems_with_5_workers.append(create_problem_instance(10, 5, 8, 5)) problems_with_10_workers.append(create_problem_instance(10, 10, 8, 5)) problems_with_15_workers.append(create_problem_instance(10, 15, 8, 5)) problems_with_20_workers.append(create_problem_instance(10, 20, 8, 5))تقبل الدالة التالية قائمة بنسخ المشكلة وخوارزمية الحل بالقوة المفرطة، وتستخدم هذه الخوارزمية لإجراء العمليات الحسابية ثم استخراج الحل لجميع النسخ، كما أنها تسجل الوقت الإجمالي المطلوب (بالثواني) لحساب الحلول وكذلك العدد الإجمالي للنسخ التي يمكن إيجاد حل منها:import time def gets_solutions(problems, solver):total_seconds = 0 # total seconds required to solve all problems with this solver total_solved = 0 # total number of problems for which the solver found a solution solutions = [] # solutions returned by the solver for problem in problems:start_time = time.time() # starts the timer best_team = solver(problem) # computes the solution end_time = time.time() # stops the timer solutions.append(best_team) # remembers the solution total_seconds += end_time-start_time # computes total elapsed time if best_team != None: # if the best team is a valid team total_solved += 1print("Solved {} problems in {} seconds".format(total_solved, total_seconds))return solutions2023 - 1447