Оптимизация поиска пути A-Star (A *) - PullRequest
Новая
       14

Оптимизация поиска пути A-Star (A *)

0 голосов
/ 26 сентября 2019

Я недавно кодировал алгоритм поиска пути A * в Python.Это основано на системе координат, где у каждой координаты есть значение, которое является ее высотой, и существует максимальная разница высот (разница между высотой двух смежных узлов), которая решает, можем ли мы перейти к этому узлу или нет.Как мне оптимизировать это больше?Кроме того, любые предложения по улучшению кода или если вы видите какие-либо отзывы, если я где-то ошибаюсь, приветствуются!

Я пробовал несколько эвристик, таких как формула расстояния, но упомянутая здесь, кажется, работает лучше всего для меня.Поправь меня, если я ошибаюсь. 

def astar(target_cord):

    def find_neighbor_astar(current):
        neighbor_mat = dict()
        current_matrix_cord = matrix[current[0]][current[1]]
        for x in neighbor_scope:
            for y in neighbor_scope:
                x_cord = current[0]+x
                y_cord = current[1]+y
                if(x != 0 or y != 0):
                    if((x_cord) >= 0 and x_cord < max_cols and y_cord >= 0 and y_cord < max_rows and abs(current_matrix_cord - matrix[x_cord][y_cord]) <= elevation_max):
                        if(x!=0 and y!=0):
                            neighbor_mat[x_cord, y_cord] = 14 + abs(current_matrix_cord - matrix[x_cord][y_cord])
                        else:
                            neighbor_mat[x_cord, y_cord] = 10 + abs(current_matrix_cord - matrix[x_cord][y_cord])
        return neighbor_mat

    def getheuristic(current, target_cord):
        # return (int(abs(((((target_cord[0]-current[0])**2)+((target_cord[1]-current[1])**2))**0.5))*10))
        dx = abs(current[0] - target_cord[0])
        dy = abs(current[1] - target_cord[1])
        return (dx + dy) + (2**0.5 - 2) * min(dx, dy)

    parent_cord = {start_cord: (None, 0)}
    frontier_nodes_heap = [(0, start_cord)]
    frontier_nodes = dict()
    frontier_nodes[start_cord] = 0
    node_gofx = dict()
    node_gofx[start_cord] = 0
    explored_nodes = set()
    while frontier_nodes_heap:
        curr_node = heapq.heappop(frontier_nodes_heap)[1]
        del frontier_nodes[curr_node]
        curr_cost = node_gofx[curr_node]
        if(curr_node == target_cord):
            return tracepath_ucs(parent_cord, target_cord)
        explored_nodes.add(curr_node)
        for x, step_cost in find_neighbor_astar(curr_node).items():
            gofx = curr_cost + step_cost
            path_cost = gofx + getheuristic(x, target_cord)
            if x in explored_nodes:
                continue
            if(x not in frontier_nodes):
                if(x not in parent_cord):
                    parent_cord[x] = (curr_node, step_cost)
                heapq.heappush(frontier_nodes_heap,(path_cost,x))
                frontier_nodes[x] = path_cost
                node_gofx[x] = gofx
            elif(x in frontier_nodes and path_cost < frontier_nodes[x]):
                frontier_nodes_heap[frontier_nodes_heap.index((frontier_nodes[x],x))] = (path_cost, x)
                frontier_nodes[x] = path_cost
                parent_cord[x] = (curr_node, step_cost)
                node_gofx[x] = gofx
    return []
...