شرح وتطبيق على خوارزمية البحث A*

إيجاد الطريق الأفضل هي من التطبيقات الأقدم والأكثر شعبية في علوم الحاسوب، يمكنك عمليا إيجاد الطريق الأمثل من منطلق إلى مستقر بإضافة التكلفة التي يمكن تكون (مال، وقت.. الخ).

خوارزمية A* هي الخيار الأفضل والأكثر استخداماً في هذا النوع من المسائل، لنتابع في هذا المقال لماذا!؟

يتضمن هذا المقال:

• ماهي خوارزميات البحث؟
• لماذا خوارزمية A*؟
• مدخلات ومخرجات الخوارزمية
• تطبيق عملي

ماهي خوارزميات البحث؟

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

لماذا خوارزمية A*؟

هي خوارزمية متطورة من خوارزميات البحث بالعرض أولاً (Breadth-First Search algorithm)، تتسم بالمثالية والكمالية.

يقصد بالمثالية أنها بالتأكيد سوف تخرج الطريق الأقل كلفة (تعطي الحل الأمثل) والكمالية أي أنها سوف توجد كافة الطرق المتوفرة التي تصل بين المنطلق والمستقر (كل الحلول المحققة لشرط).

اذاً هل هذا يجعل من A*   الأفضل؟ في معظم الحالات نعم، لكنها أيضاً بطيئة وتحتاج إلى مساحة لحفظ الطرق المتوقعة، هذا الشيء يعطي الأفضلية لباقي الخوارزميات السريعة.

لماذا اختار A* بدلاً عن باقي الخوارزميات السريعة؟

انظر الصور المرفقة، لقد قمت بالمقارنة بين خوارزمية ديكسترا (Dijkstra) وخوارزمية A*.

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

في الصورة الثانية نجد أن خوارزمية الA* تصل للحل الأكثر مثالية يمكن اعتماده للوصول من منطلق إلى مستقر، فهي تعرف من كل نقطة أي الطرق أفضل للوصول إلى الوجهة.

مدخلات ومخرجات الخوارزمية

الآن وبعد أن علمنا لما اخترناها لنعرف قليلاً عن النظرية وأساسياتها لنتعلم كيف تعمل هذه الخوارزمية.
أي أنها توجد أقل كلفة من نقطة لأخرى، يوجد معادلة واحدة كافية وهي تمثل قلب وروح هذه الخوارزمية وهي:

F = G + H

ماهي هذه المتغيرات الثلاثة ولماذا هي مهمة جداً؟ لنتابع لمعرفة الجواب.

G هو كلفة الانتقال من عقدة إلى أخرى، هذا المتغير يختلف من عقدة إلى أخرى.

H هو التابع التقديري (الإرشادي) بين العقدة الحالية والعقدة الهدف، تكون هذه القيمة غير حقيقية ولكنها اقرب إلى الحقيقة المحسوبة بين المنطلق والمستقر (المصدر والوجهة).

F هو مجموع المتغيرين السابقين ويعبر عن أقل كلفة للانتقال من عقدة إلى القعدة التالية لها في الطريق الأمثل.

انظر الشكل التالي لزيادة الفهم:

افترض أنه لدينا بيان صغير بالرؤوس A,B,S,E حيث S هي المنطلق وE هي المستقر.

تذكر ان الكلفة بين المنطلق والمستقر هي دائماً صفر.

القيم الإرشادية هي:

A:4, B:5, S:5, E:0

لنستخدم المعادلة لحساب الطريق الأقصر للوصول أولاً للمنطلق:

f(S) = 0 + 5 = 5

الطريق من S إلى باقي الرؤوس:

f(S-A) = 1 + 4 = 5

f(S-B) = 2 + 5 = 7

لذا سوف نختار الطريق من S-A لأنه الأقل كلفة.
الطرق من A  و B  إلى المستقر:

f(S-A-E) = (1 + 13) + 0 = 14

f(S-B-E) = (2 + 5) + 0 = 7

بعد الحسابات، وجدنا أن B أوصلتنا للطريق الأمثل والأقل كلفة، هكذا نستخدم المعادلة للوصول إلى الطريق الأمثل.
بعد استيعابنا للمعادلة، لننتقل الآن لنرى كيف تعمل الخوارزمية:

بداية لننشئ لائحتين سوف تساعدنا في فهم الطريق نسميهما (Open) و (Closed).

• أضف عقدة بداية إلى لائحة.
• لكل عقد الجوار اوجد الأقل كلفة أي F.
• بدل إلى اللائحة الأخرى:
  • لكل العقد المتاخمة للعقدة الحالية.
  • إذا لا يمكن الوصول للعقدة تجاهلها وإلا:
    • إذا العقدة ليست موجودة في اللائحة (Open) ضعها في القائمة واحسب F,H,G.
    • إذا العقدة موجودة تحقق من ان الطريق الذي تقدمه أقل من الطريق الحالي واستبدله إذا كان كذلك.
  • أوقف العمل عندما:
    • تصل إلى المستقر (الوجهة).
    • لم تتمكن من إيجاد الوجهة مرورا بكل الاحتمالات.

الكود المزيف (Pseudo-Code) لهذه الخوارزمية كما يلي:

