Python 95% A* algorithm with explanation


  • 0
    B

    There are some posts using BFS + PriorityQueue implementations in this question, some of them actually use A* algorithm but without any explanation. It is kind of dangerous since A* is not applicable for all shortest path problems.

        def heuristic(a, b): # it is an admissible heuristic
            return abs(b[0] - a[0]) + abs(b[1] - a[1])
    

    A* algorithm can be used to solve the problem because the distance heuristic function of the goal and current location is admissible, that means this heuristic never overestimates the real distance between the goal and current location.

    Basically A* algorithm is a best-first search algorithm. It stores the neighbors in a priorityQueue and explores the most promising neighbor first. An admissible heuristic will guarantee the shortest path on the first time you reach the goal because the later visited positions will have worse results than their heuristic values.

    For more details about A* algorithm, please refer the wiki page: https://en.wikipedia.org/wiki/A*_search_algorithm

    Python implementation:

    from heapq import *
    
    class Solution(object):
        def shortestDistance(self, maze, start, destination):
            """
            :type maze: List[List[int]]
            :type start: List[int]
            :type destination: List[int]
            :rtype: int
            """
    
            def get_neighbors(start):
                neighbors = []
                i, j = start
                if i - 1 >= 0 and maze[i-1][j] == 0:
                    while i - 1 >= 0 and maze[i-1][j] == 0: i-=1
                    neighbors.append((i,j))
                i, j = start
                if j - 1 >= 0 and maze[i][j-1] == 0:
                    while j - 1 >= 0 and maze[i][j-1] == 0: j -= 1
                    neighbors.append((i, j))
                i, j = start
                if i + 1 < len(maze) and maze[i+1][j] == 0:
                    while i + 1 < len(maze) and maze[i+1][j] == 0: i += 1
                    neighbors.append((i, j))
                i, j = start
                if j + 1 < len(maze[0]) and maze[i][j+1] == 0:
                    while j + 1 < len(maze[0]) and maze[i][j+1] == 0: j += 1
                    neighbors.append((i, j))
                return neighbors
    
            def heuristic(a, b):
                return abs(b[0] - a[0]) + abs(b[1] - a[1])
    
            start = (start[0], start[1])
            destination = (destination[0], destination[1])
            gscore = {start: 0}
            fscore = {start: heuristic(start, destination)}
            open_heap = []
            open_set = set()
            close_set = set()
    
            heappush(open_heap, (fscore[start], start))
            open_set.add(start)
    
            while open_heap:
    
                current = heappop(open_heap)[1]
                open_set.remove(current)
    
                if current == destination:
                    return gscore[current]
    
                close_set.add(current)
                for neighbor in get_neighbors(current):
                    tentative_score = gscore[current] + heuristic(current, neighbor)
                    if neighbor in close_set and tentative_score >= gscore.get(neighbor, 0):
                        continue
    
                    if tentative_score < gscore.get(neighbor, 0) or neighbor not in open_set:
                        gscore[neighbor] = tentative_score
                        fscore[neighbor] = tentative_score + heuristic(neighbor, destination)
                        if neighbor in open_set:
                            for i in xrange(len(open_heap)):
                                if open_heap[i][1] == neighbor:
                                    open_heap.pop(i)
                                    break
                        heappush(open_heap, (fscore[neighbor], neighbor))
                        open_set.add(neighbor)
    
            return -1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.