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.