Heuristics is a method of problem-solving where the goal is to come up with a workable solution in a feasible amount of time. Heuristic techniques strive for a rapid solution that stays within an appropriate accuracy range rather than a perfect solution.
When it seems impossible to tackle a specific problem with a step-by-step approach, heuristics are utilized in AI (artificial intelligence) and ML (machine learning). Heuristic functions in AI prioritize speed above accuracy; hence they are frequently paired with optimization techniques to provide better outcomes.
What is the Heuristic Function?
If there are no specific answers to a problem or the time required to find one is too great, a heuristic function is used to solve the problem. The aim is to find a quicker or more approximate answer, even if it is not ideal. Put another way, utilizing a heuristic means trading accuracy for speed.
A heuristic is a function that determines how near a state is to the desired state. Heuristics functions vary depending on the problem and must be tailored to match that particular challenge. The majority of AI problems revolve around a large amount of information, data, and constraints, and the task is to find a way to reach the goal state. The heuristics function in this situation informs us of the proximity to the desired condition. The distance formula is an excellent option if one needed a heuristic function to assess how close a location in a two-dimensional space was to the objective point.
Properties of a Heuristic Search Algorithm
Heuristic search algorithms have the following properties:
- Admissible Condition: If an algorithm produces an optimal result, it is considered admissible.
- Completeness: If an algorithm ends with a solution, it is considered complete.
- Dominance Property: If A1 and A2 are two heuristic algorithms and have h1 and h2 heuristic functions, respectively, then A1 Will dominate A2 if h1 is superior to h2 for all possible values of node n.
- Optimality Property: If an algorithm is thorough, allowable, and dominates the other algorithms, that'll be the optimal one and will unquestionably produce an optimal result.
Different Categories of Heuristic Search Techniques in AI
We can categorize the Heuristic Search techniques into two types:
Direct Heuristic Search Techniques
Direct heuristic search techniques may also be called blind control strategy, blind search, and uninformed search.
They utilize an arbitrary sequencing of operations and look for a solution throughout the entire state space. These include Depth First Search (DFS) and Breadth First Search (BFS).
BFS is a heuristic search method to diagram data or quickly scan intersection or tree structures. DFS is predicated on the likelihood of last in, first out. Similarly, the LIFO stack data structure is used to complete the process in recursion.
Weak Heuristic Techniques
Weak heuristic techniques are known as a Heuristic control strategy, informed search, and Heuristic search. These are successful when used effectively on the appropriate tasks and typically require domain-specific knowledge.
To explore and expand, users require additional information to compute preferences across child nodes. A heuristic function is connected to each node.
Let's first look at some of the strategies we frequently see before detailing specific ones. Here are a few examples.
- A* Search
- Best-first search
- Tabu search
- Bidirectional search
- Constant satisfaction problems
- Hill climbing
Examples of Heuristic Functions in AI
A variety of issues can be solved using a heuristic function in AI.
Let's talk about some of the more popular ones.
Traveling Salesman Problem
What is the quickest path between each city and its starting point, given a list of cities and the distances between each pair of them?
This problem could be brute-forced for a small number of cities. But as the number of cities grows, finding a solution becomes more challenging.
This issue is well-solved by the nearest-neighbor heuristic, which directs the computer to always choose the closest unexplored city as the next stop on the path. While NN only sometimes offers the optimum solution, it is frequently near enough that the variation is insignificant to respond to the salesman's problem. This approach decreases TSP's complexity from O(n!) to O (n^2).
Search Engine
People have been interested in SEO as long as there have been searching engines. Users want to quickly discover the information they need when utilizing a search engine. Search engines use heuristics to speed up the search process because such a staggering amount of data is available. A heuristic could initially attempt each alternative at each stage. Still, as the search progresses, it can quit at any point if the present possibility is inferior to the best solution already found. The search engine's accuracy and speed can be improved in this way.
Looking forward to a successful career in AI and Machine learning. Enrol in our Professional Certificate Program in AI and ML in collaboration with Purdue University now.
Conclusion
In conclusion, Heuristic functions in ai are critical to accelerating solution discovery. One benefit of using heuristic algorithms is the ability to generate a workable solution to the situation at hand quickly. Since the solution is quick enough, it can be imperfect; a close fit will do. With the Caltech Post Graduate Program In AI And Machine Learning, you can become an expert in the field. The program covers the most recent AI techniques and tools.
FAQs
1. What is a heuristic function to give an example?
A heuristic function estimates the approximate cost of solving a task. Determining the shortest driving distance to a particular location can be one example.
2. Where is the heuristic function used?
Informed Search uses a heuristic function to identify the most feasible path. It estimates how far away the agent is from the goal using the agent's current condition as input.
3. What are the types of heuristic functions?
Types of heuristic functions in ai are:
Breadth-First Search (BFS) and Depth First Search (DFS), Bidirectional Search, A* search Simulated Annealing, Hill Climbing, Best First search, and Beam search.
4. What is the heuristic function formula?
f(n)= g(n) + h(n), where
f(n)= estimated cost of the cheapest solution
g(n)= cost to reach node n from the start state
h(n)= cost to reach from node n to goal node
5. What are the four types of heuristics?
The four types of heuristics are:
- Availability heuristic
- Representativeness heuristic
- Anchoring and adjustment heuristic
- Quick and easy
Although they all lessen the mental effort required to make a decision, each heuristic is applied differently.
6. What are the three types of heuristics?
The three heuristics that attracted the most focus are representativeness, anchoring and adjustment, and availability.
