What is a Heuristic Search?
A Heuristic is a technique to solve a problem faster than classic methods, or to find an approximate solution when classic methods cannot. This is a kind of a shortcut as we often trade one of optimality, completeness, accuracy, or precision for speed. A Heuristic (or a heuristic function) takes a look at search algorithms. At each branching step, it evaluates the available information and makes a decision on which branch to follow. It does so by ranking alternatives. The Heuristic is any device that is often effective but will not guarantee work in every case.

Comments

Posting comment...

Premium member

Presentation Transcript

slide 1:

What is Heuristic Search
- Techniques Hill
Climibing in AI

slide 2:

Heuristic Search in Artificial Intelligence – Python
First l e t’ s revise the Artificial Intelligence Tutorial
What is a Heuristic Search
A Heuristic is a technique to solve a problem faster than classic methods or to find an
approximate solution when classic methods cannot. This is a kind of a shortcut as we
often trade one of optimality completeness accuracy or precision for speed. A
Heuristic or a heuristic function takes a look at search algorithms. At each branching
step it evaluates the available information and makes a decision on which branch to
follow. It does so by ranking alternatives. The Heuristic is any device that is often
effective but will not guarantee work in every case.
You must take a look at NLP Tutorial
So why do we need heuristics One reason is to produce in a reasonable amount of
time a solution that is good enough for the problem in question. It d o es n ’ t have to be
the best- an approximate solution will do since this is fast enough. Most problems are
exponential. Heuristic Search let us reduce this to a rather polynomial number. We
use this in AI because we can put it to use in situations where we ca n ’ t find known
algorithms.
We can say Heuristic Techniques are weak methods because they are vulnerable to
combinatorial explosion.

slide 3:

Heuristic Search Techniques in
Artificial Intelligence
Briefly we can taxonomize such techniques of Heuristic into two categories:
Heuristic Search Techniques in Artificial Intelligence
a. Direct Heuristic Search Techniques in AI
Other names for these are Blind Search Uninformed Search and Blind Control
Strategy. These a r en ’ t always possible since they demand much time or memory.
They search the entire state space for a solution and use an arbitrary ordering of
operations. Examples of these are Breadth First Search BFS and Depth First Search
DFS.
Do you know about NLTK Python
b. Weak Heuristic Search Techniques in AI
Other names for these are Informed Search Heuristic Search and Heuristic Control
Strategy. These are effective if applied correctly to the right types of tasks and usually
demand domain-specific information. We need this extra information to compute
preference among child nodes to explore and expand. Each node has a heuristic

slide 4:

function associated with it. Examples are Best First Search BFS and A.
Before we move on to describe certain techniques l et ’ s first take a look at the ones we
generally observe. Below we name a few.
Best-First Search
A Search
Bidirectional Search
Tabu Search
Beam Search
Simulated Annealing
Hill Climbing
Constraint Satisfaction Problems
Hill Climbing in Artifical Intelligence
First l et ’ s talk about Hill Climbing in Artifical Intelligence. This is a heuristic for
optimizing problems mathematically. We need to choose values from the input to
maximize or minimize a real function. It is okay if the solution i s n ’ t the global optimal
maximum.
Heuristic Search Techniques – Hill Climbing
L e t’ s discuss Python Speech Recognition
One such example of Hill Climbing will be the widely discussed Travelling Salesman
Problem- one where we must minimize the distance he travels.

slide 5:

a. Features of Hill Climbing in AI
Let ’ s discuss some of the features of this algorithm Hill Climbing:
It is a variant of the generate-and-test algorithm
It makes use of the greedy approach
This means it keeps generating possible solutions until it finds the expected solution
and moves only in the direction which optimizes the cost function for it.
b. Types of Hill Climbing in AI
Heuristic Search – Types of Hill Climbing in Artifical Intelligence
Simple Hill Climbing- This examines one neighboring node at a time and selects
the first one that optimizes the current cost to be the next node.
Steepest Ascent Hill Climbing- This examines all neighboring nodes and selects
the one closest to the solution state.
Stochastic Hill Climbing- This selects a neighboring node at random and decides
whether to move to it or examine another.
L et’ s revise Python Unit testing
Let ’ s take a look at the algorithm for simple hill climbing.
1. Evaluate initial state- if goal state stop and return success. Else make initial state
current.

slide 6:

