Unveiling A* Algorithm: Navigating Advanced Search in Software Engineering

In the previous article Beyond DFS and BFS: Unraveling Advanced Search Techniques in Software Engineering, we embarked on a journey through fundamental search algorithms, exploring the nuances of Depth-First Search (DFS) and Breadth-First Search (BFS). While these techniques form the bedrock of graph traversal, their limitations become apparent as problems increase in complexity. This article, introduce advanced approaches like informed search techniques, using A* algorithms as a prime example. We'll also relate these concepts to real-world scenarios, such as the Google Maps search query, to demonstrate how these algorithms translate into practical applications.

Consider the above-depicted network showcasing city connections. In this illustration, City A serves as the origin, while City B stands as the desired destination. The objective at hand is to identify the shortest path linking these two cities. Starting from City A, we encounter neighboring cities A1, A2, A3, and A4. Similarly, proximate to City B, we find cities denoted as B1, B2, and B3. The blue lines interconnecting the cities on the diagram signify the true distances, quantified in kilometers, between them.

Now, let's apply the Uniform Cost Search, also referred to as Dijkstra’s algorithm (for those unfamiliar with this algorithm, kindly read this article). While employing this method and accounting for actual costs, our exploration endeavors lead us to scrutinize the below mention subsequent cities during our search:

Upon reaching City B, the algorithm's exploration ceases. However, upon closer observation, it becomes evident that prior to arriving at City B, the algorithm canvassed both areas of interest: cities proximate to City A as well as those near City B. This comprehensive traversal highlights a limitation of the UCS algorithm. While human intuition guides us to skip visiting cities near City A owing to our ability to intuit that they cannot offer a more cost-effective path than those adjacent to the target City B or in that direction. This algorithm lacks such foresight. As a result, it dutifully examines all nearby cities to A before pinpointing the optimal path.

But assume a scenario where we furnish the algorithm with supplemental insights regarding the target node. Armed with this information, the algorithm could make more informed decisions when selecting the next city for assessment, expediting the process of ascertaining whether it corresponds to the target city.

One approach involves computing the Euclidean distance between the current node and the target node. Leveraging a mathematical equation based on provided latitude and longitude coordinates, this distance can be determined swiftly through an O(1) operation.

Assuming (lat1, lon1) and (lat2, lon2) are the coordinates of two points
in decimal degrees

Euclidean Distance = sqrt((lat2 - lat1)^2 + (lon2 - lon1)^2)         

This additional piece of information empowers the algorithm to navigate with greater efficiency, capitalizing on geometric insights to accelerate the search process.

Figure 2 shows a line of sight distances from each city to target city B. Here let's assume that when we put the city into the queue, we will use the below equation to calculate a cost for the next city:

cost = cost of source city to current city 
      + Euclidian distance of current city to target city        

Now if we run the same above uniform search algorithm again, then will obtain the below table compared to the earlier one.

The above table vividly illustrates the transition in our algorithm's trajectory. After starting from City A, the algorithm promptly directs its focus to City B3(search space marked with a black box from search space marked with a red box), seamlessly transitioning to the distinct realm search space. This agility stems from the algorithm now possessing insights about the target.

It harnesses the Euclidean distance, discerning the directional cues embedded within the coordinates. This calculated distance serves as a compass, guiding the algorithm's journey, and channeling its efforts towards the destination-centric expanse.

Let's bring these concepts into a real-world context, like using a uniform cost search on Google Maps. This scenario helps us understand the importance of the extra information we discussed earlier. Imagine a situation where there are many places nearby that need to be checked against the target location. Without the awareness of the target's characteristics, the exploration process could become quite complex.

Think of it like this: when you're trying to find the shortest route on Google Maps, you're dealing with a multitude of nearby options. Without having a good idea of where your destination is in relation to these options, things can get confusing.

However, when we incorporate the extra information – those smart insights we talked about – the game changes. These insights give us a way to make decisions that make sense. For instance, let's say there's a lot of traffic nearby, but we know the exact direction of our destination. This knowledge helps us make choices that get us to our goal faster, even amidst all the nearby distractions.

This kind of extra information gives us a strategic advantage. It's like having a map that not only shows us where things are but also hints at the best path to take. In our tech-driven world, combining these insights with smart algorithms lets us tackle complex situations with efficiency and accuracy. It's a bit like adding a touch of human-like intuition to our digital decision-making.

Heuristic value

This additional information we've been discussing is what we call a heuristic value. However, the choice of a proper heuristic value is crucial. We want a heuristic value that doesn't exaggerate the costs or make things seem farther than they actually are. Finding the right balance is key – a good heuristic should provide a realistic estimate without overestimating the cost.

In the realm of heuristic values, an admissible heuristic stands out as a preferred choice.

Admissible heuristic: An admissible heuristic never overestimates the true cost to reach the goal from any given point. This accuracy ensures that the algorithm doesn't get led astray by inflated estimations.

There's also an interesting relationship between the cost of the current node, its heuristic value, and the heuristic value of the previous node. This relationship is based on the triangle inequality principle.

In simple terms, the sum of the cost of the current node and its heuristic value should always be greater than the heuristic value of the previous node. This principle helps maintain the logical flow of exploration and ensures our algorithm navigates within sensible boundaries.

Mastering the art of selecting and incorporating heuristic values transforms algorithms into efficient navigators, making calculated decisions that mirror our intuitive human judgments.

In our upcoming article, we'll delve into various iterations of the A* search algorithm and explore their practical applications. Stay tuned for insights into how these variants enhance our problem-solving capabilities.

Manish Joshi

Senior Software Engineer