let the openList equal empty list of nodes
let the closedList equal empty list of nodes
put the startNode on the openList (leave it's f at zero)
while the openList is not empty
let the currentNode equal the node with the least f value
remove the currentNode from the openList
add the currentNode to the closedList
if currentNode is the goal
You've found the end!
let the children of the currentNode equal the adjacent nodes
for each child in the children
if child is in the closedList
continue to beginning of for loop
child.g = currentNode.g + distance between child and current
child.h = distance from child to end
child.f = child.g + child.h
if child.position is in the openList's nodes positions
if the child.g is higher than the openList node's g
continue to beginning of for loop
add the child to the openList

تطبيق عملي للخوارزمية

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

def Dijkstra(maze, source):
    infinity = float('infinity')
    n = len(maze)
    dist = [infinity] * n
    previous = [infinity] * n
    dist = 0
    Q = list(range(n))
    while Q:
        u = min(Q, key=lambda n: dist[n])
        Q.remove(u)
        if dist[u] == infinity:
            break
        for v in range(n):
            if maze[u][v] and (v in Q):
                alt = dist[u] + maze[u][v]
                if alt < dist[v]:
                    dist[v] = alt
                    previous[v] = u
    return dist, previous
 
def display_solution(predecessor):
    cell = len(predecessor) - 1
    while cell:
        print(cell, end='<')
        cell = predecessor[cell]
    print(0)
 
maze = ((0, 0, 0, 0, 1, 0),
        (0, 0, 0, 0, 1, 0),
        (0, 0, 0, 0, 1, 0),
        (0, 0, 0, 0, 1, 0),
        (0, 0, 0, 0, 1, 0),
        (0, 0, 0, 0, 0, 0))
graph = (
    (0, 1, 0, 0, 0, 0,),
    (1, 0, 1, 0, 1, 0,),
    (0, 1, 0, 0, 0, 1,),
    (0, 0, 0, 0, 1, 0,),
    (0, 1, 0, 1, 0, 0,),
    (0, 0, 1, 0, 0, 0,),
)
values = Dijkstra(graph, 0)
print(values)
display_solution(values[1])
values = Dijkstra(maze, 0)
print(values)
display_solution(values[1])

الخرج للكود السابق:

([0, 1, 2, 3, 2, 3], [inf, 0, 1, 4, 1, 2])
5<2<1<0
([0, inf, inf, inf, 1, inf], [inf, inf, inf, inf, 0, inf])
5
    display_solution(values[1])
  File "C:/Users/AkashkumarJainS/PycharmProjects/A Star/dijkstra.py", line 26, in display_solution
    cell = predecessor[cell]
TypeError: list indices must be integers or slices, not float

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

لنجرب نفس المدخلات في خوارزمية A*:

class Node():
    def __init__(self, parent=None, position=None):
        self.parent = parent
        self.position = position
        self.g = 0
        self.h = 0
        self.f = 0
    def __eq__(self, other):
        return self.position == other.position
def astar(maze, start, end):
    start_node = Node(None, start)
    start_node.g = start_node.h = start_node.f = 0
    end_node = Node(None, end)
    end_node.g = end_node.h = end_node.f = 0
    open_list = []
    closed_list = []
    open_list.append(start_node)
    while len(open_list) > 0:
        current_node = open_list[0]
        current_index = 0
        for index, item in enumerate(open_list):
            if item.f < current_node.f:
                current_node = item
                current_index = index
        open_list.pop(current_index)
        closed_list.append(current_node)
        if current_node == end_node:
            path = []
            current = current_node
            while current is not None:
                path.append(current.position)
                current = current.parent
            return path[::-1]
        children = []
        for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
            node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
            if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (
                    len(maze[len(maze) - 1]) - 1) or node_position[1] < 0:
                continue
            if maze[node_position[0]][node_position[1]] != 0:
                continue
            new_node = Node(current_node, node_position)
            children.append(new_node)
        for child in children:
            for closed_child in closed_list:
                if child == closed_child:
                    continue
            child.g = current_node.g + 1
            child.h = ((child.position[0] - end_node.position[0]) ** 2) + (
                    (child.position[1] - end_node.position[1]) ** 2)
            child.f = child.g + child.h
            for open_node in open_list:
                if child == open_node and child.g > open_node.g:
                    continue
            open_list.append(child)
def main():
    maze = [[0, 0, 0, 0, 1, 0],
            [0, 0, 0, 0, 1, 0],
            [0, 0, 0, 0, 1, 0],
            [0, 0, 0, 0, 1, 0],
            [0, 0, 0, 0, 1, 0],
            [0, 0, 0, 0, 0, 0]]
    graph = [[0, 1, 0, 0, 0, 0],
             [1, 0, 1, 0, 1, 0],
             [0, 1, 0, 0, 0, 1],
             [0, 0, 0, 0, 1, 0],
             [0, 1, 0, 1, 0, 0],
             [0, 0, 1, 0, 0, 0]
             ]
    start = (0, 0)
    end = (5, 5)
    end1 = (5, 5)
    path = astar(maze, start, end)
    print(path)
    path1 = astar(graph, start, end1)
    print(path1)
if __name__ == '__main__':
    main()

الخرج:

[(0, 0), (1, 1), (2, 2), (3, 3), (4, 3), (5, 4), (5, 5)]
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]

نلاحظ أن A* تتعامل مع العائق لتصل إلى حل مقبول، تقود نفسها لتعطي الخرج المطلوب.

أتمنى أن تكون قد تعرفت بشكل جيد على خوارزمية A* آلية عملها وتطبيقها، لا تتردد بالسؤال، لا تتوقف عن التعلّم.

المصادر:

https://www.edureka.co/