20

2.4.1 Control Strategies

The word ‘search’ refers to the search for a solution in a problem space.
• Search proceeds with different types of ‘search control strategies’.
• A strategy is defined by picking the order in which the nodes expand.
The Search strategies are evaluated along the following dimensions: Completeness, Time
complexity, Space complexity, Optimality (the search- related terms are first explained, and then
the search algorithms and control strategies are illustrated next).

Search-related terms
• Algorithm’s performance and complexity
Ideally we want a common measure so that we can compare approaches in order to select
the most appropriate algorithm for a given situation.
 Performance of an algorithm depends on internal and external factors.

Internal factors/ External factors

 Time required to run
 Size of input to the algorithm
 Space (memory) required to run
 Speed of the computer
 Quality of the compiler
 Complexity is a measure of the performance of an algorithm. Complexity
measures the internal factors, usually in time than space.
• Computational complexity\
It is the measure of resources in terms of Time and Space.

 If A is an algorithm that solves a decision problem f, then run-time of A is the number of

steps taken on the input of length n.
 Time Complexity T(n) of a decision problem f is the run-time of the ‘best’ algorithm A
for f.
 Space Complexity S(n) of a decision problem f is the amount of memory used by the
‘best’ algorithm A for f.

• ‘Big - O’ notation
The Big-O, theoretical measure of the execution of an algorithm, usually indicates the time or the
memory needed, given the problem size n, which is usually the number of items.
• Big-O notation
The Big-O notation is used to give an approximation to the run-time- efficiency of an algorithm;
the letter ‘O’ is for order of magnitude of operations or space at run-time.
• The Big-O of an Algorithm A
 If an algorithm A requires time proportional to f(n), then algorithm A is said to be
of order f(n), and it is denoted as O(f(n)).
 If algorithm A requires time proportional to n2, then the order of the algorithm is
said to be O(n2).
 If algorithm A requires time proportional to n, then the order of the algorithm is
said to be O(n).

21
The function f(n) is called the algorithm’s growth-rate function. In other words, if an algorithm
has performance complexity O(n), this means that the run-time t should be directly proportional
to n, ie t • n or t = k n where k is constant of proportionality.
Similarly, for algorithms having performance complexity O(log2(n)), O(log N), O(N log N),
O(2N) and so on.

Example 1:
Determine the Big-O of an algorithm:

Calculate the sum of the n elements in an integer array a[0..n-1].

Line no. Instructions No of execution steps

line 1 sum 1
line 2 for (i = 0; i < n; i++) n+1
line 3 sum += a[i] n
line 4 print sum 1
Total 2n + 3

Thus, the polynomial (2n + 3) is dominated by the 1st term as n while the number of elements in
the array becomes very large.

• In determining the Big-O, ignore constants such as 2 and 3. So the algorithm is of order n.
• So the Big-O of the algorithm is O(n).
• In other words the run-time of this algorithm increases roughly as the size of the input data n,
e.g., an array of size n.

Tree structure
Tree is a way of organizing objects, related in a hierarchical fashion.
• Tree is a type of data structure in which each element is attached to one or more
elements directly beneath it.
• The connections between elements are called branches.
• Tree is often called inverted trees because it is drawn with the root at the top.
• The elements that have no elements below them are called leaves.
• A binary tree is a special type: each element has only two branches below it.
Properties
• Tree is a special case of a graph.
• The topmost node in a tree is called the root node.
• At root node all operations on the tree begin.
• A node has at most one parent.
• The topmost node (root node) has no parents.
• Each node has zero or more child nodes, which are below it .
• The nodes at the bottommost level of the tree are called leaf nodes.
Since leaf nodes are at the bottom most level, they do not have children.
• A node that has a child is called the child’s parent node.
• The depth of a node n is the length of the path from the root to the node.
• The root node is at depth zero.

22
• Stacks and Queues

The Stacks and Queues are data structures that maintain the order of last-in, first-out and first-in,
first-out respectively. Both stacks and queues are often implemented as linked lists, but that is
not the only possible implementation.
Stack - Last In First Out (LIFO) lists
 An ordered list; a sequence of items, piled one on top of the other.
 The insertions and deletions are made at one end only, called Top.
 If Stack S = (a[1], a[2], . . . . a[n]) then a[1] is bottom most element
 Any intermediate element (a[i]) is on top of element a[i-1], 1 < i <= n.
 In Stack all operation take place on Top.

The Pop operation removes item from top of the stack.

The Push operation adds an item on top of the stack.

