Heuristic Search Technique

​

RAJKUMAR D

ASST PROG(S.G)

DEPARTMENT OF COMPUTER APPLICATIONS

SRMIST, RAMAPURAM

Heuristic Search Technique - Introduction

• Heuristic search is defined as a procedure of search that endeavors to upgrade an issue by iteratively improving the arrangement dependent on a given heuristic capacity or a cost measure.
• This technique doesn’t generally ensure to locate an ideal or the best arrangement, however, it may rather locate a decent or worthy arrangement inside a sensible measure of time and memory space. This is a sort of an alternate route as we regularly exchange one of optimality, culmination, exactness, or accuracy for speed.
• A Heuristic (or a heuristic capacity) investigates search calculations. At each stretching step, it assesses the accessible data and settles on a choice on which branch to follow.

​

​

Heuristic Search Technique - Introduction

Hill Climbing

• Hill Climbing is a kind of heuristic quest for logical progression issues in the field of Artificial Intelligence. Given a set of data sources and a better than average heuristic limit, it endeavors to find an adequate enough response for the issue. This course of action may not be the overall perfect most noteworthy.

Features of Hill Climbing

• Produce and Test variation: Hill Climbing is the variation of the Generate and Test strategy. The Generate and Test technique produce input which assists with choosing which bearing to move in the inquiry space.
• Use of Greedy Approach: Hill-climbing calculation search moves toward the path which improves the expense.
• No backtracking: It doesn’t backtrack the pursuit space, as it doesn’t recall the past states.

​

Types of Hill Climbing

1. Simple Hill Climbing

• Simple Hill climbing is the least difficult approach to execute a slope climbing calculation. It just assesses the neighbor hub state at once and chooses the first which enhances current expense and sets it as a present state.
• It just checks it’s one replacement state, and on the off chance that it discovers superior to the present state, at that point move else be in a similar state.

Its features include:

• Less tedious
• Less ideal arrangement that isn’t ensured

�

​

Types of Hill Climbing

2. Steepest Ascent Hill Climbing

• The steepest-Ascent calculation is a variety of basic slope climbing calculations. It first examines all the neighboring nodes then selects the node closest to the answer state as of next node.
• This calculation looks at all the neighboring hubs of the present state and chooses one neighbor hub which is nearest to the objective state.
• This calculation expends additional time as it looks for different neighbors

​

Types of Hill Climbing

3. Stochastic Hill Climbing

• Stochastic slope climbing doesn’t analyze for all its neighbors before moving. It makes use of randomness as a part of the search process. It is also an area search algorithm, meaning that it modifies one solution and searches the relatively local area of the search space until the local optima is found .
• This suggests that it’s appropriate on unimodal optimization problems or to be used after the appliance of a worldwide optimization algorithm.
• This calculation chooses one neighbor hub aimlessly and concludes whether to pick it as a present state or analyze another state.

​

Types of Hill Climbing�

4. Simulated Annealing

• Simulated Annealing is an algorithm that never makes a move towards lower esteem destined to be incomplete that it can stall out on a nearby extreme.
• Also, on the off chance that calculation applies an irregular stroll, by moving a replacement, at that point, it might finish yet not proficient.
• In terms of metallurgy, Annealing is a procedure of solidifying a metal or glass to a high temperature at that point cooling bit by bit, so this permits the metal to arrive at a low-vitality crystalline state.
• A similar procedure is utilized in reenacted toughening in which the calculation picks an arbitrary move, rather than picking the best move.

​

​

Problems associated with Hill Climbing

• Local Maximum: All the surrounding states have values lower than the current. With the implementation of the Greedy Approach, implies we won’t be moving to a lower state. This ends the procedure despite the fact that there may have been a superior arrangement. As a workaround, we use backtracking.
• Plateau: All neighbors to it have a similar worth. This makes it difficult to pick a course. To dodge this, we haphazardly make a major jump.
• Ridge: At an edge, development in every conceivable course is descending. This makes it resemble a pinnacle and ends the procedure. To stay away from this, we may utilize at least two guidelines before testing.

​

Best First Search (BFS)�

• Best first search uses the concept of a priority queue and heuristic search. It is a search algorithm that works on a specific rule.
• The aim is to reach the goal from the initial state via the shortest path.
• BFS is a Heuristic method, where search is carried out by using additional information to determine the next step towards finding the solution. Best First Search is an example of such algorithms.
• Informed search methods are more efficient, low in cost and high in performance as compared to the uninformed search methods. 

What is Best First Search?�

• If we consider searching as a form of traversal in a graph, an uninformed search algorithm would blindly traverse to the next node in a given manner without considering the cost associated with that step.
• An informed search, like Best first search, on the other hand would use an evaluation function to decide which among the various available nodes is the most promising (or ‘BEST’) before traversing to that node. 
• The Best first search uses the concept of a Priority queue and heuristic search. To search the graph space, the BFS method uses two lists for tracking the traversal. An ‘Open’ list which keeps track of the current ‘immediate’ nodes available for traversal and ‘CLOSED’ list that keeps track of the nodes already traversed. 

Best First Search Algorithm�

• Create 2 empty lists: OPEN and CLOSED
• Start from the initial node (say N) and put it in the ‘ordered’ OPEN list
• Repeat the next steps until GOAL node is reached
• If OPEN list is empty, then EXIT the loop returning ‘False’
• Select the first/top node (say N) in the OPEN list and move it to the CLOSED list. Also capture the information of the parent node
• If N is a GOAL node, then move the node to the Closed list and exit the loop returning ‘True’. The solution can be found by backtracking the path
• If N is not the GOAL node, expand node N to generate the ‘immediate’ next nodes linked to node N and add all those to the OPEN list
• Reorder the nodes in the OPEN list in ascending order according to an evaluation function f(n)

​

Constraint Satisfaction Problem (CSP)

• A constraint satisfaction problem (CSP) is a problem that requires its solution within some limitations or conditions also known as constraints. It consists of the following:
• A finite set of variables which stores the solution (V = {V1, V2, V3,....., Vn})
• A set of discrete values known as domain from which the solution is picked (D = {D1, D2, D3,.....,Dn})
• A finite set of constraints (C = {C1, C2, C3,......, Cn})

​

​

Constraint Satisfaction Problem (CSP) - Examples

• Graph Coloring: The problem where the constraint is that no adjacent sides can have the same color.

​

​

​

​

Constraint Satisfaction Problem (CSP) - Examples

• Sudoku Playing: The gameplay where the constraint is that no number from 0-9 can be repeated in the same row or column.

​

​

​

​

Constraint Satisfaction Problem (CSP) - Examples

• Crossword: In crossword problem, the constraint is that there should be the correct formation of the words, and it should be meaningful.

​

​

​

​