Unit- 1 AI

Iterative deepening depth-first Search:

The iterative deepening algorithm is a combination of DFS and BFS algorithms. This
search algorithm finds out the best depth limit and does it by gradually increasing the
limit until a goal is found.

This algorithm performs depth-first search up to a certain "depth limit", and it keeps
increasing the depth limit after each iteration until the goal node is found.

This Search algorithm combines the benefits of Breadth-first search's fast search and
depth-first search's memory efficiency.

The iterative search algorithm is useful uninformed search when search space is large,
and depth of goal node is unknown.

Advantages:

o It combines the benefits of BFS and DFS search algorithm in terms of fast search
and memory efficiency.

Disadvantages:

o The main drawback of IDDFS is that it repeats all the work of the previous phase.

Example:

Following tree structure is showing the iterative deepening depth-first search. IDDFS
algorithm performs various iterations until it does not find the goal node. The iteration
performed by the algorithm is given as:
1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C, F, G
4'th Iteration------>A, B, D, H, I, E, C, F, K, G
In the fourth iteration, the algorithm will find the goal node.

Completeness:

This algorithm is complete is if the branching factor is finite.

Time Complexity:

Let's suppose b is the branching factor and depth is d then the worst-case time
complexity is O(bd).

Space Complexity:

The space complexity of IDDFS will be O(bd).

Optimal:

IDDFS algorithm is optimal if path cost is a non- decreasing function of the depth of the
node.
Heuristic techniques

In this article, we are going to discuss Heuristic techniques along with some examples
that will help you to understand the Heuristic techniques more clearly.

What is Heuristics?

A heuristic is a technique that is used to solve a problem faster than the classic
methods. These techniques are used to find the approximate solution of a problem
when classical methods do not. Heuristics are said to be the problem-solving
techniques that result in practical and quick solutions.

Heuristics are strategies that are derived from past experience with similar problems.
Heuristics use practical methods and shortcuts used to produce the solutions that may
or may not be optimal, but those solutions are sufficient in a given limited timeframe.

History

Psychologists Daniel Kahneman and Amos Tversky have developed the study of
Heuristics in human decision-making in the 1970s and 1980s. However, this concept
was first introduced by the Nobel Laureate Herbert A. Simon, whose primary object of
research was problem-solving.

Why do we need heuristics?

Heuristics are used in situations in which there is the requirement of a short-term

solution. On facing complex situations with limited resources and time, Heuristics can
help the companies to make quick decisions by shortcuts and approximated
calculations. Most of the heuristic methods involve mental shortcuts to make decisions
on past experiences.

The heuristic method might not always provide us the finest solution, but it is assured
that it helps us find a good solution in a reasonable time.

Based on context, there can be different heuristic methods that correlate with the
problem's scope. The most common heuristic methods are - trial and error, guesswork,
the process of elimination, historical data analysis. These methods involve simply
available information that is not particular to the problem but is most appropriate. They
can include representative, affect, and availability heuristics.

Heuristic search techniques in AI (Artificial Intelligence)

We can perform the Heuristic techniques into two categories:

Direct Heuristic Search techniques in AI

It includes Blind Search, Uninformed Search, and Blind control strategy. These search
techniques are not always possible as they require much memory and time. These
techniques search the complete space for a solution and use the arbitrary ordering of
operations.

The examples of Direct Heuristic search techniques include Breadth-First Search (BFS)
and Depth First Search (DFS).

Hill Climbing Algorithm

It is a technique for optimizing the mathematical problems. Hill Climbing is widely used
when a good heuristic is available.

It is a local search algorithm that continuously moves in the direction of increasing

elevation/value to find the mountain's peak or the best solution to the problem. It
terminates when it reaches a peak value where no neighbor has a higher value.
Traveling-salesman Problem is one of the widely discussed examples of the Hill
climbing algorithm, in which we need to minimize the distance traveled by the salesman.

It is also called greedy local search as it only looks to its good immediate neighbor state
and not beyond that. The steps of a simple hill-climbing algorithm are listed below:
Step 1: Evaluate the initial state. If it is the goal state, then return success and Stop.

Step 2: Loop Until a solution is found or there is no new operator left to apply.

Step 3: Select and apply an operator to the current state.

Step 4: Check new state:

