NOTES

ON
ARTIFICAL INTELLIGENCE & MACHINE
LEARNING

B.Tech 6th sem IT

By
Shabana Pathan

Department of Information Technology

St. Vincent Pallotti College of Engineering &Technology
 UNIT II

Heuristic Search Techniques:

Requirements of search algorithms, Heuristic search, Generate-And-Test, Hill climbing,
best first search, , Breadth First Search, Depth First Search ,A* search algorithm, mini-max
algorithm, Alpha-Beta pruning, Constraint satisfaction.

Introduction

Heuristic
• A heuristic is a method that improves the efficiency of the search process.
• These are like tour guides

Heuristic Search Techniques

Search Algorithms

• AI is search.
• Many traditional search algorithms are used in AI applications.
• For complex problems, the traditional algorithms are unable to find the solutions within some
practical time and space limits.
• Consequently, many special techniques are developed, using heuristic functions.
• The algorithms that use heuristic functions are called heuristic algorithms.
• Heuristic algorithms are not really intelligent; they appear to be intelligent because they achieve
better performance.
• Heuristic algorithms are more efficient because they take advantage of feedback from the data to
direct the search path.
• A good heuristic will make an informed search dramatically outperform any uninformed search: for
example, the Traveling Salesman Problem (TSP), where the goal is to find is a good solution
instead of finding the best solution.
• In such problems, the search proceeds using current information about the problem to predict which
path is closer to the goal and follow it, although it does not always guarantee to find the best
possible solution. Such techniques help in finding a solution within reasonable time and space
(memory).
• Some prominent intelligent search algorithms are stated below:

1.Generate and Test Search

2. Best-first Search
3. Greedy Search
4. A* Search
5. Constraint Search
6. Means-ends analysis
• There are some more algorithms. They are either improvements or combinations of these.

• Hierarchical Representation of Search Algorithms: A Hierarchical representation of most search

algorithms is illustrated below. The representation begins with two types of search:

• Uninformed Search: Also called blind, exhaustive or brute-force search, it uses no information about
the problem to guide the search and therefore may not be very efficient.
• Informed Search: Also called heuristic or intelligent search, this uses information about the problem
to guide the search — usually guesses the distance to a goal state and is therefore efficient, but the
search may not be always possible.

Requirement of Search Algorithms / Techniques

• The first requirement is that it causes motion, in a game playing program, it moves on the board
and in the water jug problem, filling water is used to fill jugs. It means the control strategies without
the motion will never lead to the solution.
• The second requirement is that it is systematic, that is, it corresponds to the need for global motion
as well as for local motion. This is a clear condition that neither would it be rational to fill a jug and
empty it repeatedly, nor it would be worthwhile to move a piece round and round on the board in a
cyclic way in a game.
• We shall initially consider two systematic approaches for searching. Searches can be classified by the
order in which operators are tried: depth-first, breadth-first, bounded depth-first.

Breadth First Search

• It searches breadthwise in a tree or graph.
• It starts from the root node, explores the neighboring nodes first and moves towards the
next level neighbors.
• It uses queue FIFO (first-in, first-out) data structure.
• This method provides shortest path to the solution.
• Complete
• Optimal (i.e., admissible) if all operators have the same cost. Otherwise, not optimal
but finds solution with shortest path length.
• Disadvantage: It will take a long time to find solutions with a large number of steps
because It has to look at all shorter length possibilities first.
Depth First Search
• It starts from the root node and follows each path to its greatest depth node before
moving to the next path.
• That is, it traverses along the increasing depth and upon reaching the end, it backtracks
to the node from which it was started and then do the same with the sibling node.
• It uses stack LIFO (Last-in, first-out) data structure.
• May not terminate without a “depth bound,” i.e., cutting off search below a fixed depth D
( “depth-limited search”)
• Not complete (with or without cycle detection, and with or without a cutoff depth)
• Can find long solutions quickly if lucky (and short solutions slowly if unlucky!)
Differences between BFS and DFS

The following are the differences between the BFS and DFS:
 BFS DFS

Full form BFS stands for Breadth First DFS stands for Depth First Search.
Search.

Technique It a vertex-based technique to It is an edge-based technique because

find the shortest path in a the vertices along the edge are
graph. explored first from the starting to the
end node.

Definition BFS is a traversal technique in DFS is also a traversal technique in

