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

لا تأخذ خوارزمية الحل الجشعة كل الفرق الممكنة بعين الاعتبار ولا تضمن إيجاد الحل الأمثل، ولكنها كما هو موضح أدناه أسرع بكثير من خوارزمية الحل التي تعتمد على القوة المفرطة، ومع ذلك يمكنها أن تنتج حلولاً جيدة، هي في الغالب حلول مثلى، ومن المؤكد أن تجد هذه الطريقة حلاً إذا كان موجودًا. يستخدم المقطع البرمجي التالي خوارزمية الحل الجشعة لحساب حلول مجموعات البيانات: 5-workers (خمسة عمال)، و 10-workers (عشرة عمال)، و 15-workers (خمسة عشر عاملاً)، و 20-workers (عشرين عاملاً) التي تم استخدامها سابقًا لتقييم خوارزمية الحل بالقوة المفرطة:

greedy_solutions_5 = gets_solutions(problems_with_5_workers, solver = greedy_solver) greedy_solutions_10 = gets_solutions(problems_with_10_workers, solver = greedy_solver) greedy_solutions_15 = gets_solutions(problems_with_15_workers, solver = greedy_solver) greedy_solutions_20 = gets_solutions(problems_with_20_workers, solver = greedy_solver)

Solved 23 problems in 0.0009970664978027344 seconds Solved 80 problems in 0.000997304916381836 seconds Solved 94 problems in 0.00199508669921875 seconds Solved 99 problems in 0.00199437141845703 seconds

والآن يتضح الفرق في السرعة بين الخوارزميتين؛ حيث يمكن تطبيق خوارزمية الحل الجشعة على النسخ المتعلقة بالمشكلات الكبيرة جدًا، كما في المثال التالي:

# creates 100 problem instances of a team formation problem with 1000 workers problems_with_1000_workers = [] for i in range(100): # repeats 100 times problems_with_1000_workers.append(create_problem_instance(10, 1000, 8, 5)) # solves the 100-worker problems using the greedy solver greedy_solutions_1000 = gets_solutions(problems_with_1000_workers, solver = greedy_solver)

Solved 100 problems in 0.09574556350708008 seconds

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

262

لا تأخذ خوارزمية الحل الجشعة كل الفرق الممكنة بعين الاعتبار ولا تضمن إيجاد الحل الأمثل، ولكنها كما هو موضح أدناه أسرع بكثير من خوارزمية الحل التي تعتمد على القوة المفرطة، ومع ذلك يمكنها أن تنتج حلولاً جيدة، هي في الغالب حلول مثلى، ومن المؤكد أن تجد هذه الطريقة حلاً إذا كان موجودًا. يستخدم المقطع البرمجي التالي خوارزمية الحل الجشعة لحساب حلول مجموعات البيانات: 5-workers (خمسة عمال)، و 10-workers (عشرة عمال)، و 15-workers (خمسة عشر عاملاً)، و 20-workers (عشرين عاملاً) التي تم استخدامها سابقًا لتقييم خوارزمية الحل بالقوة المفرطة:greedy_solutions_5 = gets_solutions(problems_with_5_workers, solver = greedy_solver)greedy_solutions_10 = gets_solutions(problems_with_10_workers, solver = greedy_solver)greedy_solutions_15 = gets_solutions(problems_with_15_workers, solver = greedy_solver)greedy_solutions_20 = gets_solutions(problems_with_20_workers, solver = greedy_solver)Solved 23 problems in 0.0009970664978027344 seconds Solved 80 problems in 0.000997304916381836 seconds Solved 94 problems in 0.00199508669921875 seconds Solved 99 problems in 0.00199437141845703 secondsوالآن يتضح الفرق في السرعة بين الخوارزميتين؛ حيث يمكن تطبيق خوارزمية الحل الجشعة على النسخ المتعلقة بالمشكلات الكبيرة جدًا، كما في المثال التالي:# creates 100 problem instances of a team formation problem with 1000 workers problems_with_1000_workers = []for i in range(100): # repeats 100 times problems_with_1000_workers.append(create_problem_instance(10, 1000, 8, 5))# solves the 100-worker problems using the greedy solver greedy_solutions_1000 = gets_solutions(problems_with_1000_workers, solver = greedy_solver)Solved 100 problems in 0.09574556350708008 seconds2023 - 1447