Search Algorithms in AI
A search algorithm is a kind of algorithm used in artificial intelligence that explores a set of potential solutions, also known as a search space, in order to discover the best or most optimum solution to a problem. To identify the optimum answer for a given set of constraints, a search algorithm sorts through a vast number of options.
Among the most significant applications of artificial intelligence are search algorithms. This article will cover every aspect of AI search algorithms.
Properties of Search Algorithms in AI
Some AI-related properties of the Search algorithm are:
- Admissibility
- Monotonicity
- Optimality
- Dominance
1. Admissibility
The ability of an algorithm to discover the best answer is referred to as acceptability. When an algorithm discovers an optimal solution, it is said to be admissible1. Therefore, the solution is optimal if we can somehow determine that A* is acceptable. This means that we can ensure that no path exists that is shorter than the distance produced by A*.
2. Monotonicity
This property determines if an algorithm is locally acceptable, or whether it consistently undervalues the difference in cost between any two states in the search space. Remember that g(n) = g*(n) is not a requirement for A*. Heuristic function h is monotone if and only if
1. h(ni) - h(nj) <= cost(ni,nj) for all states ni and nj, where nj is a descendant of ni.
2. h(Goal) = 0 is the heuristic evaluation of the goal state.
Put otherwise, a monotonic heuristic always underestimates the cost of converting from ni to nj for any two states in the search space. The heuristic is accepted everywhere.
3. Optimality
A* guarantees that, given a suitable heuristic function, the weighted graph's optimal (shortest) path between the start and destination nodes is found. Its optimality is a key benefit in numerous situations where determining the shortest path is necessary.
4. Dominance
Offers a cost function comparison. Cost functions are non-decreasing functions that are always increasing. The domain of the cost functions is usually the size of the data collection, which we most commonly refer to as "n".