which all the nodes of the same which traversal is started from the
level are explored first, and then root node and explore the nodes as
we move to the next level. far as possible until we reach the node
that has no unvisited adjacent nodes.

Data Queue data structure is used for Stack data structure is used for the
Structure the BFS traversal. BFS traversal.

Backtracking BFS does not use the DFS uses backtracking to traverse all
backtracking concept. the unvisited nodes.

Number of BFS finds the shortest path In DFS, a greater number of edges are
edges having a minimum number of required to traverse from the source
edges to traverse from the vertex to the destination vertex.
source to the destination vertex.

Optimality BFS traversal is optimal for DFS traversal is optimal for those
those vertices which are to be graphs in which solutions are away
searched closer to the source from the source vertex.
vertex.

Speed BFS is slower than DFS. DFS is faster than BFS.

Suitability for It is not suitable for the decision It is suitable for the decision tree.
decision tree tree because it requires Based on the decision, it explores all
exploring all the neighboring the paths. When the goal is found, it
nodes first. stops its traversal.

Memory It is not memory efficient as it It is memory efficient as it requires

efficient requires more memory than less memory than BFS.
DFS.
Heuristic Search

• To find a solution in proper time rather than a complete solution in unlimited time we
use heuristics.
• ‘A heuristic function is a function that maps from problem state descriptions to
measures of desirability, usually represented as numbers’.
• Heuristic search methods use knowledge about the problem domain and choose
promising operators first. These heuristic search methods use heuristic functions to
evaluate the next state towards the goal state.
• For finding a solution, by using the heuristic technique, one should carry out the
following steps:

1. Add domain—specific information to select what is the best path to continue searching
along.

2. Define a heuristic function h(n) that estimates the ‘goodness’ of a node n. Specifically,
h(n) = estimated cost (or distance) of minimal cost path from n to a goal state.

3. The term, heuristic means ‘serving to aid discovery’ and is an estimate, based on domain
specific information that is computable from the current state description of how close
we are to a goal.

• Finding a route from one city to another city is an example of a search problem in
which different search orders and the use of heuristic knowledge are easily understood.

1. State: The current city in which the traveler is located.

2. Operators: Roads linking the current city to other cities.

3. Cost Metric: The cost of taking a given road between cities.

4. Heuristic information: The search could be guided by the direction of the goal city
from the current city, or we could use airline distance as an estimate of the distance to
the goal.

• For complex problems, the traditional algorithms, presented above, are unable to find
the solution within some practical time and space limits. Consequently, many special
techniques are developed, using heuristic functions.

• Blind search is not always possible, because it requires too much time or Space
(memory). Heuristics are rules of thumb; they do not guarantee a solution to a problem.

• Heuristic Search is a weak technique but can be effective if applied correctly; it

requires domain specific information.

Characteristics of heuristic search

• Heuristics are knowledge about domain, which help search and reasoning in its
domain.
• Heuristic search incorporates domain knowledge to improve efficiency over blind
search.
• Heuristic is a function that, when applied to a state, returns value as estimated merit of
state, with respect to goal.
✓ Heuristics might (for reasons) underestimate or overestimate the merit of a
state with respect to goal.
✓ Heuristics that underestimate are desirable and called admissible.
• Heuristic evaluation function estimates likelihood of given state leading to goal state.
• Heuristic search function estimates cost from current state to goal, presuming function is
efficient.

Properties of 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.

Heuristic search compared with other search

• The Heuristic search is compared with Brute force or Blind search techniques below:

Brute force / Blind search Heuristic search

Can only search what it has knowledge Estimates ‘distance’ to goal state through
about already explored nodes
No knowledge about how far a node
Guides search process toward the goal
from the goal state
Prefers states (nodes) that lead close to and
not away from goal State

Generate and Test Strategy

• Generate-And-Test Algorithm
• Generate-and-test search algorithm is a very simple algorithm that guarantees to find a
solution if done systematically and there exists a solution.
 • Solutions can also be generated randomly but solution is not guaranteed. This approach
is what is known as British Museum algorithm: finding an object in the British Museum
by wandering randomly.

Algorithm: Generate-And-Test

1.Generate a possible solution.

2.Test to see if this is the expected solution.

3.If the solution has been found quit else go to step 1.

Hill Climbing Algorithm