Queue - First In First Out (FIFO) lists

• An ordered list; a sequence of items; there are restrictions about how items can be added to and
removed from the list. A queue has two ends.
• All insertions (enqueue ) take place at one end, called Rear or Back
• All deletions (dequeue) take place at other end, called Front.
• If Queue has a[n] as rear element then a[i+1] is behind a[i] , 1 < i <= n.
• All operation takes place at one end of queue or the other.

The Dequeue operation removes the item at Front of the queue.

The Enqueue operation adds an item to the Rear of the queue.
Search

Search is the systematic examination of states to find path from the start / root state to the goal
state.

• Search usually results from a lack of knowledge.

• Search explores knowledge alternatives to arrive at the best answer.
• Search algorithm output is a solution, that is, a path from the initial state to a state that satisfies
the goal test.

For general-purpose problem-solving – ‘Search’ is an approach.

• Search deals with finding nodes having certain properties in a graph that represents search
space.
• Search methods explore the search space ‘intelligently’, evaluating possibilities without
investigating every single possibility.
Examples:
• For a Robot this might consist of PICKUP, PUTDOWN, MOVEFORWARD, MOVEBACK,
MOVELEFT, and MOVERIGHT—until the goal is reached.
• Puzzles and Games have explicit rules: e.g., the ‘Tower of Hanoi’ puzzle

23
This puzzle involves a set of rings of different sizes that can be placed on three different pegs.
• The puzzle starts with the rings arranged as shown in Figure 2.4(a)
• The goal of this puzzle is to move them all as to Figure 2.4(b)
• Condition: Only the top ring on a peg can be moved, and it may only be placed on a smaller
ring, or on an empty peg.

In this Tower of Hanoi puzzle:

• Situations encountered while solving the problem are described as states.
• Set of all possible configurations of rings on the pegs is called ‘problem space’.
• States
A State is a representation of elements in a given moment.
A problem is defined by its elements and their relations.
At each instant of a problem, the elements have specific descriptors and relations; the descriptors
indicate how to select elements?
Among all possible states, there are two special states called:
 Initial state – the start point
 Final state – the goal state
• State Change: Successor Function
A ‘successor function’ is needed for state change. The Successor Function moves one state to
another state.
Successor Function:
 It is a description of possible actions; a set of operators.
 It is a transformation function on a state representation, which converts that state into
another state.
 It defines a relation of accessibility among states.
 It represents the conditions of applicability of a state and corresponding transformation
function.

• State space
A state space is the set of all states reachable from the initial state.
 A state space forms a graph (or map) in which the nodes are states and the arcs between
nodes are actions.
 In a state space, a path is a sequence of states connected by a sequence of actions.
 The solution of a problem is part of the map formed by the state space.

24
• Structure of a state space
The structures of a state space are trees and graphs.
 A tree is a hierarchical structure in a graphical form.
 A graph is a non-hierarchical structure.
• A tree has only one path to a given node;
i.e., a tree has one and only one path from any point to any other point.
• A graph consists of a set of nodes (vertices) and a set of edges (arcs). Arcs establish
relationships (connections) between the nodes; i.e., a graph has several paths to a given node.
• The Operators are directed arcs between nodes.
A search process explores the state space. In the worst case, the search explores all possible
paths between the initial state and the goal state.
• Problem solution
In the state space, a solution is a path from the initial state to a goal state or, sometimes, just a
goal state.
 A solution cost function assigns a numeric cost to each path; it also gives the cost of
applying the operators to the states.
 A solution quality is measured by the path cost function; and an optimal solution has the
lowest path cost among all solutions.
 The solutions can be any or optimal or all.
 The importance of cost depends on the problem and the type of solution asked

• Problem description
A problem consists of the description of:
 The current state of the world,
 The actions that can transform one state of the world into another,
 The desired state of the world.
The following action one taken to describe the problem:
 State space is defined explicitly or implicitly
A state space should describe everything that is needed to solve a problem and nothing that is
not needed to solve the problem.
 Initial state is start state
 Goal state is the conditions it has to fulfill.
The description by a desired state may be complete or partial.
 Operators are to change state
 Operators do actions that can transform one state into another;
 Operators consist of: Preconditions and Instructions;

Preconditions provide partial description of the state of the world that must be true in order to
perform the action, and
Instructions tell the user how to create the next state.
 Operators should be as general as possible, so as to reduce their number.
 Elements of the domain has relevance to the problem
 Knowledge of the starting point.
 Problem solving is finding a solution
 Find an ordered sequence of operators that transform the current (start) state
