Digital Themes

Heuristic Search Techniques

A heuristic search technique is a type of search performed by artificial intelligence (AI) that looks to find a good solution, not necessarily a perfect one, out of the available options. This technique makes decisions by ranking every available choice at each branch of a search and then chooses the best option of those presented. Rather than focusing on finding an optimal solution like other search methods, heuristic searching is designed to be quick, and therefore finds the most acceptable option within a reasonable time limit or within the allocated memory space. There are several different types of heuristic search algorithms that can be utilized depending on the task.

Hill Climbing in AI seeks to find the best available solution by continuing to generate solutions until it finds the goal state.  At each step in the process, the algorithm will generate solutions (nodes) and compare the node to the goal. If it is the expected goal state, it completes the process. If it is not, it will generate new nodes and repeat until the goal state is found or until it reaches the local maximum, or the state in which all other options are worse than the current one. Hill climbing search strategies are often utilized for mathematical optimizations, such as in the travelling salesman problem, which tries to find the shortest possible routes between sales stops.

Simulated Annealing is an iterative algorithm with a starting solution and an optimization problem. Simulated Annealing uses heuristic functions to compare the neighboring states of data and decide between staying in the same state or moving to a new one. Simulated annealing will move to states closer to the optimum solution until it reaches a state that has been noted as “good enough” for the application, or until its execution time has been reached. Simulated annealing may be used to determine costs and increase revenue.

When searching through tree data structures, there are two types of heuristic searches available. The breadth-first search will start at the determined “root” node of the tree, and then explore all neighboring nodes at the same depth before moving on to the next depth level. Depth-first search, on the other hand, starts at the root and follows an entire “branch” until it reaches the final depth before backtracking and moving to a neighboring node. Both search types can be used to conduct topological sorting or finding connections between components.

Heuristic searches can be helpful for businesses and organizations because they:

  • Optimize costs: Heuristic search methods are often utilized due to the lower cost of the analysis. Rather than being allowed to run indefinitely, heuristic searches can be programmed to search for an allotted amount of time or computing resources, and then to terminate and communicate the best solution that was found.

  • Speed up analysis: Because heuristic searches are not necessarily looking for the perfect solution, they can be much faster than other search methods. Rather than running and running until an optimal solution is found, heuristic searches can terminate after finding a good solution that matches the inputted requirements.
Related content