o Hill climbing algorithm is a local search algorithm which continuously moves in the
direction of increasing elevation/value to find the peak of the mountain or best
solution to the problem. It terminates when it reaches a peak value where no
neighbor has a higher value.
o Hill climbing algorithm is a technique which is used for optimizing the
mathematical problems. One of the widely discussed examples of Hill climbing
algorithm is Traveling-salesman Problem in which we need to minimize the
distance traveled by the salesman.
o It is also called greedy local search as it only looks to its good immediate neighbor
state and not beyond that.
o A node of hill climbing algorithm has two components which are state and value.
o Hill Climbing is mostly used when a good heuristic is available.
o In this algorithm, we don't need to maintain and handle the search tree or graph as it
only keeps a single current state.
 Features of Hill Climbing
Generate and Test variant:

o It is a variant of generate and test algorithm.

o The generate and test algorithm is as follows:
A. Generate possible solutions.
B. Test to see if this is the expected solution.
C. If the solution has been found
quit
else
go to step 1.
o Hill climbing takes the feedback from the test procedure. Then this feedback is
utilized by the generator in deciding the next move in search space.

Greedy approach:
Hill-climbing algorithm search moves in the direction which optimizes the cost.
At any point in state space, the search moves in that direction only which optimizes the
cost of function with the hope of finding the most optimum solution at the end.

No backtracking: It does not backtrack the search space, as it does not remember the
previous states.
• Feedback mechanism: A variant of the generate-and-test algorithm. It helps to decide
the next action. Whether to move up or down the hill.
• Incremental Change: Through incremental changes, the algorithm improves the
current state.

State-space Diagram
• The state-space landscape is a graphical representation of the hill climbing
algorithm which is showing a graph between various states of algorithm and
objective function/Cost.
1. The X-axis denotes the state space i.e. states or configuration our algorithm may reach.
2. The Y-axis denotes the values of objective function corresponding to a particular state.
• The best solution will be that state space where objective function has maximum
value or global maxima.

Different regions in the state space landscape:

Local Maximum: Local maximum is a state which is better than its neighbor states, but
there is also another state which is higher than it.
Global Maximum: Global maximum is the best possible state of state space landscape. It
has the highest value of objective function
Current state: It is a state in a landscape diagram where an agent is currently present.
Flat local maximum: It is a flat space in the landscape where all the neighbor states of
current states have the same value.
Shoulder: It is a plateau region which has an uphill edge.

Types of Hill Climbing Algorithm

Simple hill Climbing
Steepest-Ascent hill-climbing

Simple hill Climbing

 • Simple hill climbing only evaluates the neighbor node state at a time and selects the
first one which optimizes current cost and set it as a current state.
• It only checks it's one successor state, and if it finds better than the current state,
then move else be in the same state.

Simple Hill Climbing: Algorithm

• Step 1 : Evaluate the initial state. If it is a goal state then stop and return success.
Otherwise, make initial state as current state.
• Step 2 : Loop until the solution state is found or there are no new operators present which
can be applied to the current state.
a) Select an operator that has not been yet applied to the current state and apply it to
produce a new state.
b) Perform these to evaluate new state
i. If the current state is a goal state, then stop and return success.
ii. If it is better than the current state, then make it current state and proceed further.
iii. If it is not better than the current state, then continue in the loop until a solution is
found.
• Step 3 : Exit.
Steepest-ascent Hill Climbing
• This algorithm examines all the neighboring nodes of the current state and selects one
neighbor node which is closest to the goal state.
• This algorithm consumes more time as it searches for multiple neighbors.

Steepest-ascent Hill Climbing: Algorithm

• Step 1 : Evaluate the initial state. If it is goal state then exit else make the current state as
initial state
• Step 2 : Repeat these steps until a solution is found or current state does not change
A. Let ‘target’ be a state such that any successor of the current state will be better than it;
B. For each operator that applies to the current state
apply the new operator and create a new state
evaluate the new state
if this state is goal state then quit else compare with ‘target’
if this state is better than ‘target’, set this state as ‘target’
if target is better than current state set current state to Target
• Step 3 : Exit

Issues in Hill Climbing