into a goal state.

25
  Restrictions are solution quality any, optimal, or all
 Finding the shortest sequence, or
 finding the least expensive sequence defining cost, or
 finding any sequence as quickly as possible.
This can also be explained with the help of algebraic function as given below.

PROBLEM CHARACTERISTICS

Heuristics cannot be generalized, as they are domain specific. Production systems provide ideal
techniques for representing such heuristics in the form of IF-THEN rules. Most problems
requiring simulation of intelligence use heuristic search extensively. Some heuristics are used to
define the control structure that guides the search process, as seen in the example described
above. But heuristics can also be encoded in the rules to represent the domain knowledge. Since
most AI problems make use of knowledge and guided search through the knowledge, AI can be
described as the study of techniques for solving exponentially hard problems in polynomial time
by exploiting knowledge about problem domain.

To use the heuristic search for problem solving, we suggest analysis of the problem for the
following considerations:
 Decomposability of the problem into a set of independent smaller subproblems
 Possibility of undoing solution steps, if they are found to be unwise
 Predictability of the problem universe
 Possibility of obtaining an obvious solution to a problem without comparison of all other
possible solutions
 Type of the solution: whether it is a state or a path to the goal state
 Role of knowledge in problem solving
 Nature of solution process: with or without interacting with the user

The general classes of engineering problems such as planning, classification, diagnosis,

monitoring and design are generally knowledge intensive and use a large amount of heuristics.
Depending on the type of problem, the knowledge representation schemes and control strategies
for search are to be adopted. Combining heuristics with the two basic search strategies have been
discussed above. There are a number of other general-purpose search techniques which are
essentially heuristics based. Their efficiency primarily depends on how they exploit the domain-
specific knowledge to abolish undesirable paths. Such search methods are called ‘weak
methods’, since the progress of the search depends heavily on the way the domain knowledge is
exploited. A few of such search techniques which form the centre of many AI systems are briefly
presented in the following sections.

Problem Decomposition

Suppose to solve the expression is: + (X³ + X² + 2X + 3sinx) dx

26
This problem can be solved by breaking it into smaller problems, each of which we can solve by
using a small collection of specific rules. Using this technique of problem decomposition, we can
solve very large problems very easily. This can be considered as an intelligent behaviour.

Can Solution Steps be Ignored?

Suppose we are trying to prove a mathematical theorem: first we proceed considering that
proving a lemma will be useful. Later we realize that it is not at all useful. We start with another
one to prove the theorem. Here we simply ignore the first method.
Consider the 8-puzzle problem to solve: we make a wrong move and realize that mistake. But
here, the control strategy must keep track of all the moves, so that we can backtrack to the initial
state and start with some new move.
Consider the problem of playing chess. Here, once we make a move we never recover from that
step. These problems are illustrated in the three important classes of problems mentioned below:
1. Ignorable, in which solution steps can be ignored. Eg: Theorem Proving
2. Recoverable, in which solution steps can be undone. Eg: 8-Puzzle
3. Irrecoverable, in which solution steps cannot be undone. Eg: Chess

Is the Problem Universe Predictable?

Consider the 8-Puzzle problem. Every time we make a move, we know exactly what will happen.
This means that it is possible to plan an entire sequence of moves and be confident what the
resulting state will be. We can backtrack to earlier moves if they prove unwise.

Suppose we want to play Bridge. We need to plan before the first play, but we cannot play with
certainty. So, the outcome of this game is very uncertain. In case of 8-Puzzle, the outcome is
very certain. To solve uncertain outcome problems, we follow the process of plan revision as the
plan is carried out and the necessary feedback is provided. The disadvantage is that the planning
in this case is often very expensive.

Is Good Solution Absolute or Relative?

Consider the problem of answering questions based on a database of simple facts such as the
following:

27
 1. Siva was a man.
2. Siva was a worker in a company.
3. Siva was born in 1905.
4. All men are mortal.
5. All workers in a factory died when there was an accident in 1952.
6. No mortal lives longer than 100 years.
Suppose we ask a question: ‘Is Siva alive?’
By representing these facts in a formal language, such as predicate logic, and then using formal
inference methods we can derive an answer to this question easily.
There are two ways to answer the question shown below:
Method I:
1. Siva was a man.
2. Siva was born in 1905.
3. All men are mortal.
4. Now it is 2008, so Siva’s age is 103 years.
5. No mortal lives longer than 100 years.
Method II:
1. Siva is a worker in the company.
2. All workers in the company died in 1952.
Answer: So Siva is not alive. It is the answer from the above methods.

