Heuristic algorithms are solutions that optimize efficiency sometimes at the expense of accuracy. The idea is that if you have a computationally expensive problem (NP-hard), it's better to come up with a good approximation in a reasonable amount of time rather than find an exact solution after a very long time.
Traveling Salesman Problem
To illustrate, I will use a classic example of an NP-hard problem: the Traveling Salesman Problem. In this problem, the goal is to determine the shortest route for our traveling salesman to pass through a given set of cities.
To conceptualize why this problem is so expensive, let's think about examples: if our salesman has to visit 3 cities, how many possible routes are there to explore? For the first stop, we have 3 choices; for the second, we have 2; and for the third, we are only left with one city. So, we have a total of 6 possible routes. This might look familiar to some as an n! problem.
3 x 2 x 1 = 3!
With only 3 cities to visit, this problem is easy to visualize. However, if we jump up to 10 cities, we are suddenly at over 3 million solutions (3,628,800 to be exact). As we might imagine, the inputs for computer science problems tend to be much larger than 10, so this problem becomes inordinately expensive to solve very quickly.
So how do heuristic algorithms help us solve this problem? If we are able to estimate the shortest path without actually traveling all 3,628,800 routes, we can save a lot of time. One example of a heuristic algorithm that often works "well enough" for TSP is a greedy algorithm. At each stop, select the next closest city. With this, we are able to come up with an approximate solution for our problem in only 10 steps.
This YouTube video gives a good introduction to TSP, and even offers more optimal solutions than a simple greedy algorithm (like Simulated Annealing):
A* Search
Another common heuristic algorithm is A* search. If we are searching a graph for the shortest path from node A to node N, A* search will represent all of the possible first-steps from A in a tree and use a heuristic to select the "best" first step. The "best" node is the one with the smallest cost that brings us closest to the end goal. Of course, we won't travel every path from the start node to the end, but we can use an estimation of the distance (like absolute distance) to evaluate which node is best.
This tool is really useful for visualizing path traversal with A* and other algorithms: PathFinding by qiao.
Heuristic algorithm applications
Heuristic algorithms are used in many NP-hard problems, but they are especially common in Artificial Intelligence and anti-virus software. In both of these cases, there is a large "problem space" to traverse (a decision tree, or a computer's filesystem), and heuristic algorithms often provide a "good enough" solution.
Sources:
Latest comments (0)