• Hill climbing cannot reach the optimal/best state(global maximum) if it enters any of the
following regions :
• Local maximum :
– At a local maximum all neighboring states have a values which is worse than the current
state.
– Since hill-climbing uses a greedy approach, it will not move to the worse state and
terminate itself.
– The process will end even though a better solution may exist.
Solution :
– Utilize backtracking technique. Maintain a list of visited states.
– If the search reaches an undesirable state, it can backtrack to the previous
configuration and explore a new path.
Plateau:
– A plateau is the flat area of the search space in which all the
neighbor states of the current state contains the same value, because of this algorithm does
not find any best direction to move.
– A hill-climbing search might be lost in the plateau area.
• Solution:
– The solution for the plateau is to take big steps or very little steps while searching, to
solve the problem.
– Randomly select a state which is far away from the current state so it is possible that the
algorithm could find non-plateau region.
Ridges:
– A ridge is a special form of the local maximum.
– It has an area which is higher than its surrounding areas, but itself has a slope, and cannot
be reached in a single move.
– Any point on a ridge can look like peak because movement in all possible directions is
downward. Hence the algorithm stops when it reaches this state.
• Solution:
– With the use of bidirectional search, or by moving in different directions, we can improve
this problem.

Heuristics function:
Heuristic is a function which is used in Informed Search, and it finds the most promising
path. It takes the current state of the agent as its input and produces the estimation of how
close agent is from the goal. The heuristic method, however, might not always give the best
solution, but it guaranteed to find a good solution in reasonable time. Heuristic function
estimates how close a state is to the goal. It is
represented by h(n), and it calculates the cost of an optimal path between the pair of states.
The value of the heuristic function is always positive.
h(n) <= h*(n)
Here,
• h(n) is heuristic cost, and
 • h*(n) is the estimated cost.
• Hence, heuristic cost should be less than or equal to the estimated cost.

Best First Search

• The best first search belongs to a branch of search algorithms known as heuristic
search algorithms.
• The basic idea of heuristic search is that, rather than trying all possible search paths
at each step, we try to find which paths seem to be getting us nearer to our goal state.
Of course, we can’t be sure that we are really near to our goal state. It could be that
we are really near to our goal state. It could be that we have to take some really
complicated and circuitous sequence of steps to get there. But we might be able to
make a good guess. Heuristics are used to help us make that guess.
• To use any heuristic search we need an evaluation function that scores a node in the
search tree according to how close to the goal or target node it seems to be. It will
just be an estimate but it should still be useful. But the estimate should always be on
the lower side to find the optimal or the lowest cost path.
• For example, to find the optimal path/route between Delhi and Jaipur, an estimate
could be straight arial distance between the two cities.
• There are a whole batch of heuristic search algorithms eg. Hill Climbing, best first
search, A* ,AO* etc. But here we will be focussing on best first search.

Greedy best-first search algorithm always selects the path which appears best at that
moment. It is the combination of depth-first search and breadth-first search algorithms. It
uses the heuristic function and search. Best-first search allows us to take the advantages of
both algorithms. With the help of best-first search, at each step, we can choose the most
promising node. In the best first search algorithm, we expand the node which is closest to
the goal node and the closest cost is estimated by heuristic function, i.e.
f(n)= g(n).
Were, h(n)= estimated cost from node n to the goal.
The greedy best first algorithm is implemented by the priority queue.

Best first search algorithm:

Step 1: Place the starting node into the OPEN list.
Step 2: If the OPEN list is empty, Stop and return failure.
Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n), and
places it in the CLOSED list.
Step 4: Expand the node n, and generate the successors of node n.
Step 5: Check each successor of node n, and find whether any node is a goal node or not. If
any successor node is goal node, then return success and terminate the search, else proceed
to Step 6.
Step 6: For each successor node, algorithm checks for evaluation function f(n), and then
check if the node has been in either OPEN or CLOSED list. If the node has not been in
both list, then add it to the OPEN list.
Step 7: Return to Step 2.

Advantages:
Best first search can switch between BFS and DFS by gaining the advantages of both the
algorithms.
This algorithm is more efficient than BFS and DFS algorithms.

Disadvantages:
It can behave as an unguided depth-first search in the worst case scenario.
It can get stuck in a loop as DFS.
This algorithm is not optimal.

Example: Consider the below search problem, and we will traverse it using greedy
best-first search. At each iteration, each node is expanded using evaluation function
f(n)=h(n) , which is given in the below table.

Expand the nodes of S and put in the CLOSED list

Initialization: Open [A, B], Closed [S]
Iteration 1: Open [A], Closed [S, B]
Iteration 2: Open [E, F, A], Closed [S, B]
: Open [E, A], Closed [S, B, F]
Iteration 3: Open [I, G, E, A], Closed [S, B, F]
 : Open [I, E, A], Closed [S, B, F, G]