We are interested to answer the question; it does not matter which path we follow. If we follow
one path successfully to the correct answer, then there is no reason to go back and check another
path to lead the solution.

CHARACTERISTICS OF PRODUCTION SYSTEMS

Production systems provide us with good ways of describing the operations that can be
performed in a search for a solution to a problem.
At this time, two questions may arise:
1. Can production systems be described by a set of characteristics? And how can they be
easily implemented?
2. What relationships are there between the problem types and the types of production
systems well suited for solving the problems?
To answer these questions, first consider the following definitions of classes of production
systems:
1. A monotonic production system is a production system in which the application of a
rule never prevents the later application of another rule that could also have been
applied at the time the first rule was selected.
2. A non-monotonic production system is one in which this is not true.
3. A partially communicative production system is a production system with the
property that if the application of a particular sequence of rules transforms state P into
state Q, then any combination of those rules that is allowable also transforms state P
into state Q.
4. A commutative production system is a production system that is both monotonic and
partially commutative.

28
 Is there any relationship between classes of production systems and classes of problems?
For any solvable problems, there exist an infinite number of production systems that show how
to find solutions. Any problem that can be solved by any production system can be solved by a
commutative one, but the commutative one is practically useless. It may use individual states to
represent entire sequences of applications of rules of a simpler, non-commutative system. In the
formal sense, there is no relationship between kinds of problems and kinds of production systems
Since all problems can be solved by all kinds of systems. But in the practical sense, there is
definitely such a relationship between the kinds of problems and the kinds of systems that lend
themselves to describing those problems.

Partially commutative, monotonic productions systems are useful for solving ignorable
problems. These are important from an implementation point of view without the ability to
backtrack to previous states when it is discovered that an incorrect path has been followed. Both
types of partially commutative production systems are significant from an implementation point;
they tend to lead to many duplications of individual states during the search process. Production
systems that are not partially commutative are useful for many problems in which permanent
changes occur.

Issues in the Design of Search Programs

Each search process can be considered to be a tree traversal. The object of the search is to find a
path from the initial state to a goal state using a tree. The number of nodes generated might be
huge; and in practice many of the nodes would not be needed. The secret of a good search
routine is to generate only those nodes that are likely to be useful, rather than having a precise
tree. The rules are used to represent the tree implicitly and only to create nodes explicitly if they
are actually to be of use.

The following issues arise when searching:

• The tree can be searched forward from the initial node to the goal state or backwards from the
goal state to the initial state.
• To select applicable rules, it is critical to have an efficient procedure for matching rules against
states.
• How to represent each node of the search process? This is the knowledge representation
problem or the frame problem. In games, an array suffices; in other problems, more complex
data structures are needed.

Finally in terms of data structures, considering the water jug as a typical problem do we use a
graph or tree? The breadth-first structure does take note of all nodes generated but the depth-first
one can be modified.

29
Check duplicate nodes

1. Observe all nodes that are already generated, if a new node is present.
2. If it exists add it to the graph.
3. If it already exists, then
a. Set the node that is being expanded to the point to the already existing node
corresponding to its successor rather than to the new one. The new one can be thrown
away.

b. If the best or shortest path is being determined, check to see if this path is better or
worse than the old one. If worse, do nothing.

Better save the new path and work the change in length through the chain of successor nodes if
necessary.

Example: Tic-Tac-Toe

State spaces are good representations for board games such as Tic-Tac-Toe. The position of a
game can be explained by the contents of the board and the player whose turn is next. The board
can be represented as an array of 9 cells, each of which may contain an X or O or be empty.
• State:
 Player to move next: X or O.
 Board configuration:

• Operators: Change an empty cell to X or O.

• Start State: Board empty; X’s turn.
• Terminal States: Three X’s in a row; Three O’s in a row; All cells full.

Search Tree

The sequence of states formed by possible moves is called a search tree. Each level of the tree is
called a ply.

Since the same state may be reachable by different sequences of moves, the state space may in
general be a graph. It may be treated as a tree for simplicity, at the cost of duplicating states.

30
Solving problems using search
• Given an informal description of the problem, construct a formal description as a state space:
 Define a data structure to represent the state.
 Make a representation for the initial state from the given data.
 Write programs to represent operators that change a given state representation to a new
state representation.
 Write a program to detect terminal states.

• Choose an appropriate search technique:

 How large is the search space?
 How well structured is the domain?
 What knowledge about the domain can be used to guide the search?

