4. A* algorithm

A star algorithm은 길찾기 알고리즘으로 유다시티 수업 마지막 프로젝트로도 나왔다.

생각보다 재밌는 알고리즘 이었다.

 

그리디 알고리즘으로도 길찾기 문제는 해결할 수 있는데, 사실상 효율적이지 않다는 문제가 있다.

start node 중심에서 원형으로 모든 가능성에 대해서 길찾기를 하게 됨으로

방향성을 가지고 길찾기를 할 수 있도록, 알고리즘에 약간의 수정을 해야 한다.

 

function = g + h

 

g = cost of the path

h = estimated distance to the goal

 

위의 function의 값이 최소화가 되는 방향으로 알고리즘을 짜는 문제다. 

 

아래는 내가 프로젝트로 냈었던 문제다. 피타고라스정리를 이용해서 거리를 계산해가고 있으며

그리디 알고리즘에 h 요소를 집어넣어 문제를 해결할 수 있었다.

 

def shortest_path(M,start,goal):
    explored = []
    frontiers = {}

    for neighbour in M.roads[start]:
        route = [start, neighbour]
        distance_from_start = math.sqrt((M.intersections[start][0] - M.intersections[neighbour][0])**2 + (M.intersections[start][1] - M.intersections[neighbour][1])**2)
        distance_to_goal = math.sqrt((M.intersections[goal][0] - M.intersections[neighbour][0])**2 + (M.intersections[goal][1] - M.intersections[neighbour][1])**2)
        total_distance = distance_from_start + distance_to_goal
        frontiers[neighbour] = Intersection(route, distance_from_start, distance_to_goal, total_distance)

    explored.append(start)

    while frontiers:
        smallest_frontier = sorted(frontiers.items(), key=lambda x: x[1].total_distance)[0]
        smallest_fron_key = smallest_frontier[0]
        explored.append(smallest_fron_key)
        if smallest_fron_key == goal:
            print("shortest path called")
            return smallest_frontier[1].route

        for neighbour in M.roads[smallest_fron_key]:
            if neighbour not in explored:
                route = smallest_frontier[1].route.append(neighbour)
                distance_from_start = smallest_frontier[1].distance_from_start + math.sqrt(
                    (M.intersections[smallest_fron_key][0] - M.intersections[neighbour][0])**2 + (M.intersections[smallest_fron_key][1] - M.intersections[neighbour][1])**2
                    )
                distance_to_goal = math.sqrt((M.intersections[goal][0] - M.intersections[neighbour][0])**2 + (M.intersections[goal][1] - M.intersections[neighbour][1])**2)
                total_distance = distance_from_start + distance_to_goal
                if frontiers.get(neighbour) != None and total_distance > frontiers[neighbour].total_distance:
                    continue
                frontiers[neighbour] = Intersection(route, distance_from_start, distance_to_goal, total_distance)

    if not frontiers:
        return -1