Hence the final solution path will be: S----> B----->F----> G
Time Complexity: The worst case time complexity of Greedy best first search is O(bm).
Space Complexity: The worst case space complexity of Greedy best first search is O(bm).
Where, m is the maximum depth of the search space.
Complete: Greedy best-first search is also incomplete, even if the given state space is
finite.
Optimal: Greedy best first search algorithm is not optimal.

A* Search Algorithm
A* search is the most commonly known form of best-first search. It uses heuristic function
h(n), and cost to reach the node n from the start state g(n). It has combined features of UCS
and greedy best-first search, by which it solve the problem efficiently. A* search algorithm
finds the shortest path through the search space using the heuristic function. This search
algorithm expands less search tree and provides optimal result faster. A* algorithm is
similar to UCS except that it uses g(n)+h(n) instead of g(n).
In A* search algorithm, we use search heuristic as well as the cost to reach the node. Hence
we can combine both costs as following, and this sum is called as a fitness number.

At each point in the search space, only those node is expanded which have the lowest
value of f(n), and the algorithm terminates when the goal node is found.

Algorithm of A* search:
Step1: Place the starting node in the OPEN list.
Step 2: Check if the OPEN list is empty or not, if the list is empty then return failure and
stops.
Step 3: Select the node from the OPEN list which has the smallest value of evaluation
function (g+h), if node n is goal node then return success and stop, otherwise
Step 4: Expand node n and generate all of its successors, and put n into the closed list. For
each successor n', check whether n' is already in the OPEN or CLOSED list, if not then
compute evaluation function for n' and place into Open list.
Step 5: Else if node n' is already in OPEN and CLOSED, then it should be attached to the
back pointer which reflects the lowest g(n') value.
Step 6: Return to Step 2.
Advantages:
o A* search algorithm is the best algorithm than other search algorithms.
o A* search algorithm is optimal and complete.
o This algorithm can solve very complex problems.
Disadvantages:
o It does not always produce the shortest path as it mostly based on heuristics and
approximation.
o A* search algorithm has some complexity issues.
o The main drawback of A* is memory requirement as it keeps all generated nodes in
the memory, so it is not practical for various large-scale problems.

Example:

In this example, we will traverse the given graph using the A* algorithm. The heuristic value
of all states is given in the below table so we will calculate the f(n) of each state using the
formula f(n)= g(n) + h(n), where g(n) is the cost to reach any node from start state.
Here we will use OPEN and CLOSED list.

Initialization: {(S, 5)}

Iteration1: {(S--> A, 4), (S-->G, 10)}
Iteration2: {(S--> A-->C, 4), (S--> A-->B, 7), (S-->G, 10)}
Iteration3: {(S--> A-->C--->G, 6), (S--> A-->C--->D, 11), (S--> A-->B, 7), (S-->G, 10)}
Iteration 4 will give the final result, as S--->A--->C--->G it provides the optimal path with
cost 6.

Points to remember:
• A* algorithm returns the path which occurred first, and it does not search for all
remaining paths.
• The efficiency of A* algorithm depends on the quality of heuristic.
• A* algorithm expands all nodes which satisfy the condition f(n)
Complete: A* algorithm is complete as long as:
• Branching factor is finite.
• Cost at every action is fixed.
Optimal: A* search algorithm is optimal if it follows below two conditions:
• Admissible: the first condition requires for optimality is that h(n) should be an
admissible heuristic for A* tree search. An admissible heuristic is optimistic in
nature.
• Consistency: Second required condition is consistency for only A* graph-search.
If the heuristic function is admissible, then A* tree search will always find the least cost
path.
Time Complexity: The time complexity of A* search algorithm depends on heuristic
function, and the number of nodes expanded is exponential to the depth of solution d. So
the time complexity is O(b^d), where b is the branching factor.
Space Complexity: The space complexity of A* search algorithm is O(b^d)

Constraint satisfaction problem

A constraint satisfaction problem (or CSP) is a special kind of problem that satisfies some
additional structural properties beyond the basic requirements for problems in general.
In a CSP, the states are defined by the values of a set of variables and the goal test specifies
a set of constraints that the values have to obey.
There are mainly three basic components in the constraint satisfaction problem:
Variables:The things that need to be determined are variables. Variables in a CSP are the
objects that must have values assigned to them in order to satisfy a particular set of
onstraints. Boolean, integer, and categorical variables are just a few examples of the
various types of variables Variables, for instance, could stand in for the many puzzle cells
that need to be filled with numbers in a sudoku puzzle.
Domains: The range of potential values that a variable can have is represented by domains.
Depending on the issue, a domain may be finite or limitless. For instance, in Sudoku, the
set of numbers from 1 to 9 can serve as the domain of a variable representing a problem
cell.
Constraints: The guidelines that control how variables relate to one another are known as
constraints. Constraints in a CSP define the ranges of possible values for variables. Unary
constraints, binary constraints, and higher-order constraints are only a few examples of the
various sorts of constraints. For instance, in a sudoku problem, the restrictions might be that
each row, column, and 3×3 box can only have one instance of each number from 1 to 9.

Examples of CSPs
• Graph/Map coloring
• Sudoku problems
• Cryptarithmetic Problems
• 4-Queen Problems
• Puzzles etc
•
Example ; Cryptarithmetic

Cryptarithmetic: is a type of constraint satisfaction problem in which each alphabet and

symbol is associated with unique digit.
Rules:
1. Each alphabet has a unique digit.
2. Digit ranges from 0-9
3. Only one carry should be found
4. Can be solved from both sides.
 Explanation
• These alphabets then are replaced by numbers such that all the constraints are
satisfied. So initially we have all blank spaces.
• We first look for the MSB in the last word which is 'M' in the word 'MONEY' here.
It is the letter which is generated by carrying. So, carry generated can be only one.
SO, we have M=1.
• Now, we have S+M=O in the second column from the left side. Here M=1.
Therefore, we have, S+1=O. So, we need a number for S such that it generates a
carry when added with 1. And such a number is 9. Therefore, we
have S=9 and O=0.
• Now, in the next column from the same side we have E+O=N. Here we have O=0.
Which means E+0=N which is not possible. This means a carry was generated by
the lower place digits. So we have:
1+E=N ----------(i)
• Next alphabets that we have are N+R=E -------(ii)
• So, for satisfying both equations (i) and (ii), we get E=5 and N=6.
• Now, R should be 9, but 9 is already assigned to S, So, R=8 and we have 1 as a
carry which is generated from the lower place digits.
• Now, we have D+5=Y and this should generate a carry. Therefore, D should be
greater than 4. As 5, 6, 8 and 9 are already assigned, we have D=7 and
therefore Y=2.
• Therefore, the solution to the given Crypt-Arithmetic problem is:
S=9; E=5; N=6; D=7; M=1; O=0; R=8; Y=2
Which can be shown in layout form as:
9567
1085
------------
10652
 Question bank

• What are different Heuristic search techniques.

• List the Characteristics of heuristic search.
• List the properties of Heuristic search Algorithm.
• Write the algorithm for simple Hill climbing Algorithm with advantages and
disadvantages.
• Explain the issues associated with Hill climbing Algorithm.
• Write the algorithm for best first search with advantages and disadvantages.
• Write and explain A* algorithm with suitable example. Write advantages and
disadvantages.
• Explain constraint satisfaction problem with respect to the cryptarithmetic problem
given below
SEND + MORE =MONEY
CROSS +ROADS=DANGER
NOON +SOON = MOON
TWO +TWO=FOUR
• Identify the path for below example using A* algorithm.
• Solve the following Cryptarithmetic puzzle.Write constraint equations and fins one
solution using DFS. Show the steps involved in finding Solution.
i.SEND + MORE=MONEY ii.ROADS +CROSS =DANGER
iii.DONALD +GERALD =ROBERT iv.LOGIC +LOGIC =PROLOG

• Explain Breadth first search with example.

• Explain Depth first search with Example.
• Distinguish between Breadth first search and Depth first search.
• Explain the best first search Algorithm. Write its advantages and Disadvantages.
Identify the path for below example using best first search Algorithm.

2 mark Questions.

• What are the requirements of search algorithms.

• What is Heuristic functions.
• List properties of Heuristic search.
• What is Generate and test strategy?
• What are the Different regions in the state space landscape of Hill climbing algorithm.
• Define Predicate.
• Differentiate between Procedural and Declarative Knowledge.
• What are the requirements of Search Algorithms / Techniques?
• What is Knowledge representation.
• What do you mean by Constraint Satisfaction?