31
HEURISTIC SEARCH TECHNIQUES:
Search Algorithms
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.
• Uninformed search algorithms or Brute-force algorithms, search through the search space all
possible candidates for the solution checking whether each candidate satisfies the problem’s
statement.
• Informed search algorithms use heuristic functions that are specific to the problem, apply
them to guide the search through the search space to try to reduce the amount of time spent in
searching.

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.

32
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.

33
Breadth-first search
A Search strategy, in which the highest layer of a decision tree is searched completely before
proceeding to the next layer is called Breadth-first search (BFS).
• In this strategy, no viable solutions are omitted and therefore it is guaranteed that an optimal
solution is found.
• This strategy is often not feasible when the search space is large.
Algorithm
1. Create a variable called LIST and set it to be the starting state.
2. Loop until a goal state is found or LIST is empty, Do
a. Remove the first element from the LIST and call it E. If the LIST is empty, quit.
b. For every path each rule can match the state E, Do
(i) Apply the rule to generate a new state.
(ii) If the new state is a goal state, quit and return this state.
(iii) Otherwise, add the new state to the end of LIST.

34
Advantages
1. Guaranteed to find an optimal solution (in terms of shortest number of steps
to reach the goal).
2. Can always find a goal node if one exists (complete).
Disadvantages
1. High storage requirement: exponential with tree depth.
Depth-first search
A search strategy that extends the current path as far as possible before backtracking to the last
choice point and trying the next alternative path is called Depth-first search (DFS).
• This strategy does not guarantee that the optimal solution has been found.
• In this strategy, search reaches a satisfactory solution more rapidly than breadth first, an
advantage when the search space is large.
Algorithm
Depth-first search applies operators to each newly generated state, trying to drive directly toward
the goal.
1. If the starting state is a goal state, quit and return success.
2. Otherwise, do the following until success or failure is signalled:
a. Generate a successor E to the starting state. If there are no more successors, then signal failure.
b. Call Depth-first Search with E as the starting state.
c. If success is returned signal success; otherwise, continue in the loop.
Advantages
1. Low storage requirement: linear with tree depth.
2. Easily programmed: function call stack does most of the work of maintaining state of the
search.
Disadvantages
1. May find a sub-optimal solution (one that is deeper or more costly than the best solution).
2. Incomplete: without a depth bound, may not find a solution even if one exists.
[Link] Bounded depth-first search
Depth-first search can spend much time (perhaps infinite time) exploring a very deep path that
does not contain a solution, when a shallow solution exists. An easy way to solve this problem is
to put a maximum depth bound on the search. Beyond the depth bound, a failure is generated
automatically without exploring any deeper.
Problems:
1. It’s hard to guess how deep the solution lies.
2. If the estimated depth is too deep (even by 1) the computer time used is dramatically
increased, by a factor of bextra.
3. If the estimated depth is too shallow, the search fails to find a solution; all that computer time
is wasted.

Heuristics
A heuristic is a method that improves the efficiency of the search process. These are like tour
guides. There are good to the level that they may neglect the points in general interesting
directions; they are bad to the level that they may neglect points of interest to particular
individuals. Some heuristics help in the search process without sacrificing any claims to entirety
that the process might previously had. Others may occasionally cause an excellent path to be
overlooked. By sacrificing entirety it increases efficiency. Heuristics may not find the best

35
solution every time but guarantee that they find a good solution in a reasonable time. These are
particularly useful in solving tough and complex problems, solutions of which would require
infinite time, i.e. far longer than a lifetime for the problems which are not solved in any other
way.
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 traveller 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.
Heuristic search techniques
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.

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

Comparison of Algorithms

Brute force / Blind search Heuristic search

Can only search what it has knowledge Estimates ‘distance’ to goal state
about already through explored nodes

No knowledge about how far a node Guides search process toward goal
node from goal state
Prefers states (nodes) that lead
close to and not away from goal
state

Example: Travelling salesman

A salesman has to visit a list of cities and he must visit each city only once. There are different
routes between the cities. The problem is to find the shortest route between the cities so that the
salesman visits all the cities at once.

Suppose there are N cities, then a solution would be to take N! possible combinations to find the
shortest distance to decide the required route. This is not efficient as with N=10 there are
36,28,800 possible routes. This is an example of combinatorial explosion.