If it is a goal state, then return to success and quit.

Else if it is better than the current state, then assign a new state as a current state.

Else if not better than the current state, then return to step2.

Step 5: Exit.

Best first search (BFS)

This algorithm always chooses the path which appears best at that moment. It is the
combination of depth-first search and breadth-first search algorithms. It lets us to take
the benefit of both algorithms. It uses the heuristic function and search. With the help of
the best-first search, at each step, we can choose the most promising node.

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 the goal node, then return success and stop the search,
else continue to next step.

Step 6: For each successor node, the 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 lists, then add it to the OPEN list.

Step 7: Return to Step 2.

A* Search Algorithm
A* search is the most commonly known form of best-first search. It uses the 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.

It finds the shortest path through the search space using the heuristic function. This
search algorithm expands fewer search tree and gives optimal results faster.

Algorithm of A* search:

Step 1: 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 the
evaluation function (g+h). If node n is the 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 the evaluation function for n' and place it into the 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.

Examples of heuristics in everyday life

Some of the real-life examples of heuristics that people use as a way to solve a
problem:

o Common sense: It is a heuristic that is used to solve a problem based on the

observation of an individual.
o Rule of thumb: In heuristics, we also use a term rule of thumb. This heuristic
allows an individual to make an approximation without doing an exhaustive
search.
o Working backward: It lets an individual solve a problem by assuming that the
problem is already being solved by them and working backward in their minds to
see how much a solution has been reached.
o Availability heuristic: It allows a person to judge a situation based on the
examples of similar situations that come to mind.
 o Familiarity heuristic: It allows a person to approach a problem on the fact that
an individual is familiar with the same situation, so one should act similarly as
he/she acted in the same situation before.
o Educated guess: It allows a person to reach a conclusion without doing an
exhaustive search. Using it, a person considers what they have observed in the
past and applies that history to the situation where there is not any definite
answer has decided yet.

What is an Informed Search in AI?

Algorithms have information on the goal state which helps in more efficient searching.
This information is obtained by a function that estimates how close a state is to the goal
state. Informed search in AI is a type of search algorithm that uses additional
information to guide the search process, allowing for more efficient problem-solving
compared to uninformed search algorithms. This information can be in the form of
heuristics, estimates of cost, or other relevant data to prioritize which states to expand
and explore. Examples of informed search algorithms include A* search, Best-First
search, and Greedy search. Example: Greedy Search and Graph Search.

Here are some key features of informed search algorithms in AI:

 Use of Heuristics – informed search algorithms use heuristics, or additional
information, to guide the search process and prioritize which nodes to expand.
 More efficient – informed search algorithms are designed to be more efficient
than uninformed search algorithms, such as breadth-first search or depth-first
search, by avoiding the exploration of unlikely paths and focusing on more promising
ones.
 Goal-directed – informed search algorithms are goal-directed, meaning that they
are designed to find a solution to a specific problem.
 Cost-based – informed search algorithms often use cost-based estimates to
evaluate nodes, such as the estimated cost to reach the goal or the cost of a
particular path.
 Prioritization – informed search algorithms prioritize which nodes to expand
based on the additional information available, often leading to more efficient
problem-solving.
 Optimality – informed search algorithms may guarantee an optimal solution if
the heuristics used are admissible (never overestimating the actual cost) and
consistent (the estimated cost is a lower bound on the actual cost).
What is an Uninformed Search in AI?
algorithms have no additional information on the goal node other than the one provided
in the problem definition. The plans to reach the goal state from the start state differ only
by the order and length of actions. Uninformed search in AI refers to a type of search
algorithm that does not use additional information to guide the search process. Instead,
these algorithms explore the search space in a systematic, but blind, manner without
considering the cost of reaching the goal or the likelihood of finding a solution.
Examples of uninformed search algorithms include Breadth-First search (BFS), Depth-
First search (DFS), and Depth-Limited search.

Uninformed search algorithms are often used as a starting point for more complex,
informed search algorithms or as a way to explore the search space in simple problems.
However, in complex problems with large search spaces, uninformed search algorithms
may be inefficient and lead to an exponential increase in the number of states
explored. Examples: Depth First Search and Breadth-First Search.

Here are some key features of uninformed search algorithms in AI:

 Systematic exploration – uninformed search algorithms explore the search
