Heuristic Engines

A heuristic engine might be solved the way a human solves it.

For example, a Sudoku puzzle can be solved by mimicking a human by tracking possible values in each set and making a couple of logical inferences from the options. The selection rule means that if you select a value, then you remove that value from the options of all the other cells in the sets that contain that cell. Rule of 1 means if there’s only one option, select it. Rule of 2 means that if two cells have exactly the same 2 options, then no other cell can have that option. The game starts by using the Selection Rule for the values given to you in the puzzle. Then you search all cells for Rule of 1. Then you search all cells for Rule of 2. If any selection is made, then start the search of Rule of 1 for all cells again. This will solve a large number of puzzles that don’t get to a point where we must explore an option (guess).

But there’s also a nearly endless supply of metaheuristics or “heuristic types”. The most famous is likely the hill-climbing algorithm, where that algorithm continually adds to the best possible choice to a solution as it determines a solution – climbs the hill. This of course gets caught in local minimums or maximums where you have a good solution but perhaps not the best. The climber climbs the hill and sees another hill across the valley that they didn’t even consider. This is caused because sometimes an option that is not the best on its own merits putting everything else in the problem in a position to produce a better result.

Another fun algorithm is Dykstra’s Algorithm. This is an algorithm designed to help solve routing problems. In this problem, you are trying to find the shortest path between two points when the number of the intervening points would make it impossible to evaluate all possible combinations. It’s based on the idea that the shortest path between a point and the destination can be used as a fact when considering a point even further away from the destination. Consider driving from New York to LA, and we want the shortest path. If we find that from Salt Lake City to LA is shorter by going through Las Vegas than it is going through San Francisco, then I can use that when considering where to go from Denver. If we consider Denver to Salt Lake City as an option, then I know how far that is to LA because we already found the fastest way to LA from Salt Lake City. This way, as we build back the combinations to New York, we only keep the best routes. At some point, we ask if it’s faster to go from New York through Washington or Pittsburg. We already know ]the fastest routes from those cities, so we just pick the shortest combined distance and that is the shortest route.