Đoạn code ngắn gọn thuật toán tìm kiếm A* bằng python! A-Star Search Algorithm

Code by Nguyễn Công Cường:

from queue import PriorityQueue as PQ

# def diff(frontier):

#     dict = {}

#     for t in frontier:

#         if (t[-1] not in dict) or (dict[t[-1]][0] > t[0]):

#             dict[t[-1]] = t

#     return dict

def a_star(start, goal):

    frontier = PQ()         #uu tien F(state) -> H(state)

    frontier.put((0, start[-1], start[0]))

    F = {start[0] : 0}

    G = {start[0] : 0}

    explored = []

    while not frontier.empty():

        #print('Frontier: ', diff(list(frontier.queue)))

        ff, _, state = frontier.get()      

       

        if (ff != F[state]): #giam dpt: bo qua cac state chua update

            continue

        explored.append(state)

        if state == goal[0]:

            return explored

       

        for neighbor, weight in tree[state]:

            if (neighbor not in F) or (F[neighbor] > G[state] + weight + H[neighbor]):

               

                G[neighbor] = G[state] + weight

                F[neighbor] = G[neighbor] + H[neighbor]

                frontier.put((F[neighbor], H[neighbor], neighbor))

    return False

V = [

    ('S', 10),

    ('A', 9),

    ('B', 8),

    ('C', 7),

    ('D', 6),

    ('E', 5),

    ('F', 4),

    ('G', 10),

    ('H', 10),

    ('K', 3),

    ('M', 8),

    ('N', 10),

    ('I', 6),

    ('J', 9),

    ('L', 0),

    ('Z', 0),

]

E = [

     ('S', 'A', 5)

    ,('S', 'B', 6)

    ,('S', 'C', 5)

    ,('A', 'D', 6)

    ,('A', 'E', 7)

    ,('B', 'F', 3)

    ,('B', 'G', 4)

    ,('C', 'H', 6)

    ,('C', 'K', 4)

    ,('D', 'M', 5)

    ,('D', 'N', 8)

    ,('E', 'I', 8)

    ,('F', 'J', 4)  

    ,('F', 'L', 4)

    ,('K', 'Z', 2)    

]

tree = {}

H = {}

for v in V:

    tree[v[0]] = []

    H[v[0]] = v[1]

for e in E:

    tree[e[0]].append((e[1], e[2]))

    tree[e[1]].append((e[0], e[2]))

for v in V:

    if v[1] == 0 and v != V[0]:

       

        res = a_star(V[0], v)

        if res:

            print('\nExplored: ', res, '\n')

        else:  

            print("\nKhong tim thay duong di")

Đoạn code trên là một đoạn mã Python thực hiện thuật toán A*. Thuật toán A* là một thuật toán tìm kiếm heuristics phổ biến được sử dụng để tìm đường đi ngắn nhất giữa trạng thái bắt đầu và trạng thái đích trên đồ thị.

Đoạn code định nghĩa một hàm được gọi là a_star với hai tham số đầu vào là start và goal. Hàm sử dụng một hàng đợi ưu tiên để theo dõi các trạng thái cần khám phá dựa trên ước tính chi phí, tức là tổng chi phí để đến trạng thái đó từ trạng thái bắt đầu và ước tính chi phí để đến trạng thái đích từ trạng thái hiện tại.

Thuật toán duy trì hai từ điển: F và G. F lưu trữ chi phí ước tính của một trạng thái và G lưu trữ chi phí thực tế để đến một trạng thái từ trạng thái bắt đầu. Thuật toán cũng duy trì một danh sách được gọi là explored để theo dõi các trạng thái đã được khám phá.

Từ điển tree đại diện cho đồ thị, trong đó mỗi khóa là một nút và giá trị là một danh sách các bộ ba đại diện cho các nút láng giềng và trọng số cạnh tương ứng. Từ điển H lưu trữ chi phí heuristic cho mỗi nút.

Sau đó, đoạn mã lặp lại qua tất cả các nút trong V và kiểm tra xem chi phí heuristic của chúng có bằng 0 hay không (ngoại trừ nút bắt đầu). Đối với mỗi nút như vậy, nó gọi hàm a_star với nút bắt đầu và nút hiện tại làm đối số. Nếu tìm thấy một đường đi, nó sẽ được in ra cùng với các nút đã được khám phá trong quá trình tìm kiếm. Nếu không tìm thấy đường đi, một thông báo sẽ được in ra cho biết không tìm thấy đường đi.

English Version:

The above code appears to be a Python implementation of the A* algorithm. The A* algorithm is a popular heuristic search algorithm used to find the shortest path between a starting state and a goal state in a graph.

The code defines a function called a_star that takes two arguments: start and goal. It uses a priority queue to keep track of the states to explore based on their estimated cost, which is the sum of the cost to reach the state from the starting state and the estimated cost to reach the goal state from the current state.

The algorithm maintains two dictionaries: F and G. F stores the estimated cost of a state and G stores the actual cost of reaching a state from the starting state. The algorithm also maintains a list called explored to keep track of the states that have already been explored.

The tree dictionary represents the graph, where each key is a node and the value is a list of tuples representing the neighboring nodes and their corresponding edge weights. The H dictionary stores the heuristic cost for each node.

The code then iterates over all nodes in V and checks if their heuristic cost is 0 (except for the starting node). For each such node, it calls the a_star function with the starting node and the current node as arguments. If a path is found, it is printed along with the nodes that were explored during the search. If no path is found, a message is printed stating that no path was found.