Manhattan distance :
The Manhattan distance, also known as the taxicab distance, is a measure of distance between two points in a grid-based system. It is calculated by taking the absolute difference of the two points’ coordinates in each dimension, summing those differences, and then returning the result.
For example, consider two points, A and B, in a two-dimensional grid. Point A has coordinates (3,5) and point B has coordinates (6,2). To find the Manhattan distance between these two points, we first find the absolute difference in the x-coordinates, which is |3-6| = 3. We then find the absolute difference in the y-coordinates, which is |5-2| = 3. Finally, we sum these differences to get 3+3 = 6, which is the Manhattan distance between points A and B.
Another example, consider two points, C and D, in a three-dimensional grid. Point C has coordinates (7,4,2) and point D has coordinates (1,3,9). To find the Manhattan distance between these two points, we first find the absolute difference in the x-coordinates, which is |7-1| = 6. We then find the absolute difference in the y-coordinates, which is |4-3| = 1. Finally, we find the absolute difference in the z-coordinates, which is |2-9| = 7. We then sum these differences to get 6+1+7 = 14, which is the Manhattan distance between points C and D.
The Manhattan distance is commonly used in a variety of contexts, including pathfinding algorithms in computer science and clustering algorithms in machine learning. In pathfinding, the Manhattan distance can be used to determine the “cost” of moving from one point to another, as it reflects the number of steps required to move horizontally and vertically to reach the destination point. In clustering, the Manhattan distance can be used to measure the similarity between points, with smaller distances indicating a closer relationship between points.
In addition to its practical applications, the Manhattan distance also has some interesting properties that make it a useful measure of distance. For example, it satisfies the “triangle inequality,” which states that the sum of the lengths of any two sides of a triangle must be greater than or equal to the length of the third side. This property is important because it allows us to use the Manhattan distance in a variety of algorithms that require the triangle inequality to be satisfied.
Furthermore, the Manhattan distance is often used as a “heuristic” in pathfinding algorithms, which means that it provides an estimate of the cost of moving from one point to another. This property allows us to quickly and efficiently find approximate solutions to complex problems, such as finding the shortest path through a maze.
Overall, the Manhattan distance is a useful and versatile measure of distance that has a variety of applications in fields such as computer science and machine learning. By taking the absolute difference of the coordinates in each dimension and summing these differences, we can quickly and easily determine the Manhattan distance between two points in a grid-based system.