خوارزميات البحث المستنيرة - الذكاء الاصطناعي - ثالث ثانوي

107 رابط الدرس الرقمي الدرس الرابع خوارزميات البحث المستنيرة تطبيقات خوارزميات البحث Applications of Search Algorithms خوارزميات البحث هي أحد المكونات الرئيسة لأنظمة الذكاء الاصطناعي، فباستخدامها يُمكن اكتشاف الاحتمالات المختلفة لإيجاد الحلول المناسبة للمشكلات المعقدة في العديد من التطبيقات السائدة. وفيما يلي أمثلة على بعض تطبيقات خوارزميات البحث: الروبوتية (Robotics) : قد يستخدم الروبوت خوارزمية البحث لتحديد طريقه عبر المتاهة أو لتحديد موقع أحد الكائنات في نطاق بيئته. مواقع التجارة الإلكترونية (E-Commerce Websites: تستخدم مواقع التسوق عبر الإنترنت خوارزميات البحث لتطابق بين استفسارات العملاء وبين المنتجات المتوفرة، ولتصفية نتائج البحث وفق بعض المعايير مثل السعر، والعلامة التجارية والتقييمات، واقتراح المنتجات ذات الصلة. • منصات مواقع التواصل الاجتماعي ( Social Media Platforms): تستخدم مواقع التواصل الاجتماعي خوارزميات البحث لعرض التدوينات، والأشخاص، والمجموعات للمستخدمين وفقًا للكلمات المفتاحية واهتمامات المستخدم. • تمكين الآلة من ممارسة الألعاب بمستوى عال من المهارة www.ien.edu.sa الحالة النهائية كائن الروبوت | الحالة الأولية (Enabling a Machine to Play Games at a High Skill Level: يستخدم الذكاء الاصطناعي خوارزمية البحث أثناء لعب الشطرنج أو قو (Go) لتقييم الحركات المختلفة واختيار الخطوات التي من المرجح أن تؤدي إلى الفوز. نظم الملاحة باستخدام مُحدِّد المواقع العالمي (GPS Navigation Systems): تَستخدم نظم الملاحة القائمة على مُحدِّد المواقع العالمي خوارزميات البحث لتحديد شكل 2.15 استخدام الروبوت خوارزمية أقصر وأسرع طريق بين موقعين، مع مراعاة بيانات حركة المرور في الوقت الحالي. نظم إدارة الملفات (File Management Systems : تُستخدم خوارزميات البحث في نظم إدارة الملفات لتحديد موقع الملفات باستخدام اسم، ومحتوى الملف، وبعض السمات الأخرى. البحث لتحديد طريقه أنواع خوارزميات البحث وأمثلتها Types and Examples of Search Algorithms هناك نوعان رئيسان من خوارزميات البحث وهما : غير المستنيرة (Uninformed) والمستنيرة (Informed). خوارزميات البحث غير المستنيرة Uninformed Search Algorithms خوارزميات البحث غير المستنيرة، وتسمّى أيضًا : خوارزميات البحث العمياء، وهي تلك التي لا تحتوي على معلومات إضافية حول حالات المشكلة بإستثناء المعلومات المستفادة من تعريف المشكلة. وتقوم هذه الخوارزميات بإجراء فحص شامل لمساحة البحث استنادًا إلى مجموعة من القواعد المحدَّدة مُسبقًا. وتُعدُّ تقنيات البحث بأولوية الاتساع (BFS) والبحث بأولوية العمق (DFS) المشار إليها في الدرس الثاني أمثلة على خوارزميات البحث غير المستنيرة. وزارة التعليم Ministry of Education 2024-1446

وزارة التعليم Ministry of Education 2024-1446 لل على سبيل المثال، تبدأ خوارزمية البحث بأولوية العمق (DFS) عند عُقدة الجذر بالشجرة أو المُخطَّط وتتوسع حتى تصل للعقدة الأعمق التي لم تُفحص ويستمر الأمر بهذه الطريقة حتى تستنفد الخوارزمية مساحة البحث بأكملها بعد فحص كل العقد المتاحة. ثم تُخرج الحل الأمثل الذي وجدته أثناء البحث. فالحقيقة أن خوارزمية البحث بأولوية العمق (DFS) تتبع دومًا هذه القواعد ولا يمكن ضبط استراتيجتها بصرف النظر عن نتائج البحث، وهذا ما يجعلها خوارزمية غير مستنيرة. ومثال آخر ملحوظ على هذا النوع من الخوارزميات هو خوارزمية البحث بأولوية العمق التكراري المتعمق (Iterative Deepening Depth-First Search - IDDFS) التي يمكن اعتبارها مزيجا بين خوارزميتي البحث بأولوية العمق (DFS) والبحث بأولوية الاتساع (BFS) ، فهي تستخدم استراتيجة العُمق أولا للبحث في جميع الخيارات الموجودة في النطاق الكامل بصورة متكررة حتى تصل إلى عُقدة مُحدّدة. خوارزميات البحث المستنيرة Informed Search Algorithms على النقيض من خوارزميات البحث غير المستنيرة، تستخدم خوارزميات البحث المستنيرة المعلومات حول المشكلة ومساحة البحث لتوجيه عملية البحث. والأمثلة على هذه الخوارزميات تشمل: الدالة الاستدلالية *(Heuristic Function) هي الدالة التي تُصنِّف البدائل في خوارزميات البحث عند كل مرحلة ستسلكه. • خوارزمية البحث بأولوية الأفضل (A search تستخدم دالة فرعية استنادًا إلى تقديرات استدلالية لتقدير المسافة بين كل عُقدة من العقد المُرشَّحة والعقدة استدلالية مبنية على البيانات المستهدفة. ثم تُوسّع العُقدة المُرشَّحة بالتقدير الأقل. إن فعالية المتوفرة لتحديد الفرع الذي خوارزمية البحث بأولوية الأفضل A search مرتبطة بجودة دالتها الاستدلالية على سبيل المثال، إذا كنت تضمن أن الاستدلال لن يتجاوز المسافة الفعلية إلى الهدف، فبالتالي ستعثر الخوارزمية على الحل الأمثل. بخلاف ذلك، قد لا يكون الحل الناتج من الخوارزمية هو الأفضل. خوارزمية ديكسترا (Dijkstra's Algorithm تُوسع العقدة بناء على أقصر مسافة فعلية إلى الهدف في كل خطوة. ولذلك، على النقيض من خوارزمية البحث بأولوية الأفضل ، تحسب خوارزمية ديكسترا Dijkstra) المسافة الفعلية ولا تستخدم التقديرات الاستدلالية. وبينما يجعل هذا خوارزمية ديكسترا أبطأ من خوارزمية البحث بأولوية الأفضل إلا أن ذلك يعني ضمان العثور على الحل الأمثل دومًا ( ممثلا بالمسار الأقصر من البداية حتى الهدف. خوارزمية تسلُّق التلال (Hill Climbing تبدأ بتوليد حل عشوائي، ثم تحاول تحسين هذا الحل بصورة متكررة بإجراء تغييرات بسيطة تُحسن من دالة استدلالية مُحدَّدة. وبالرغم من أن هذه المنهجية لا تضمن إيجاد الحل الأمثل، إلا أنها سهلة التنفيذ وتتميز بفعالية كبيرة عند تطبيقها على أنواع معينة من المشكلات. خوارزمية البحث بأولوية الأفضل (A* search) خوارزمية ديسكترا (Dijkstra's Algorithm) شكل 2.16 حل المتاهة نفسها باستخدام خوارزمية البحث بأولوية الأفضل وخوارزمية ديسكترا الخلايا ذات اللون البنفسجي هي الخلايا التي تم فحصها، والخلية ذات اللون الأخضرهي موضع البدء، والخلية ذات اللون الأحمر هي موقع الهدف، بينما الخلايا ذات اللون الأصفر تمثل المسار الذي تم العثور عليه. 108

109 في هذه الوحدة، ستشاهد بعض الأمثلة المرئية وتطبيقات البايثون على خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية الأفضل A search لمعرفة الاختلافات بين خوارزميتي البحث المستنيرة وغير المستنيرة. إنشاء ألغاز المتاهة بواسطة البايثون الهدف موضع البداية 0 1 2 0 1 العقبة 2 X Creating Maze Puzzles in Python و و تُعرَّف المتاهة في صورة إطار شبكي 3×3. يُحدد موضع البداية بنجمة في أسفل يسار المتاهة. الهدف هو الوصول إلى الخلية المستهدفة المحددة بالعلامة ، ويمكن للاعب الانتقال إلى أي خلية فارغة مجاورة لموقعه الحالي. شكل 2.17 لغز متاهة بسيط تكون الخلية فارغة إذا لم تحتوي على عائق. على سبيل المثال، المتاهة الموضّحة في شكل 2.17 تحتوي على 3 خلايا تشغلها الحواجز (Blocks) . هذه الحواجز الملوّنة باللون الرمادي تُشكّل عائقًا يجب على اللاعب تجاوزه للوصول إلى الهدف ، ويمكن للاعب الانتقال بشكل أفقي أو رأسي أو قطري إلى أي خلية فارغة مجاورة لموقعه الحالي كما يظهر في الشكل 2.18، على سبيل المثال: وزارة التعليم Ministry of Education 2024-1446 0 0 1 2 1 2 0 0 1 2 --> 1 2 شكل 2.18: يمكن للاعب الانتقال بشكل أفقي أو رأسي أو قطري إلى أي خلية فارغة مجاورة لموقعه الحالي الهدف هو إيجاد المسار الأقصر والأقل عددًا لمرات فحص الخلايا. وبالرغم من أن المتاهة الصغيرة 3×3 قد تبدو بسيطة للاعب البشري، إلا أنه يتوجب على الخوارزمية الذكية إيجاد حلول للتعامل مع المتاهات الكبيرة والمعقدة للغاية، مثل: متاهة 10,000×10,000 التي تحتوي على ملايين الحواجز الموزّعة في أشكال معقدة ومتنوعة. يمكن استخدام المقطع البرمجي التالي بلغة البايثون لإنشاء مجموعة بيانات تُصوّر المثال الموضح في الشكل 2.18. import numpy as np. # create a numeric 3 x 3 matrix full of zeros. small_maze=np.zeros((3,3)) # coordinates of the cells occupied by blocks blocks [(1, 1), (2, 1), (2, 2)] for block in blocks: # set the value of block-occupied cells to be equal to 1 small_maze[block]=1 small_maze array([[0., 0., 0.], [0., 1., 0.], [0., 1., 1.]])

110 في هذا التمثيل الرقمي للمتاهة، تُمثَّل الخلايا الفارغة بالأصفار (Zeros) والمشغولة بالآحاد (Ones). يمكن تحديث المقطع البرمجي نفسه بسهولة لإنشاء متاهات كبيرة ومعقدة للغاية، مثل: import random random_maze=np.zeros((10,10)) # coordinates of 30 random cells occupied by blocks blocks=[(random.randint(0,9), random.randint(0,9)) for i in range(30)] for block in blocks: random_maze[block]=1 تُستخدم الدالة التالية لتمثيل المتاهة: import matplotlib.pyplot as plt #library used for visualization def plot_maze(maze): ax = plt.gca() ax.invert_yaxis() ax.axis('off') # create a new figure # invert the y-axis to match the matrix #hide the axis labels ax.set_aspect('equal') # make sure the cells are rectangular plt.pcolormesh(maze, edgecolors='black', linewidth=2,cmap='Accent') plt.show() plot_maze(random_maze) المربعات الخضراء فارغة ويُمكن اجتيازها. شكل :2.19 تمثيل متاهة 10×10 باستخدام حواجز عشوائية المربعات السوداء مشغولة بالحواجز ولا يُمكن اجتيازها. وزارة التعليم Ministry of Education 2024-1446

111 وزارة التعليم Ministry of Education 2024-1446 يمكن استخدام الدالة التالية لاستدعاء قائمة تحتوي على كل الخلايا الفارغة والمجاورة لخلية محددة في أي متاهة: def get_accessible_neighbors (maze: np.ndarray, cell: tuple): # list of accessible neighbors, initialized to empty neighbors=[] x-1, y-1 x-1, y x-1, y+1 x, y-1 x+1, y-1 , x, y+1 x+1, y x+1, y+1 x,y=cell # for each adjacent cell position for i,j in [(x-1,y-1),(x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y), (x+1,y+1)]: # if the adjacent cell is within the bounds of the grid and is not occupied by a block if i>=0 and j>=0 and i<len(maze) and j<len(maze[0]) and maze[(i,j)]==0: neighbors.append(((i,j),1)) return neighbors يفترض هذا التطبيق أن كل عميلة انتقال من خلية إلى أخرى مجاورة سواءً أفقيًا أو رأسيًا أو قطريًا يتم بتكلفة مقدارها وحدَةٌ وَاحِدَة فقط. سيتم إعادة النظر في هذه الفرضية في وقت لاحق من هذا الدرس بعرض حالات أكثر تعقيدًا مع شروط انتقال متغيرة. تستخدم كل خوارزميات البحث دالة ( )get_accessible_neighbors في محاولة حل المتاهة. في الأمثلة التالية تُستخدم المتاهة 3×3 المصمَّمة بالأعلى للتحقق من أن الدالة تستدعي الخلية الصحيحة الفارغة والمجاورة للخلية المحددة. 1 2 1 2 0 1 2 0 1 2 # this cell is the northwest corner of the grid and has only 2 accessible neighbors get_accessible_neighbors (small_maze, (0,0)) [((0, 1), 1), ((1, 0), 1)] # the starting cell (in the southwest corner) has only 1 accessible neighbor get_accessible_neighbors (small_maze, (2,0)) [((1, 0), 1)] بعد أن تعلمت كيفية إنشاء المتاهات، وكذلك استدعاء الخلايا المجاورة لأي خلية في المتاهة، فإن الخطوة التالية هي تطبيق خوارزميات البحث التي يمكنها حل المتاهة من خلال إيجاد المسار الأقصر من خلية البداية إلى خلية الهدف المحددة. و الخلية المجاورة خلية البداية شكل 2.20: الخلايا المجاورة

استخدام خوارزمية البحث بأولوية الاتساع في حل ألغاز المتاهة Using BFS to Solve Maze Puzzles و تَستخدم دالة ( )bfs_maze_solver المشار إليها في هذا الجزء خوارزمية البحث بأولوية الاتساع (BFS) لحل ألغاز المتاهة باستخدام خلية البداية وخلية الهدف. يستخدم هذا النموذج دالة ( )get_accessible_neighbors المحددة بالأعلى لاستدعاء الخلايا المجاورة التي يمكن فحصها عند أي نقطة أثناء البحث، وبمجرد عثور خوارزمية البحث بأولوية الاتساع (BFS) على الخلية الهدف، ستستخدم دالة ( )reconstruct_shortest_path الموضحة بالأسفل لإعادة بناء المسار الأقصر واستدعائه، وذلك بتتبع المسار بصورة عكسية من خلية الهدف إلى خلية البداية: وزارة التعليم Ministry of Education 2024-1446 def reconstruct_shortest_path(parent:dict, start_cell:tuple, target_cell:tuple): shortest_path = [] my_parent=target_cell # start with the target_cell # keep going from parent to parent until the search cell has been reached while my_parent!=start_cell: shortest_path.append(my_parent) # append the parent my_parent=parent[my_parent] # get the parent of the current parent shortest_path.append(start_cell) #append the start cell to complete the path shortest_path.reverse() # reverse the shortest path return shortest_path ستُستخدم دالة ()reconstruct_shortest_path أيضًا لإعادة بناء الحل لخوارزمية البحث بأولوية الأفضل (A search المشار إليها سلفًا في هذا الدرس. وبالنظر إلى تعريف الدالتين ( ) get_accessible_ neighbors و ()reconstruct_shortest_path المساعدتين ، يمكن تنفيذ دالة ()bfs_maze_solver على النحو التالي: from typing import Callable # used to call a function as an argument of another function def bfs_maze_solver(start_cell:tuple, target_cell:tuple, maze:np.ndarray, get_neighbors: Callable, verbose:bool-False): #by default, suppresses descriptive output text cell_visits=0 #keeps track of the number of cells that were visited during the search visited = set() #keeps track of the cells that have already been visited to expand = [ ] # keeps track of the cells that have to be expanded # add the start cell to the two lists visited.add(start_cell) to_expand.append(start_cell) # remembers the shortest distance from the start cell to each other cell shortest_distance = {} # the shortest distance from the start cell to itself, zero 112

113 وزارة التعليم Ministry of Education 2024-1446 shortest_distance[start_cell] = Θ # remembers the direct parent of each cell on the shortest path from the start_cell to the cell parent = {} #the parent of the start cell is itself parent[start_cell] = start_cell while len(to_expand)>0: next_cell = to_expand.pop(0) # get the next cell and remove it from the expansion list if verbose: print('\nExpanding cell', next_cell) # for each neighbor of this cell for neighbor, cost in get_neighbors (maze, next_cell): if verbose: print('\tVisiting neighbor cell', neighbor) cell_visits+=1 if neighbor not in visited: # if this is the first time this neighbor is visited visited.add(neighbor) to_expand.append(neighbor) parent[neighbor]= next_cell shortest_distance [neighbor] = shortest_distance[next_cell]+cost # target reached if neighbor ==target_cell: # get the shortest path to the target cell, reconstructed in reverse. shortest path = reconstruct_shortest_path (parent, start_cell, target_cell) return shortest_path, shortest_distance [target_cell], cell_visits else: # this neighbor has been visited before # if the current shortest distance to the neighbor is longer than the shortest # distance to next_cell plus the cost of transitioning from next_cell to this neighbor if shortest_distance [neighbor]>shortest_distance [next_cell] parent[neighbor] = next_cell +cost: shortest_distance [neighbor] = shortest_distance[next_cell]+cost #search complete but the target was never reached, no path exists return None, None, None

تتبع الدالة منهجية البحث بأولوية الاتساع (BFS ) للبحث في كل الخيارات في العمق الحالي قبل الانتقال إلى مستوى العُمق التالي، وتستخدم هذه المنهجية مجموعة واحدة تُسمّى visited وقائمة تُسمى to_expand. تتضمن المجموعة الأولى كل الخلايا التي فُحِصَت مرة واحدة على الأقل من قبل الخوارزمية، بينما تتضمن القائمة الثانية كل الخلايا التي لم تُوسَّع ،بعد ، مما يعني أن الخلايا المجاورة لم تُفحص بعد. تستخدم الخوارزمية كذلك قاموسين shortest_distance و parent ، يحفظ الأوّل منهما طول المسار الأقصر من خلية البداية إلى كل خلية أخرى، بينما يحفظ الثاني عُقدة الخلية الأصل في المسار الأقصر. بمجرد الوصول إلى الخلية الهدف وانتهاء البحث، سيُخزن المتغيّر [shortest_distance [target_cell طول الحل والذي يمثل طول المسار الأقصر من البداية إلى الهدف. يَستخدم المقطع البرمجي التالي دالة ()bfs_maze_solver لحل المتاهة الصغيرة 3×3 الموضّحة بالأعلى: وزارة التعليم Ministry of Education 2024-1446 start_cell=(2,0) # start cell, marked by a star in the 3x3 maze target_cell=(1,2) # target cell, marked by an "X" in the 3x3 maze solution, distance, cell_visits=bfs_maze_solver(start_cell, target_cell, small_maze, get_accessible_neighbors, verbose=True) print('\nShortest Path: ', solution) print('Cells on the Shortest Path:', len(solution)) print('Shortest Path Distance:', distance) print('Number of cell visits:', cell_visits) Expanding cell (2, 0) Visiting neighbor cell (1, 0) Expanding cell (1, 0) Visiting neighbor cell (0, 0) Visiting neighbor cell (0, 1) Visiting neighbor cell (2, 0) Expanding cell (0, 0) Visiting neighbor cell (0, 1) Visiting neighbor cell (1, 0) Expanding cell (0, 1) Visiting neighbor cell (0, 0) Visiting neighbor cell (0, 2) Visiting neighbor cell (1, 0) Visiting neighbor cell (1, 2) Shortest Path: [(2, 0), (1, 0), (0, 1), (1, 2)] Cells on the Shortest Path: 4 Shortest Path Distance: 3 Number of cell visits: 10 114

115 وزارة التعليم Ministry of Education 2024-1446 تنجح خوارزمية البحث بأولوية الاتساع (BFS) في إيجاد المسار الأقصر بعد فحص 10 خلايا . يمكن تصوير عملية البحث المطبقة بخوارزمية البحث بأولوية الاتساع (BFS) بسهولة عند تصوير المتاهة بالتمثيل المستند إلى مُخطَّط. المثال التالي يعرض متاهة 3×3 وتمثيلها بالمخطَّط: 0 X 1,0 0,0 1,2 0 2,0 1 0,1 0,2 2 1 2 X يتضمن تمثيل المخطَّط عُقدة واحدة لكل خلية غير مشغولة. تُوضّح القيمة على العُقد إحداثيات خلية المصفوفة المقابلة. ستظهر حافة غير مُوجَّهة من عُقدة إلى أخرى في حال كانت الخلايا المقابلة يمكن الوصول إليها من خلال الانتقال من واحدة إلى الأخرى. إحدى الملاحظات المهمة حول خوارزمية البحث بأولوية الاتساع (BFS) هي أنه في حالة المخطّطات غير الموزونة ( weighted Graphs) يكون المسار الأول الذي تُحدّده الخوارزمية بين خلية البداية وأي خلية أخرى هو المسار الذي يتضمن أقل عدد من الخلايا التي تم فحصها . وهذا يعني أنه إذا كانت كلّ الحواف في المخطّط لها الوزن نفسه، أي كان لكلّ الانتقالات من خلية إلى أخرى التكلفة نفسها ، فإنّ المسار الأول الذي تُحدِّده الخوارزمية إلى عُقدة مُحدَّدة يكون هو المسار الأقصر إلى تلك العقدة. ولهذا السبب، تتوقف دالة ( )bfs_maze_solver عن البحث ، وتعرض نتيجة المرة الأولى التي فَحصت فيها العقدة المستهدفة. ذلك، لا يمكن تطبيق هذه المنهجية على المخطّطات الموزونة (Weighted Graphs). المثال التالي يوضّح ومع إصدارًا موزونًا (Weighted Version) لتمثيل مُخطَّط متاهة 3×3: 0 1 X 1,0 1 0,0 1,2 0 1 3 1 3 1 1 0,1 1 0,2 2 2,0 2 ✓ شكل 2.21: المتاهة ومُخطَّطها الموزون في هذا المثال، يكون وزن كل الحواف المقابلة للحركات الرأسية أو الأفقية (جنوبًا ، شمالا، غربا، شرقًا) يساوي 1. ومع ذلك، يكون وزن كل الحواف المقابلة للحركات القطرية (جنوبية غربية ، جنوبية شرقية، شمالية غربية، شمالية شرقية يساوي 3 في هذه الحالة الموزونة، سيكون المسار الأقصر هو [(2,0) ، (1,0) ، (0,0)، (0,1)، (0,2)، (1,2)]، بمسافة إجمالية: 1+1+1+1+1=5. يمكن ترميز هذه الحالة الأكثر تعقيدًا باستخدام الإصدار الموزون من الدالة ( ) get_accessible_neighbors الموضحة بالأسفل. def get_accessible_neighbors_weighted(maze:np.ndarray, cell:tuple, horizontal_vertical_weight:float, diagonal_weight: float):

وزارة التعليم Ministry of Education 2024-1446 neighbors = [] x,y=cell for i,j in [(x-1,y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)]: # for diagonal neighbors # if the cell is within the bounds of the grid and it is not occupied by a block if i>=0 and j>=0 and i<len (maze) and j<len (maze[0]) and maze [(i,j)]==0: neighbors.append(((i,j), diagonal_weight)) for i,j in [(x-1,y), (x,y-1), (x,y+1), (x+1,y)]: #for horizontal and vertical neighbors if i>=0 and j>=0 and i<len(maze) and j<len(maze[0]) and maze[(i,j)]==0: neighbors.append(((i,j), horizontal_vertical_weight)) return neighbors تسمح الدالة للمُستخدم بتعيين وزن مُخصص للحركات الأفقية والحركات الرأسية، وكذلك وزن مخصص مختلف للحركات القطرية. إذا استُخدِم الإصدار الموزون (Weighted Version) المشار إليه بواسطة أداة الحل في البحث بأولوية الاتساع (BFS solver) ، فإن النتائج ستكون كما يلي: from functools import partial start_cell=(2,0) target_cell (1,2) horz_vert_w=1 # weight for horizontal and vertical moves diag_w=3 #weight for diagonal moves solution, distance, cell_visits=bfs_maze_solver(start_cell, print('\nShortest Path:', solution) target_cell, small_maze, partial(get_accessible_neighbors_weighted, horizontal_vertical_weight=horz_vert_w, diagonal_weight=diag_w), verbose=False) print('Cells on the Shortest Path:', len(solution)) print('Shortest Path Distance:', distance) print('Number of cell visits:', cell_visits) Shortest Path: [(2, 0), (1, 0), (0, 1), (1, 2)] Cells on the Shortest Path: 4 Shortest Path Distance: 7 Number of cell visits: 6 116

117 وكما هو متوقع، أخطأت أداة الحل في البحث بأولوية الاتساع (BFS solver ) في عرض المسار السابق نفسه بالضبط، على الرغم من أن التكلفة تساوي 7 ، ومن الواضح أنه ليس المسار الأقصر. ويرجع ذلك إلى الطبيعة غير المستنيرة لخوارزمية البحث بأولوية الاتساع (BFS) ، حيث لا تأخذ الخوارزمية الأوزان بعين الاعتبار عند تحديد الخلية المقرَّر توسيعها في الخطوة التالية؛ لأنها تُطبق ببساطة منهجية البحث بالعرض نفسها والتي تؤدي إلى المسار نفسه الذي وجدته الخوارزمية في الإصدار غير الموزون (Unweighted Version من المتاهة. القسم التالي يصف طريقة معالجة نقطة الضعف هذه باستخدام خوارزمية البحث بأولوية الأفضل (A search)، وهي خوارزمية مُستنيرة وأكثر ذكاءً تضبط سلوكها وفقًا للأوزان المحدَّدة، وبالتالي يُمكنها حل المتاهات باستخدام الانتقالات الموزونة (Weighted Transitions) والانتقالات غير الموزونة (Unweighted Transitions ) . استخدام خوارزمية البحث بأولوية الأفضل في حل ألغاز المتاهة Using A* Search to Solve Maze Puzzles كما في خوارزمية البحث بأولوية الاتساع (BFS) ، تفحص خوارزمية البحث بأولوية الأفضل (A search) خلية واحدة في كل مرة بفحص كل خلية مجاورة يمكن الوصول إليها. فبينما تستخدم خوارزمية البحث بأولوية الاتساع (BFS) منهجية بحث عمياء بأولوية العرض لتحديد الخلية التالية التي ستفحصها ، تفحص خوارزمية البحث بأولوية الأفضل (search الخلية التي يكون بينها وبين الخلية المستهدفة أقصر مسافة محسوبة بواسطة الدالة الاستدلالية )Heuristic Function. يعتمد التعريف الدقيق للدالة الاستدلالية على التطبيق. في حالة ألغاز المتاهة، توفّر الدالة الاستدلالية تقديرًا دقيقًا لمدى قُرب الخلية المرشَّحة إلى الخلية المستهدفة. يضمن الاستدلال المُطبَّق عدم المبالغة في تقدير (Overestimate) المسافة الفعلية إلى الخلية المستهدفة مثل: عرض مسافة تقديرية أكبر من المسافة الحقيقية إلى الهدف، وبالتالي ستُحدِّد الخوارزمية أقصر مسار محتمل لكل من المخططين الموزون (Weighted) وغير الموزون (Unweighted) . إذا كان الاستدلال يُبالغ في بعض الأحيان في تقدير المسافة، ستُقدِّم خوارزمية البحث بأولوية الأفضل (A search حلا ، ولكن قد لا يكون الأفضل. الاستدلال المحتمل الأبسط الذي لن يؤدي إلى المبالغة في تقدير المسافة هو دالة بسيطة تعطي دوما مسافة تقديرية قدرها وحدة واحدة. وزارة التعليم Ministry of Education 2024-1446 def constant_heuristic(candidate_cell:tuple, target_cell:tuple): return 1 على الرغم من أن هذا الاستدلال شديد التفاؤل، إلا أنه لن يُقدم أبدًا تقديرًا أعلى من المسافة الحقيقية، وبالتالي سيؤدي إلى أفضل حل ممكن. سيتم تقديم استدلال متطور يُمكنه العثور على أفضل حل بشكل سريع في هذا القسم لاحقًا. 0,0 1,0 1 1 0,1 تستخدم الدالة التالية دالة استدلالية معطاة للعثور على الخلية التي يجب توسيعها بعد ذلك: شكل 2.22: الاستدلال الثابت def get_best_candidate(expansion_candidates:set, winner = None shortest_distance:dict, heuristic: Callable): # best (lowest) distance estimate found so far. Initialized to a very large number best_estimate sys.maxsize for candidate in expansion_candidates: # distance estimate from start to target, if this candidate is expanded next

وزارة التعليم Ministry of Education 2024-1446 candidate estimate-shortest_distance [candidate] + heuristic(candidate, target_cell) if candidate_estimate < best_estimate: winner = candidate best estimate=candidate_estimate return winner يَستخدم التطبيق المشار إليه بالأعلى حلقة التكرار For لفحص الخلايا المرشَّحة في المجموعة وتحديد الأفضل. ولتطبيق أكثر كفاءة، قد يُستخدم طابور الأولوية (Priority Queue) في تحديد المرشّح الأفضل دون الحاجة إلى فحص كل المُرشَّحين بصورة متكررة. تُستخدم دالة ( ) get_best_candidate كدالة مساعدة بواسطة دالة ( )astar_maze_solver الموضّحة فيما يلي. وبالإضافة إلى الدالة الاستدلالية، يُستخدم هذا التطبيق كذلك ŵ Я ✓ail reconstruct_shortest_path(), get_accessible_neighbors_weighted () import sys def astar_maze_solver (start_cell: tuple, target_cell: tuple, maze: np.ndarray, get_neighbors: Callable, heuristic: Callable, verbose: bool =False): cell_visits=0 إليهما في القسم السابق. shortest distance = {} shortest_distance [start_cell] = 0 parent = {} parent[start_cell] = start_cell expansion_candidates = fully expanded = set() set([start_cell]) # while there are still cells to be expanded while len(expansion_candidates) > 0: best_cell = get_best_candidate (expansion_candidates, shortest_distance, heuristic) if best cell == None: break if verbose: print('\nExpanding cell', best_cell) # if the target cell has been reached, reconstruct the shortest path and exit if best cell == target_cell: 118

119 وزارة التعليم Ministry of Education 2024-1446 shortest_path=reconstruct_shortest_path(parent,start_cell,target_cell) return shortest_path, shortest_distance[target_cell],cell_visits for neighbor,cost in get_neighbors(maze, best_cell): if verbose: print('\nVisiting neighbor cell', neighbor) cell_visits+=1 # first time this neighbor is reached if neighbor not in expansion_candidates and neighbor not in fully_expanded: expansion_candidates.add(neighbor) parent[neighbor] = best_cell #mark the best_cell as this neighbor's parent # update the shortest distance for this neighbor shortest_distance[neighbor] = shortest_distance[best_cell] + cost # this neighbor has been visited before, but a better (shorter) path to it has just been found elif shortest_distance[neighbor] > shortest_distance[best_cell] + cost: shortest_distance[neighbor] = shortest_distance[best_cell] + cost parent[neighbor] = best_cell if neighbor in fully_expanded: fully_expanded.remove(neighbor) expansion_candidates.add(neighbor) # all neighbors of best_cell have been inspected at this point expansion_candidates.remove(best_cell) fully_expanded.add(best_cell) return None, None, None # no solution was found وكما الحال في الدالة ( )bfs_maze_solver ، تستخدم الدالة الموضّحة بالأعلى كذلك القاموسين shortest_distance و parent لحفظ طول المسار الأقصر من خلية البداية إلى أي خلية أخرى، وحفظ عُقدة أصل الخلية في هذا المسار الأقصر. تَستخدم ورغم ذلك، تتبع الدالة ( )astar_maze_solve منهجية مختلفة لفحص الخلايا وتوسيعها ، فه expansion_candidates لتتبع كل الخلايا التي يمكن توسيعها بعد ذلك. في كل تكرار، تُستخدم دالة ()get_best_candidate لتحديد أي من الخلايا المرشَّحة ستُوسِّعُها بعد ذلك. بعد اختيار الخلية المرشحة best_cell ، تُستخدم حلقة التكرار For لفحص كل الخلايا المجاورة لها. إذا كانت الخلية المجاورة تُفحص للمرة الأولى، فستصبح best_cell عُقدة الأصل للخلية المجاورة في المسار الأقصر.

وزارة التعليم Ministry of Education 2024-1446 يحدث الأمر نفسه إذا تم فحص الدالة المجاورة من قبل، ولكن فقط إذا كان المسار إلى هذه الخلية المجاورة من خلال best_cell أقصر من المسار السابق. إذا عثرت الدالة بالفعل على مسار أفضل ، فسيتعين على الخلية المجاورة العودة إلى مجموعة expansion_candidates لإعادة تقييم المسار الأقصر إلى الخلايا المجاورة لها. يُستخدم المقطع البرمجي التالي ( )astar_maze_solver لحل الحالة غير الموزونة ( Unweighted Case) للغز المتاهة 3x3 start_cell=(2,0) target_cell=(1,2) solution, distance, cell_visits=astar_maze_solver(start_cell, target_cell, small_maze, get_accessible_neighbors, constant_heuristic, verbose=False) print('\nShortest Path: ', solution). print('Cells on the Shortest Path:', len(solution)) print('Shortest Path Distance:', distance) print('Number of cell visits:', cell_visits) Shortest Path: [(2, 0), (1, 0), (0, 1), (1, 2)] Cells on the Shortest Path: 4 Shortest Path Distance: 3 Number of cell visits: 12 * ستبحث أداة الحل في البحث بأولوية الأفضل (A search solver عن المسار المحتمل الأقصر والأفضل بعد فحص 12 خلية. وهذا أكثر قليلًا من أداة الحل في البحث بأولوية الاتساع (BFS solver) التي وجدت الحل بعـد فحص 10 خلايا فقط. هذا يعود إلى بساطة الاستدلال الثابت المستخدم لإرشاد ()astar_maze_solver. وكما لاحقًا في هذا القسم، يُمكن استخدام دالة استدلال أخرى لتمكين الخوارزمية من إيجاد الحل بشكل أسرع. الخطوة التالية هي تقييم ما إذا كانت خوارزمية البحث بأولوية الأفضل (search ) قادرة على حل المتاهة الموزونة التي فشلت خوارزمية البحث بأولوية الاتساع (BFS) في العثور على أقصر مسار لها أم لا: سيتضح * start_cell=(2,0) target_cell=(1,2) horz_vert_w=1 # weight for horizontal and vertical moves diag_w=3 #weight for diagonal moves solution, distance, cell_visits-astar_maze_solver(start_cell, target_cell, small_maze, partial(get_accessible_neighbors_weighted, horizontal_vertical_weight=horz_vert_w, diagonal_weight=diag_w), constant_heuristic, verbose=False) 120

121 print('\nShortest Path:', solution) print('Cells on the Shortest Path: ', len(solution)) print('Shortest Path Distance: ', distance) print('Number of cell visits:', cell_visits) Shortest Path: [(2, 0), (1, 0), (0, 0), (0, 1), (0, 2), (1, 2)] Cells on the Shortest Path: 6 Shortest Path Distance: 5 Number of cell visits: 12 تُوضّح النتائج قدرة ()astar_maze_solver على حل الحالة الموزونة بالعثور على المسار الأقصر المحتمل [(2، 0) ، (1، 0) ، (0، 0) ، (0، 1)، (0، 2) ، (1، 2)] بتكلفة إجمالية قدرها .. وهذا يوضح مزايا استخدام خوارزمية بحث مستنيرة ، فهي تُمكِّنك من إيجاد الحل الأمثل باستخدام أبسط طريقة ممكنة. المقارنة بين الخوارزميات Algorithm Comparison target_cell ( الخلية المستهدفة) الخطوة التالية هي المقارنة بين خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية الأفضل A search في متاهة أكبر حجمًا وأكثر تعقيدًا. يُستخدَم المقطع البرمجي التالي بلغة البايثون لإنشاء تمثيل رقمي لهذه المتاهة: X big_maze=np.zeros( (15,15) # coordinates of the cells occupied by blocks blocks=[(2,8), (2,9), (2,10), (2,11), (2,12), (8,8), (8,9), (8,10), (8,11), (8,12), (3,8), (4,8), (5,8), (6,8), (7,8), (3,12), (4,12), (6,12), (7,12)] for block in blocks: # set the value of block-occupied cells to be equal to 1 big_maze[block] =1 شكل 2.23 خلية البداية والخلية المستهدفة للمتاهة start_cell خلية البداية ) هذه المتاهة 15×15 تحتوي على قسم من الحواجز على شكل حرف C ينبغي على اللاعب تجاوزها للوصول إلى الهدف المحدَّد بالعلامة .. ثم تُستخدم أداة الحل في البحث بأولوية الاتساع (BFSolver ) وأداة الحل في البحث بأولوية الأفضل (search solver ) لحل الإصدارات الموزونة وغير الموزونة من هذه المتاهة كبيرة الحجم وزارة التعليم Ministry of Education 2024-1446 start_cell=(14,0) target_cell=(5,10) الإصدار غير الموزون solution_bfs_unw, distance_bfs_unw, cell_visits_bfs_unw=bfs_maze_solver(start_cell, target_cell, big_maze, get_accessible_neighbors,

وزارة التعليم Ministry of Education 2024-1446 print('\nBFS unweighted.') verbose=False) print('\nShortest Path: ', solution_bfs_unw) print('Cells on the Shortest Path:', len(solution_bfs_unw)) print('Shortest Path Distance:', distance_bfs_unw) print('Number of cell visits:', cell_visits_bfs_unw) solution_astar_unw, distance_astar_unw, cell_visits_astar_unw=astar_maze_solver( start_cell, target_cell, big_maze, get_accessible_neighbors, constant heuristic, verbose=False) print('\nA* Search unweighted with a constant heuristic.') print('\nShortest Path: ', solution_astar_unw) print('Cells on the Shortest Path:', len(solution_astar_unw)) print('Shortest Path Distance:', distance_astar_unw) print('Number of cell visits:', cell_visits_astar_unw) BFS unweighted. Shortest Path: [(14, 0), (13, 1), (12, 2), (11, 3), (10, 4), (9, 5), (8, 6), (8, 7), (9, 8), (9, 9), (9, 10), (9, 11), (9, 12), (8, 13), (7, 13), (6, 13), (5, 12), (4, 11), (5, 10)] Cells on the Shortest Path: 19 Shortest Path Distance: 18 Number of cell visits: 1237 A* Search unweighted with a constant heuristic. Shortest Path: [(14, 0), (13, 1), (12, 2), (11, 3), (10, 4), (10, 5), (10, 6), (9, 7), (9, 8), (10, 9), (9, 10), (9, 11), (9, 12), (8, 13), (7, 13), (6, 13), (5, 12), (6, 11), (5, 10)] Cells on the Shortest Path: 19 Shortest Path Distance: 18 Number of cell visits: 1272 start_cell=(14,0) target_cell = (5,10) horz_vert_w=1 diag_w=3 الإصدار الموزون solution_bfs_w, distance_bfs_w, cell_visits_bfs_w=bfs_maze_solver(start_cell, target_cell, 122

123 وزارة التعليم Ministry of Education 2024-1446 print('\nBFS weighted.') big_maze, partial(get_accessible_neighbors_weighted, horizontal_vertical_weight=horz_vert_w, diagonal_weight=diag_w), verbose=False) print('\nShortest Path:', solution_bfs_w) print('Cells on the Shortest Path:', len(solution_bfs_w)) print('Shortest Path Distance:', distance_bfs_w) print('Number of cell visits:', cell_visits_bfs_w) solution_astar_w, distance_astar_w, cell_visits_astar_w=astar_maze_solver(start_cell, target_cell, big_maze, partial(get_accessible_neighbors_weighted, horizontal_vertical_weight=horz_vert_w, diagonal_weight=diag_w), constant heuristic, verbose=False) print('\nA* Search weighted with constant heuristic.') print('\nShortest Path:', solution_astar_w) print('Cells on the Shortest Path:', len(solution_astar_w)) print('Shortest Path Distance:', distance_astar_w) print('Number of cell visits:', cell_visits_astar_w) BFS weighted. Shortest Path: [(14, 0), (14, 1), (14, 2), (13, 2), (13, 3), (12, 3), (12, 4), (11, 4), (11, 5), (10, 5), (10, 6), (9, 6), (9, 7), (9, 8), (9, 9), (9, 10), (9, 11), (9, 12), (9, 13), (8, 13), (7, 13), (6, 13), (5, 13), (5, 12), (4, 11), (5, 10)] Cells on the Shortest Path: 26 Shortest Path Distance: 30 Number of cell visits: 1235 A* Search weighted with constant heuristic. Shortest Path: [(14, 0), (13, 0), (12, 0), (11, 0), (10, 0), (9, 0), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6), (9, 7), (9, 8), (9, 9), (9, 10), (9, 11), (9, 12), (9, 13), (8, 13), (7, 13), (6, 13), (5, 13), (5, 12), (5, 11), (5, 10)] Cells on the Shortest Path: 26 Shortest Path Distance: 25 Number of cell visits: 1245

وزارة التعليم Ministry of Education 2024-1446 تتوافق النتائج مع تلك التي حصلت عليها في المتاهة الصغيرة وهي كالتالي: نجحت خوارزميتا البحث بأولوية الاتساع (BFS) والبحث بأولوية الأفضل (search ) في العثور على المسار الأقصر للإصدار غير الموزون. وجدت خوارزمية البحث بأولوية الاتساع (BFS) الحل بعد فحص عدد أقلّ من الخلايا وهو 1237 مقابل 1272 في خوارزمية البحث بأولوية الأفضل search ) . • فشلت خوارزمية البحث بأولوية الاتساع (BFS) في العثور على المسار الأقصر للإصدار الموزون، حيث عثرت على مسار بطول 30 وحدة. عثرت خوارزمية البحث بأولوية الأفضل ( A search على المسار الأقصر للإصدار الموزون، حيث عثرت على مسار بطول 25 وحدة. يُستخدم المقطع التالي لتمثيل المسار الأقصر الذي وجدته الخوارزميتان؛ خوارزمية البحث بأولوية الاتساع (BFS ) وخوارزمية البحث بأولوية الأفضل search ) للإصدار الموزون كالتالي: maze_bfs_w=big_maze.copy() for cell in solution_bfs_w: maze_bfs_w[cell]=2 plot_maze(maze_bfs_w) maze_astar_w=big_maze.copy( ) for cell in solution_astar_w: maze_astar_w[cell]=2 plot_maze(maze_astar_w) خوارزمية البحث بأولوية الاتساع (BFS). خوارزمية البحث بأولوية الأفضل (A search) . شكل 2.24: مقارنة بين حلّي خوارزميتي البحث بأولوية الاتساع والبحث بأولوية الأفضل يؤكد التمثيلان أن الطبيعة المستنيرة لخوارزمية البحث بأولوية الأفضل (A* search) تسمح لها بتجنب الحركة القُطرية؛ لأن تكلفتها أعلى من الحركتين الأفقية والرأسية. ومن ناحية أخرى تتجاهل خوارزمية البحث بأولوية الأفضل (BFS) غير المستنيرة تكلفة كل حركة وتُعطي حلًا أعلى تكلفة . وفيما يلي مقارنة عامة بين الخوارزميات المستنيرة وغير المستنيرة كما هو موضح في الجدول 2.6 124

جدول :2.6 مقارنة بين الخوارزميات المستنيرة وغير المستنيرة معايير المقارنة التعقيد الحسابي (Computational Complexity) المستنيرة غير المستنيرة أقل تعقيدا. أكثر تعقيدًا حسابيًا. الكفاءة (Efficiency) أسرع في عمليات البحث. أبطأ من الخوارزميات المستنيرة. أفضل في حل مشكلات البحث واسع غير عملية لحل مشكلات البحث الأداء (Performance) النطاق. واسع النطاق. الفعالية (Effectiveness) تحقق حلولا مناسبةً بشكل عام. تحقق الحل الأمثل. ومع ذلك، تُظهر النتائج أن خوارزمية البحث بأولوية الاتساع (BFS) يمكنها العثور على الحل الأمثل بشكل سريع بفحص عدد أقل من الخلايا في الحالة غير الموزونة. يمكن مُعالجة ذلك بتوفير استدلال أكثر ذكاءً لخوارزمية البحث بأولوية الأفضل .A search . والاستدلال الشهير في التطبيقات المستندة إلى المسافة هو مسافة مانهاتن (Manhattan Distance ) ، وهي مجموع الفروقات المطلقة بين إحداثِيَّي نقطتين مُعطاتين. يوضح الشكل أدناه مثالًا على كيفية حساب مسافة مانهاتن مسافة مانهاتن Manhattan Distance Manhattan (A, B) = |x1-x2 | + |y1-y2| B (x2, y2) A (x1, y1) شكل 2.25: مسافة مانهاتن 125 وزارة التعليم Ministry of Education 2024-1446

وزارة التعليم Ministry of Education 2024-1446 يمكن تطبيق هذا بسهولة في صورة دالة البايثون كما يلي: def manhattan_heuristic(candidate_cell:tuple, target_cell:tuple): x1,y1-candidate_cell x2,y2 target_cell return abs(x1 - x2) + abs(y1 - y2) يُستخدَم المقطع البرمجي التالي لاختبار إمكانية استخدام هذا الاستدلال الذكي لدعم ()astar_maze_solver في البحث بشكل أسرع في كل من الحالات الموزونة وغير الموزونة: start_cell=(14,0) target_cell=(5,10) solution_astar_unw_mn, distance_astar_unw_mn, cell_visits_astar_unw_mn=astar_ maze_solver(start_cell, target_cell, big_maze, get_accessible_neighbors, manhattan_heuristic, verbose=False) print('\nA* Search unweighted with the Manhattan heuristic.') print('\nShortest Path:', solution_astar_unw_mn) print('Cells on the Shortest Path:', len(solution_astar_unw_mn)) print('Shortest Path Distance:', distance_astar_unw_mn) print('Number of cell visits:', cell_visits_astar_unw_mn) horz_vert_w=1 # weight for horizontal and vertical moves diag_w=3 #weight for diagonal moves solution_astar_w_mn, distance_astar_w_mn, cell_visits_astar_w_mn=astar_maze_ solver(start_cell, target_cell, big_maze, partial(get_accessible_neighbors_weighted, horizontal_vertical_weight=horz_vert_w, diagonal_weight=diag_w), manhattan heuristic, verbose=False) print('\nA* Search weighted with the Manhattan heuristic.') print('\nShortest Path:', solution_astar_w_mn) print('Cells on the Shortest Path:', len(solution_astar_w_mn)) print('Shortest Path Distance:', distance_astar_w_mn) print('Number of cell visits:', cell_visits_astar_w_mn) 126

A* Search unweighted with the Manhattan heuristic. Shortest Path: [(14, 0), (13, 1), (12, 2), (11, 3), (10, 4), (9, 5), (8, 6), (8, 7), (9, 8), (9, 9), (9, 10), (9, 11), (9, 12), (8, 13), (7, 13), (6, 13), (5, 12), (5, 11), (5, 10)] Cells on the Shortest Path: 19 Shortest Path Distance: 18 Number of cell visits: 865 A* Search weighted with the Manhattan heuristic. Shortest Path: [(14, 0), (14, 1), (13, 1), (12, 1), (12, 2), (12, 3), (12, 4), (12, 5), (12, 6), (12, 7), (11, 7), (11, 8), (10, 8), (9, 8), (9, 9), (9, 10), (9, 11), (9, 12), (9, 13), (8, 13), (7, 13), (6, 13), (5, 13), (5, 12), (5, 11), (5, 10)] Cells on the Shortest Path: 26 Shortest Path Distance: 25 Number of cell visits: 1033 تؤكد النتائج أن استدلال مسافة مانهاتن (Manhattan Distance يمكن استخدامه لدعم خوارزمية البحث بأولوية الأفضل (A search في العثور على المسارات الأقصر المحتملة بفحص أقل عدد من الخلايا في كل من ) الحالات الموزونة وغير الموزونة. علمًا بأن استخدام هذا الاستدلال الأكثر ذكاءً يفحص عددًا أقل من الخلايا من ذلك المستخدم في خوارزمية البحث بأولوية الاتساع (BFS). يُلخّص الجدول 2.7 النتائج حول متغيرات الخوارزميات المختلفة في المتاهة الكبيرة: جدول :2.7 مقارنة بين أداء الخوارزميات خوارزمية البحث بأولوية خوارزمية البحث بأولوية خوارزمية البحث بأولوية الاتساع (BFS) الأفضل (A* search) بالاستدلال الثابت الأفضل A search باستدلال مانهاتن المسافة = 25، وفحصت 1033 المسافة = 25، وفحصت 1245 المسافة = 30 ، وفحصت 1235 الموزونة المسافة = 18، وفحصت 865 المسافة = 18، وفحصت 1272 المسافة = 18، وفحصت 1237 غير الموزونة الدرس: يُوضّح الجدول مزايا استخدام الطَّرائق الأكثر ذكاءً لحل المشكلات المستندة إلى البحث مثل تلك الموضحة بهذا التحول من خوارزمية البحث بأولوية الاتساع (BFS) غير المستنيرة إلى خوارزمية البحث بأولوية الأفضل (A search المستنيرة حَقَّق نتائج أفضل، كما أتاح إمكانية حل المشكلات الأكثر تعقيدا. • يُمكن تحسين ذكاء خوارزميات البحث المستنيرة باستخدام دوال الاستدلال الأفضل التي تسمح لها بالعثور على الحل الأمثل بشكل أسرع. 127 وزارة التعليم Ministry of Education 2024-1446

وزارة التعليم Ministry of Education 2024-1446 تمرينات اذكر تطبيقين لخوارزميات البحث. حدد الاختلافات بين خوارزميات البحث المستنيرة وغير المستنيرة، ثم اذكر مثالا على كل خوارزمية. 1 2 128

129 اشرح بإيجاز كيف تعمل خوارزمية البحث بأولوية الأفضل (A* search). عدل المقطع البرمجي بتغيير الوزن القُطري Diagonal Weight من 3 إلى 1.5. ماذا تُلاحظ ؟ هل يتغير المسار الأقصر في حالتي خوارزمية البحث بأولوية الاتساع (BFS) وخوارزمية البحث بأولوية الأفضل (A* search )؟ عَدِّل المقطع البرمجي بتبديل إحداثيات خلية البداية مع احداثيات الخلية المستهدفة. ماذا تُلاحظ؟ هل المسار هو نفسه كما كان سابقًا للحالات الموزونة من خوارزميتي البحث بأولوية الاتساع (BFS) والبحث بأولوية وزارة التعليم Ministry of Education 2024-1446 $(A* search) is 3 4 5