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

greedy_sol = greedy_solver(sample_problem, deadline_heuristic) greedy_sol

{'schedule': [3, 1, 4, 0, 2], 'tardiness': 124, 'finish_times': [15, 26, 32, 48, 57]}

تُطبّق الدالة التالية استدلالاً بديلاً يأخذ في اعتباره أوزان المهام عند اتخاذ قرار ترتيبها في الجدول:

# returns the weighted deadline of a given job def weighted_deadline_heuristic(job, problem): # accesses the deadlines for this problem and returns the deadline for the job return problem['deadlines'][job] / problem['weights'][job] weighted_greedy_sol = greedy_solver(sample_problem, weighted_deadline_heuristic) weighted_greedy_sol

{'schedule': [3, 2, 1, 4, 0], 'tardiness': 89, 'finish_times': [15, 24, 35, 41, 57]}

البحث المحلي Local Search

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

البحث المحلي (Local Search) هو طريقة تحسين استدلالية تركز على اكتشاف حلول مجاورة لحل معين بهدف تحسينه.

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

أنشأت خوارزمية الحل الاستدلالية الجشعة (Greedy Heuristic Solver) حلاً للمشكلة خطوة خطوة حتى حصلت في النهاية على حل كامل ونهائي، وعلى العكس من ذلك تبدأ طرائق البحث المحلية بحل كامل قد يكون ذا جودة متوسطة أو سيئة، وتعمل بطريقة تكرارية لتحسين جودته. في كل خطوة يكون هناك تغيير بسيط على الحل الحالي، ويتم تقييم جودة الحل الناتج (يُسمى الحل المجاور). وإذا كان يتمتع بجودة أفضل، فإنه يستبدل الحل الحالي ويستمر في البحث. وإذا لم يكن كذلك، يتم تجاهل الحل المجاور وتتكرر العملية لتوليد حل مجاور آخر. ثم ينتهي البحث عندما يتعذر العثور على حل مجاور آخر يتمتع بجودة أفضل من الحل الحالي، ويتم تحديد أفضل حل تم العثور عليه.

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

274

--- SECTION: Code Snippet 1 --- greedy_sol = greedy_solver(sample_problem, deadline_heuristic) greedy_sol--- SECTION: Code Output 1 --- {'schedule': [3, 1, 4, 0, 2], 'tardiness': 124, 'finish_times': [15, 26, 32, 48, 57]}تُطبّق الدالة التالية استدلالاً بديلاً يأخذ في اعتباره أوزان المهام عند اتخاذ قرار ترتيبها في الجدول:--- SECTION: Code Snippet 2 --- # returns the weighted deadline of a given job def weighted_deadline_heuristic(job, problem): # accesses the deadlines for this problem and returns the deadline for the job return problem['deadlines'][job] / problem['weights'][job] weighted_greedy_sol = greedy_solver(sample_problem, weighted_deadline_heuristic) weighted_greedy_sol--- SECTION: Code Output 2 --- {'schedule': [3, 2, 1, 4, 0], 'tardiness': 89, 'finish_times': [15, 24, 35, 41, 57]}--- SECTION: البحث المحلي --- البحث المحلي Local Searchعلى الرغم من أن خوارزمية الحل الجشعة أسرع بكثير من خوارزمية القوة المفرطة، إلا أنها تميل إلى إنتاج حلول ذات جودة أقل بزمن تباطؤ أعلى. ويُعدّ البحث المحلي طريقة لتحسين حل تم حسابه بواسطة الخوارزمية الجشعة أو بأي طريقة أخرى.--- SECTION: البحث المحلي --- البحث المحلي (Local Search) هو طريقة تحسين استدلالية تركز على اكتشاف حلول مجاورة لحل معين بهدف تحسينه.في البحث المحلي، يُمثّل الحل الذي تم التوصل إليه في البداية بشكل متكرر من خلال فحص الحلول المجاورة التي وُجدت عن طريق إجراء تعديلات بسيطة على الحل الحالي. وبالنسبة للعديد من مشكلات التحسين، فهناك طريقة شائعة لتعديل الحل تتمثل في تبديل العناصر بشكل متكرر. على سبيل المثال، في مشكلة تكوين الفريق التي تم توضيحها في الدرس السابق، سيحاول أسلوب البحث المحلي إنشاء فريق أفضل وذلك من خلال تبديل أعضاء الفريق بالعمال الذين لا يُعدّون حاليًا جزءًا من الفريق.أنشأت خوارزمية الحل الاستدلالية الجشعة (Greedy Heuristic Solver) حلاً للمشكلة خطوة خطوة حتى حصلت في النهاية على حل كامل ونهائي، وعلى العكس من ذلك تبدأ طرائق البحث المحلية بحل كامل قد يكون ذا جودة متوسطة أو سيئة، وتعمل بطريقة تكرارية لتحسين جودته. في كل خطوة يكون هناك تغيير بسيط على الحل الحالي، ويتم تقييم جودة الحل الناتج (يُسمى الحل المجاور). وإذا كان يتمتع بجودة أفضل، فإنه يستبدل الحل الحالي ويستمر في البحث. وإذا لم يكن كذلك، يتم تجاهل الحل المجاور وتتكرر العملية لتوليد حل مجاور آخر. ثم ينتهي البحث عندما يتعذر العثور على حل مجاور آخر يتمتع بجودة أفضل من الحل الحالي، ويتم تحديد أفضل حل تم العثور عليه.2025 - 1447