space systematically, either by expanding all children of a node (e.g. BFS) or by
exploring as deep as possible in a single path before backtracking (e.g. DFS).
 No heuristics – uninformed search algorithms do not use additional information,
such as heuristics or cost estimates, to guide the search process.
 Blind search – uninformed search algorithms do not consider the cost of
reaching the goal or the likelihood of finding a solution, leading to a blind search
process.
 Simple to implement – uninformed search algorithms are often simple to
implement and understand, making them a good starting point for more complex
algorithms.
 Inefficient in complex problems – uninformed search algorithms can be
inefficient in complex problems with large search spaces, leading to an exponential
increase in the number of states explored.
Not guaranteed to find optimal solution – uninformed search algorithms do not
guarantee an optimal solution, as they do not consider the cost of reaching the goal or
other relevant information.

Solutions Informed Search vs. Uninformed Search is depicted pictorially as follows:

Parameters Informed Search Uninformed Search

It is also known as Heuristic It is also known as Blind

Known as
Search. Search.

Using It uses knowledge for the It doesn’t use knowledge for

Knowledge searching process. the searching process.
Parameters Informed Search Uninformed Search

It finds solution slow as

Performance It finds a solution more quickly. compared to an informed
search.

Completion It may or may not be complete. It is always complete.

Cost Factor Cost is low. Cost is high.

It consumes less time because of It consumes moderate time

Time
quick searching. because of slow searching.

There is a direction given about No suggestion is given

Direction
the solution. regarding the solution in it.

It is less lengthy while It is more lengthy while

Implementation
implemented. implemented.

It is more efficient as efficiency It is comparatively less

takes into account cost and efficient as incurred cost is
Efficiency performance. The incurred cost is more and the speed of finding
less and speed of finding the Breadth-Firstsolution is
solutions is quick. slow.

Computational Computational requirements are Comparatively higher

requirements lessened. computational requirements.

Size of search Having a wide scope in terms of Solving a massive search task
problems handling large search problems. is challenging.
 Parameters Informed Search Uninformed Search

 Depth First Search

 Greedy Search
Examples of (DFS)
 A* Search
Algorithms  Breadth First Search
 AO* Search
(BFS)
 Hill Climbing Algorithm

Informed Search Algorithms

So far we have talked about the uninformed search algorithms which looked through
search space for all possible solutions of the problem without having any additional
knowledge about search space. But informed search algorithm contains an array of
knowledge such as how far we are from the goal, path cost, how to reach to goal node,
etc. This knowledge help agents to explore less to the search space and find more
efficiently the goal node.

The informed search algorithm is more useful for large search space. Informed search
algorithm uses the idea of heuristic, so it is also called Heuristic search.

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.

Admissibility of the heuristic function is given as:

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

Pure Heuristic Search:

Pure heuristic search is the simplest form of heuristic search algorithms. It expands
nodes based on their heuristic value h(n). It maintains two lists, OPEN and CLOSED
list. In the CLOSED list, it places those nodes which have already expanded and in the
OPEN list, it places nodes which have yet not been expanded.
 On each iteration, each node n with the lowest heuristic value is expanded and
generates all its successors and n is placed to the closed list. The algorithm continues
unit a goal state is found.

In the informed search we will discuss two main algorithms which are given below:

o Best First Search Algorithm(Greedy search)

o A* Search Algorithm

1.) Best-first Search Algorithm (Greedy 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.

1. 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:

o Step 1: Place the starting node into the OPEN list.

o Step 2: If the OPEN list is empty, Stop and return failure.
o 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.
o Step 4: Expand the node n, and generate the successors of node n.
o 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.
o 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.
o Step 7: Return to Step 2.

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

Disadvantages:

o It can behave as an unguided depth-first search in the worst case scenario.

o It can get stuck in a loop as DFS.
o 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.

In this search example, we are using two lists which are OPEN and CLOSED Lists.
Following are the iteration for traversing the above example.
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.

2.) 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.

Solution:
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:

o A* algorithm returns the path which occurred first, and it does not search for all
remaining paths.
o The efficiency of A* algorithm depends on the quality of heuristic.
o A* algorithm expands all nodes which satisfy the condition f(n)<="" li="">

