Understand the A* search algorithm - Python Tutorial

- Now we come to what, in some ways, is the culmination of everything we have studied so far, the A-star algorithm. The A-star search algorithm is a powerful, and widely used, algorithm for calculating shortest paths. Here are some applications. So A-star search is used very often in traffic navigational systems, including GPS. It's used a lot in social network analysis, natural language processing, machine learning. It's used for finding solutions to puzzles, and also real world situations, which can be modeled as puzzles. It's used, for example, in algorithmic training, also in robotics, and it has many applications in video games. And beyond this list, there are also many other applications. It's a very widespread and powerful algorithm. What distinguishes the A-star algorithm from the previous pathfinding algorithms we have studied is the use of a heuristic to determine the likely best choice for each step of the algorithm. A heuristic is often informally defined as a rule of thumb. In the case of the A-star algorithm, the rule of thumb is to choose the next position to visit based on its distance from the goal. In our implementation, this distance will be calculated using something called the Manhattan distance, or taxi cab distance, which means the distance between two points on a 2-D grid when the path between those two points has to follow the grid layout. It's based on the idea that a taxi will have to stay on the road and will not be able to drive through buildings. Taxi cab distance between two points is measured along the axes at right angles. And you can see on the slide here, we have an example of how you would calculate the Manhattan distance. So to get from the point on the bottom left to the point on the top, right, you can see you have to travel a certain number of blocks in a horizontal direction, and a certain number of blocks in a vertical direction. And actually, it doesn't really matter what path you take the Manhattan distance will remain the same. Another heuristic that is sometimes used in the A-star algorithm is the Euclidean distance, calculated using Pythagoras' theorem. In the A-Star algorithm, every discovered cell is assigned the following values. We have a G value, which is the best distance from the start to the current cell. We have the H value, which is the heuristic distance from the current cell to the destination. And we have the F value, which is the sum of the G value and H age value, representing the probable optimal value, i.e. that's the minimum distance based on the heuristic used. In our implementation, we calculate H values as needed without storing them. G values and predecessors are stored in a dictionary, while the priority queue contains cell coordinates along with their associated F values. That is because F value is the one of primary importance, and the other two are used just in calculating that F value. There are other ways this can be implemented, for example, creating objects representing the cells or nodes with properties containing the various values. One thing that can help you in understanding how the A-star search algorithm works, is just to be clear about the language which is being used. So, for example, we have visited versus discovered, and we have something called an open set, which contains the discovered nodes. And that means, in our implementation, the ones that have been put into the priority queue already. So they are discovered, but they're not necessarily visited. There's another piece of terminology called the closed set, which in our implementation is the nodes which have been visited. That means we have values stored for them in our G values dictionary and our predecessors dictionary. This can all be a bit abstract. For now, just make a point of remembering these key values, the G, H, and F values and what they represent. This will make the next stage a lot easier. Let's have a quick look at how the A-star search algorithm behaves in our GUI. So if I select A-star and I place my treasure, maybe up here in the top left, and I press S, you can see that A-star is actually very good at going directly for the treasure. This is in contrast to, for example, BFS. If I put the treasure in the same place and I do BFS and press S, you'll see it takes a lot longer. And let's just do one more example with A-star. Press A-star before setting your treasure. So I'll put it down there in the left hand side, press S, and you can see here kind of appearingly intelligently gives up on its first trajectory, 'cause it realizes, if that's the right word, calculates, that that's not a good direction to go. And then it tries a different path and gets there very efficiently. So that's the A-star search algorithm in action in a maze.