Heuristic
A heuristic is a method that, while it may not always get the best answer, it will always give a good answer within a reasonable amount of time. It can solve many difficult problems that are unsolvable in other ways.
Heuristics are approximations used to minimize the search process.
Heuristic search
Heuristic search is a kind of algorithm for solving problems that guide the search for potential solutions using heuristic functions. An approximation or estimation known as a heuristic function is a method that can be utilized to find faster and more effective solutions than conducting extensive searches through every potential combination.
Heuristic Search Techniques
In the most basic sense, a heuristic is a technique that involves customizing a solution to a problem based on earlier solutions to issues that are similar to the current one.
By using heuristics computationally, the concept of a heuristic can be applied to a variety of issues in science, mathematics, and optimization.
There are several methods used in the Heuristic search technique :
- Hill climbing
- Constraints satisfaction
- Simulated annealing
- Best first search (BFS)
Hill climbing
A local search technique known as "hill climbing" continuously moves toward a greater value in an attempt to locate the problem's optimal solution or the highest point of the mountain.
The hill climbing algorithm generates and tests variants while taking a greedy approach and not going back.
Hill climbing is used when the path to the goal does not matter. In this search method, the state space landscape is considered.
Hill Climbing Graph
Algorithm of Hill climbing
- Step 1: Analyze the starting state. Return success and stop if it is the desired state.
- Step 2: Encircle until a fix is discovered or no more operators are available to apply.
- Step 3: Choose an operator and apply it to the present state.
- Step 4: Verify the new state. If it's the desired state, go back to success and end the process. Otherwise, mark a new state as the current state if it is superior to the present state. If not, go back to step 2 if it's not better than the situation as it is.
- Step 5: Exit.
Constraints satisfaction
- One type of problem-solving strategy that works for many problems is constraint satisfaction.
- In many AI challenges, the objective is not stated clearly in the problem description.
- These categories include problems like crypto-arithmetic puzzles, design tasks requiring the creation of designs, and material where constraint satisfaction is relevant.
- Formally, a set of variables {V1, V2,,,,,,,, Vn} and a set of constraints {C1, C2,,,,,,, Cn} characterize a constraint satisfaction.
Thus, Constraint satisfaction is a two steps process:
- Firstly, Constraint satisfaction is discovered and propagated throughout the system.
- If there is no solution, and a search begins, a guess is made and added to the constraint.
Best First Search (BFS)
BFS is an algorithm that combines the depth-first and breadth-first search strategies. Using both algorithms' benefits is made possible by it. Its methods include search and the heuristic function. At each phase, we can select the most promising node with the aid of the best-first search.
One path is followed at a time in the Best First Search approach, but paths are swapped when a more promising path than the one being followed is discovered.
Algorithm Best First Search
- Step 1: Add the initial node to the list of OPEN list
- Step 2: Stop and return failure if the OPEN list is empty
- Step 3: Transfer the node n (which has the lowest value of h(n)) from the OPEN list to the CLOSED list
- Step 4: Compute the successors of node n and expand node n
- Step 5: Examine every node that comes after node n to determine if it is a goal node or not. Proceed to the next stage if none of the successor nodes are the goal node; else, return success and end the search
- Step 6: The algorithm looks for the evaluation function f(n) for each successor node, after which it determines if the node has ever been in the OPEN or CLOSED list
- Step 7: Return to step 2