Complete: A* algorithm is complete as long as:

o Branching factor is finite.

o Cost at every action is fixed.
Optimal: A* search algorithm is optimal if it follows below two conditions:

o 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.
o 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)

What is CSP in AI? Constraint Satisfaction Problems (CSPs) are a class of

computational problems where the goal is to find a solution that satisfies a set of
constraints. These constraints impose restrictions on the values or assignments of
variables in such a way that the variables must be assigned values from their respective
domains while meeting all specified conditions.

Significance of Constraint Satisfaction Problem in AI

CSPs are highly significant in artificial intelligence for several reasons:

 They model a wide range of real-world problems where decision-making is

subject to certain conditions and limitations.
 CSPs offer a structured and general framework for representing and solving
problems, making them versatile in problem-solving applications.
 Many AI applications, such as scheduling, planning, and configuration, can be
mapped to CSPs, allowing AI systems to find optimal solutions efficiently.

Key Elements of CSPs

CSPs are characterized by three main components:

 1. Variables: Variables represent the entities or components of the problem that
need to be assigned values. For example, in a scheduling problem, variables
might represent time slots or tasks.
2. Domains: Each variable has an associated domain, which defines the set of
values that the variable can take. For instance, in scheduling, the domain of a
time slot variable might be a list of available times.

3. Constraints: Constraints are the rules or conditions that specify relationships

between variables. They restrict the combinations of values that variables can
take. Constraints can be unary (involving a single variable) or binary (involving
two variables) or involve more variables.

Real-World Examples of CSPs

To illustrate CSPs, consider the following examples:

 Sudoku Puzzles: In Sudoku, the variables are the empty cells, the domains are
numbers from 1 to 9, and the constraints ensure that no number is repeated in a
row, column, or 3x3 subgrid.
 Scheduling Problems: In university course scheduling, variables might
represent classes, domains represent time slots, and constraints ensure that
classes with overlapping students or instructors cannot be scheduled
simultaneously.

 Map Coloring: In the map coloring problem, variables represent regions or

countries, domains represent available colors, and constraints ensure that
adjacent regions must have different colors.

These examples demonstrate how CSPs provide a framework for modeling and solving
problems that require satisfying various conditions and limitations, making them a
fundamental tool in AI and operations research.
Example of CSP in AI

Constraint Satisfaction Problem in Artificial Intelligence

Representation of CSPs:

The representation of Constraint Satisfaction Problems (CSPs) is crucial for effectively

solving these problems. Let's explore how to represent CSPs using variables, domains,
and constraints:

1. Variables as Placeholders:

Variables in CSPs act as placeholders for problem components that need to be

assigned values. They represent the entities or attributes of the problem under
consideration. For example:

 In a Sudoku puzzle, variables represent the empty cells that need numbers.
 In job scheduling, variables might represent tasks to be scheduled.
  In map coloring, variables correspond to regions or countries that need to be
colored.

The choice of variables depends on the specific problem being modeled.

2. Domains:

Each variable in a CSP is associated with a domain, which defines the set of values that
the variable can take. Domains are a critical part of the CSP representation, as they
restrict the possible assignments of values to variables. For instance:

 In Sudoku, the domain for each empty cell is the numbers from 1 to 9.
 In scheduling, the domain for a task might be the available time slots.
 In map coloring, the domain could be a list of available colors.

Domains ensure that variable assignments remain within the specified range of values.

3. Constraints:

Constraints in CSPs specify the relationships or conditions that must be satisfied by the
variables. Constraints restrict the combinations of values that variables can take.
Constraints can be unary (involving a single variable), binary (involving two variables),
or n-ary (involving more than two variables). Constraints are typically represented in the
form of logical expressions, equations, or functions. For example:

 In Sudoku, constraints ensure that no two numbers are repeated in the same
row, column, or subgrid.
 In scheduling, constraints might involve ensuring that two tasks are not
scheduled at the same time.
 In map coloring, constraints require that adjacent regions have different colors.

Constraint specification is a crucial part of problem modeling, as it defines the rules that
the variables must follow.

Overall Representation:

To represent a CSP, you need to define:

 The set of variables: What entities or attributes need values?

 The domains: What are the possible values that each variable can take?
 The constraints: What conditions or limitations must be satisfied by the
variables?