There are better methods for the solution of such problems: one is called branch and bound.
First, generate all the complete paths and find the distance of the first complete path. If the next
path is shorter, then save it and proceed this way avoiding the path when its length exceeds the
saved shortest path length, although it is better than the previous method.

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.
Algorithm: Generate-And-Test
[Link] a possible solution.
[Link] to see if this is the expected solution.
[Link] the solution has been found quit else go to step 1.
Potential solutions that need to be generated vary depending on the kinds of problems. For some
problems the possible solutions may be particular points in the problem space and for some
problems, paths from the start state.

37
Figure: Generate And Test
Generate-and-test, like depth-first search, requires that complete solutions be generated for
testing. In its most systematic form, it is only an exhaustive search of the problem space.
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.
Systematic Generate-And-Test
While generating complete solutions and generating random solutions are the two extremes there
exists another approach that lies in between. The approach is that the search process proceeds
systematically but some paths that unlikely to lead the solution are not considered. This
evaluation is performed by a heuristic function.
Depth-first search tree with backtracking can be used to implement systematic generate-and-test
procedure. As per this procedure, if some intermediate states are likely to appear often in the
tree, it would be better to modify that procedure to traverse a graph rather than a tree.
Generate-And-Test And Planning
Exhaustive generate-and-test is very useful for simple problems. But for complex problems even
heuristic generate-and-test is not very effective technique. But this may be made effective by
combining with other techniques in such a way that the space in which to search is restricted. An
AI program DENDRAL, for example, uses plan-Generate-and-test technique. First, the planning
process uses constraint-satisfaction techniques and creates lists of recommended and
contraindicated substructures. Then the generate-and-test procedure uses the lists generated and
required to explore only a limited set of structures. Constrained in this way, generate-and-test
proved highly effective. A major weakness of planning is that it often produces inaccurate
solutions as there is no feedback from the world. But if it is used to produce only pieces of
solutions then lack of detailed accuracy becomes unimportant.

38
Hill Climbing
Hill Climbing is heuristic search used for mathematical optimization problems in the field of
Artificial Intelligence .
Given a large set of inputs and a good heuristic function, it tries to find a sufficiently good
solution to the problem. This solution may not be the global optimal maximum.
 In the above definition, mathematical optimization problems implies that hill climbing
solves the problems where we need to maximize or minimize a given real function by
choosing values from the given inputs. Example-Travelling salesman problem where we
need to minimize the distance traveled by salesman.
 ‘Heuristic search’ means that this search algorithm may not find the optimal solution to
the problem. However, it will give a good solution in reasonable time.
 A heuristic function is a function that will rank all the possible alternatives at any
branching step in search algorithm based on the available information. It helps the
algorithm to select the best route out of possible routes.
Features of Hill Climbing
1. Variant of generate and test algorithm : It is a variant of generate and test algorithm. The
generate and test algorithm is as follows :

1. Generate a possible solutions.

2. Test to see if this is the expected solution.
3. If the solution has been found quit else go to step 1.
Hence we call Hill climbing as a variant of generate and test algorithm as it takes the feedback
from test procedure. Then this feedback is utilized by the generator in deciding the next move in
search space.
2. Uses the Greedy approach : 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 optimal solution at
the end.
Types of Hill Climbing

1. Simple Hill climbing : It examines the neighboring nodes one by one and selects the first
neighboring node which optimizes the current cost as next node.
Algorithm for Simple Hill climbing :
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 current state.
a) Select a state 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.

39
 2. Steepest-Ascent Hill climbing : It first examines all the neighboring nodes and then
selects the node closest to the solution state as next node.

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
i. Let ‘target’ be a state such that any successor of the current state will be better than it;
ii. for each operator that applies to the current state
a. apply the new operator and create a new state
b. evaluate the new state
c. if this state is goal state then quit else compare with ‘target’
d. if this state is better than ‘target’, set this state as ‘target’
e. if target is better than current state set current state to Target
Step 3 : Exit
3. Stochastic hill climbing : It does not examine all the neighboring nodes before deciding
which node to select .It just selects a neighboring node at random, and decides (based on
the amount of improvement in that neighbor) whether to move to that neighbor or to
examine another.
State Space diagram for Hill Climbing
State space diagram is a graphical representation of the set of states our search algorithm can
reach vs the value of our objective function(the function which we wish to maximize).
X-axis : denotes the state space ie states or configuration our algorithm may reach.
Y-axis : denotes the values of objective function corresponding to to a particular state.
The best solution will be that state space where objective function has maximum value(global
maximum).

Different regions in the State Space Diagram

1. Local maximum : It is a state which is better than its neighboring state however there
exists a state which is better than it(global maximum). This state is better because here
value of objective function is higher than its neighbors.

40