Euclidean distance measures the straight-line separation between points by taking the square root of the sum of squared coordinate differences. It provides a geometric notion of closeness for numerical data and spatial locations. section 4.3.3 section 11.3
Use Euclidean distance to:
- Estimate the remaining cost from a node to a destination in A* search. section 4.3.3
- Represent closeness among points in numerical, image, audio, text, or spatial data. section 11.3
- Create distance heatmaps between points in traveling-salesperson problem instances. section 11.7
Routing and TSP
In A* routing, straight-line distance supplies h(n), the estimated cost from node n to the goal, alongside the traveled cost g(n). In TSP experiments, pairwise Euclidean distances appear as a normalized heatmap and help describe relationships among points before a model constructs a tour. section 4.3.3 section 11.7
Algorithm 4.4 A* algorithm
Inputs: Source node, Destination node
Output: Route from source to destination
Initialize A* heuristic ← sum of straight-line distance to source and destination
Initialize PQ ← min heap according to A* heuristic
Initialize frontier ← a PQ initialized with source
Initialize explored ← empty
Initialize found ← False
While frontier is not empty and found is False do
Set node ← frontier.pop()
Add node to explored
For child in node.expand() do
If child is not in explored and child is not in frontier then
If child is destination then
Update route ← child.route()
Update found ← True
Add child to frontier
Return route
Trace how a straight-line estimate participates in A* node selection, frontier management, expansion, and route construction. section 4.3.3