2. Loop until the solution reached or until no new operators left to apply to current
state:
a. Select new operator to apply to the current producing new state.
b. Evaluate new state:
If a goal state stop and return success.
If better than the current state make it current state proceed.
Even if not better than the current state continue until the solution reached.
3. Exit.
c. Problems with Hill Climbing in AI
We usually run into one of three issues-
Local Maximum- All neighboring states have values worse than the current. The
greedy approach means we w o n ’ t be moving to a worse state. This terminates the
process even though there may have been a better solution. As a workaround we
use backtracking.
Plateau- All neighbors to it have the same value. This makes it impossible to
choose a direction. To avoid this we randomly make a big jump.
Ridge- At a ridge movement in all possible directions is downward. This makes
it look like a peak and terminates the process. To avoid this we may use two or
more rules before testing.
Do you know about Python Assert Statements
Constraint Satisfaction Problems
CSP
A constraint is nothing but a limitation or a restriction. Working with AI we may
need to satisfy some constraints to solve problems. Let ’ s try solving a problem this
way shall we
Let ’ s talk of a magic square. This is a sequence of numbers- usually integers-
arranged in a square grid. The numbers in each row each column and each diagonal
all add up to a constant which we call the Magic Constant. Let ’ s implement this with
Python.
1. def magic_squarematrix:
2. sizelenmatrix0
3. sum_list
4. for col in rangesize: Vertical sum
5. sum_list.appendsumrowcol for row in matrix
6. sum_list.extendsumlines for lines in matrixHorizontal sum

slide 7:

7. result10
8. for i in range0size:
9. result1+matrixii
10. sum_list.appendresult1
11. result20
12. for i in rangesize-1-1-1:
13. result2+matrixii
14. sum_list.appendresult2
15. if lensetsum_list1:
16. return False
17. return True
Now l et ’ s run this code.
1. magic_square123456789
False
This is not a magic square. The numbers in the rows/columns/diagonals do not add up
to the same value. Let ’ s try another list of lists.
Have a look at AI Neural Networks
1. magic_square276951438
True

slide 8:

Heuristic Search – Magic
Since the values add up to the constant 15 in all directions surely this is a magic
square
Simulated Annealing Heuristic Search
In metallurgy when we slow-cool metals to pull them down to a state of low energy
gives them exemplary amounts of strength. We call this annealing. While high
temperatures observe much random movement low temperatures notice little
randomness.
In AI we take a cue from this to produce something called simulated annealing. This
is a way of optimization where we begin with a random search at a high temperature
and reduce the temperature slowly. Eventually as the temperature approaches zero
the search becomes pure greedy descent. At each step this processes randomly selects
a variable and a value. It accepts the assignment only when it is an improvement or

slide 9:

d o esn ’ t lead to more conflict. If not it checks if the temperature is much worse than
the current assignment to accept the assignment with some probability.
Do you know about Python ternary Operators
An annealing schedule defines how the temperature drops as the search progress. A
very common schedule is geometric cooling. If we begin with a temperature of 10 and
multiply by 0.97 after every step then after 100 steps w e’ r e left with a temperature of
0.48.
Best-First Search BFS Heuristic
Search
Often dubbed BFS Best First Search is an informed search that uses an evaluation
function to decide which adjacent is the most promising before it can continue to
explore. Breadth- and Depth- First Searches blindly explore paths without keeping a
cost function in mind. Things a r e n ’ t the same with BFS though. Here we use a
priority queue to store node costs. Let ’ s understand BFS Heuristic Search through
pseudocode.
1. Define list OPEN with single node s – the start node.
2. IF list is empty return failure.
3. Remove node n node with best score from list move it to list CLOSED.
4. Expand node n.
5. IF any successor to n is the goal node return success and trace path from goal
node to s to return the solution.
6. FOR each successor node:
Apply evaluation function f.
IF the node i sn ’ t in either list add it to list OPEN.
7. Loop to step 2.
L e t’ s learn about Python Slice
So this was all in Heuristic Search Techniques in AI. Hope you like our
explanation.
Conclusion – Heuristic Search
Techniques

slide 10:

Hence in this Python AI tutorial we discussed the Heuristic Search in AI. While we
named a few techniques that fall under that we also discussed in brief those like
BFS Hill Climbing Simulated Annealing and CSP. We also implemented CSP in
Python. Still if you have any query in Heuristic Search Techniques feel free to ask in
the comment tab.

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.