|
||||||||
Manhattan Distance - Python Automation and Machine Learning for ICs - - An Online Book - |
||||||||
Python Automation and Machine Learning for ICs http://www.globalsino.com/ICs/ | ||||||||
Chapter/Index: Introduction | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | Appendix | ||||||||
================================================================================= Manhattan distance is a common heuristic used in Greedy Best-First Search and other algorithms. It is a distance metric often employed in grid-based environments or problems where movement is restricted to horizontal and vertical paths, as opposed to diagonal movement. In the Greedy Best-First Search, the Manhattan distance heuristic is used to estimate the cost of reaching the goal from a given state. The Manhattan distance between two points is calculated as the sum of the absolute differences of their Cartesian coordinates. It is also known as the L1 norm or taxicab distance. For a grid-based problem with two-dimensional coordinates (x1, y1) and (x2, y2), the Manhattan distance (D) is given by: In the Greedy Best-First Search, this distance is used as a heuristic to estimate the cost from the current state to the goal state. The algorithm selects the path that minimizes this heuristic value at each step, prioritizing paths that seem to be closer to the goal based on the Manhattan distance. While the Manhattan distance is a simple and efficient heuristic, it may not always provide the most accurate estimates, especially in situations where diagonal movements are allowed. In such cases, other heuristics like Euclidean distance or Chebyshev distance might be more appropriate. Nonetheless, Manhattan distance remains a popular choice in grid-based environments and is frequently used in pathfinding algorithms. While Manhattan Distance is a useful heuristic in many scenarios and can significantly improve the efficiency of search processes, it does not guarantee optimality. The efficiency of a heuristic is measured by its ability to guide the search algorithm toward the goal state in a manner that is both effective and efficient. Some consideratios are: i) Admissibility: An admissible heuristic is one that never overestimates the true cost to reach the goal from any given state. If Manhattan Distance is admissible, it ensures that the search algorithm will always explore the optimal path first. Manhattan Distance is admissible when used in problems where only horizontal and vertical movements are allowed. In such cases, the Manhattan Distance provides the minimum possible cost to reach the goal. ii) Grid-Based Environments: Manhattan Distance is particularly effective in grid-based environments where movements are restricted to horizontal and vertical paths. In these situations, the heuristic accurately reflects the number of grid cells that need to be traversed to reach the goal. iii) Efficiency, but not Necessarily Optimality: While Manhattan Distance can significantly improve efficiency by guiding the search algorithm toward the goal, it doesn't guarantee finding the globally optimal solution. The algorithm may find a solution that is close to optimal but not necessarily the best possible solution. iv) Limitations in Some Environments: In environments where diagonal movements are allowed, Manhattan Distance may not be as effective as other heuristics like Euclidean distance or Chebyshev distance. It can sometimes underestimate the true cost when diagonal paths are available, leading to suboptimal solutions. ============================================
|
||||||||
================================================================================= | ||||||||
|
||||||||