Tag: Artificial Intelligence Notes for CSE JNTU

A* Algorithm | A* Algorithm Example in AI

Artificial Intelligence

A* Algorithm-

 

  • A* Algorithm is one of the best and popular techniques used for path finding and graph traversals.
  • A lot of games and web-based maps use this algorithm for finding the shortest path efficiently.
  • It is essentially a best first search algorithm.

 

Working-

 

A* Algorithm works as-

  • It maintains a tree of paths originating at the start node.
  • It extends those paths one edge at a time.
  • It continues until its termination criterion is satisfied.

 

A* Algorithm extends the path that minimizes the following function-

f(n) = g(n) + h(n)

 

Here,

  • ‘n’ is the last node on the path
  • g(n) is the cost of the path from start node to node ‘n’
  • h(n) is a heuristic function that estimates cost of the cheapest path from node ‘n’ to the goal node

 

Algorithm-

 

  • The implementation of A* Algorithm involves maintaining two lists- OPEN and CLOSED.
  • OPEN contains those nodes that have been evaluated by the heuristic function but have not been expanded into successors yet.
  • CLOSED contains those nodes that have already been visited.

 

The algorithm is as follows-

 

Step-01:

 

  • Define a list OPEN.
  • Initially, OPEN consists solely of a single node, the start node S.

 

Step-02:

 

If the list is empty, return failure and exit.

 

Step-03:

 

  • Remove node n with the smallest value of f(n) from OPEN and move it to list CLOSED.
  • If node n is a goal state, return success and exit.

 

Step-04:

 

Expand node n.

 

Step-05:

 

  • If any successor to n is the goal node, return success and the solution by tracing the path from goal node to S.
  • Otherwise, go to Step-06.

 

Step-06:

 

For each successor node,

  • Apply the evaluation function f to the node.
  • If the node has not been in either list, add it to OPEN.

 

Step-07:

 

Go back to Step-02.

 

AI algorithms will differ based on their applications.  For a better understanding of how AI algorithms work in coding, the Github Certification course offers skills to learn how AI algorithms are used to analyze code, identify bugs, etc.

 

PRACTICE PROBLEMS BASED ON A* ALGORITHM-

 

Problem-01:

 

Given an initial state of a 8-puzzle problem and final state to be reached-

 

 

Find the most cost-effective path to reach the final state from initial state using A* Algorithm.

Consider g(n) = Depth of node and h(n) = Number of misplaced tiles.

 

Solution-

 

  • A* Algorithm maintains a tree of paths originating at the initial state.
  • It extends those paths one edge at a time.
  • It continues until final state is reached.

 

 

Problem-02:

 

Consider the following graph-

 

 

The numbers written on edges represent the distance between the nodes.

The numbers written on nodes represent the heuristic value.

Find the most cost-effective path to reach from start state A to final state J using A* Algorithm.

 

Solution-

 

Step-01:

 

  • We start with node A.
  • Node B and Node F can be reached from node A.

 

A* Algorithm calculates f(B) and f(F).

  • f(B) = 6 + 8 = 14
  • f(F) = 3 + 6 = 9

 

Since f(F) < f(B), so it decides to go to node F.

 

Path- A → F

 

Step-02:

 

Node G and Node H can be reached from node F.

 

A* Algorithm calculates f(G) and f(H).

  • f(G) = (3+1) + 5 = 9
  • f(H) = (3+7) + 3 = 13

 

Since f(G) < f(H), so it decides to go to node G.

 

Path- A → F → G

 

Step-03:

 

Node I can be reached from node G.

 

A* Algorithm calculates f(I).

f(I) = (3+1+3) + 1 = 8

It decides to go to node I.

 

Path- A → F → G → I

 

Step-04:

 

Node E, Node H and Node J can be reached from node I.

 

A* Algorithm calculates f(E), f(H) and f(J).

  • f(E) = (3+1+3+5) + 3 = 15
  • f(H) = (3+1+3+2) + 3 = 12
  • f(J) = (3+1+3+3) + 0 = 10

 

Since f(J) is least, so it decides to go to node J.

 

Path- A → F → G → I → J

This is the required shortest path from node A to node J.

 

 

Important Note-

 

It is important to note that-

  • A* Algorithm is one of the best path finding algorithms.
  • But it does not produce the shortest path always.
  • This is because it heavily depends on heuristics.

 

To gain better understanding about A* Search Algorithm,

Watch this Video Lecture

 

Get more notes and other study material of Artificial Intelligence.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Genetic Algorithm in AI | Operators | Working

Artificial Intelligence

Genetic Algorithm-

 

In Artificial Intelligence,

  • Genetic Algorithm is one of the heuristic algorithms.
  • They are used to solve optimization problems.
  • They are inspired by Darwin’s Theory of Evolution.
  • They are an intelligent exploitation of a random search.
  • Although randomized, Genetic Algorithms are by no means random.

 

Algorithm-

 

Genetic Algorithm works in the following steps-

 

Step-01:

 

  • Randomly generate a set of possible solutions to a problem.
  • Represent each solution as a fixed length character string.

 

Step-02:

 

Using a fitness function, test each possible solution against the problem to evaluate them.

 

Step-03:

 

  • Keep the best solutions.
  • Use best solutions to generate new possible solutions.

 

Step-04:

 

Repeat the previous two steps until-

  • Either an acceptable solution is found
  • Or until the algorithm has completed its iterations through a given number of cycles / generations.

 

Basic Operators-

 

The basic operators of Genetic Algorithm are-

 

1. Selection (Reproduction)-

 

  • It is the first operator applied on the population.
  • It selects the chromosomes from the population of parents to cross over and produce offspring.
  • It is based on evolution theory of “Survival of the fittest” given by Darwin.

 

There are many techniques for reproduction or selection operator such as-

  • Tournament selection
  • Ranked position selection
  • Steady state selection etc.

 

2. Cross Over-

 

  • Population gets enriched with better individuals after reproduction phase.
  • Then crossover operator is applied to the mating pool to create better strings.
  • Crossover operator makes clones of good strings but does not create new ones.
  • By recombining good individuals, the process is likely to create even better individuals.

 

3. Mutation-

 

  • Mutation is a background operator.
  • Mutation of a bit includes flipping it by changing 0 to 1 and vice-versa.
  • After crossover, the mutation operator subjects the strings to mutation.
  • It facilitates a sudden change in a gene within a chromosome.
  • Thus, it allows the algorithm to see for the solution far away from the current ones.
  • It guarantees that the search algorithm is not trapped on a local optimum.
  • Its purpose is to prevent premature convergence and maintain diversity within the population.

 

Flow Chart-

 

The following flowchart represents how a genetic algorithm works-

 

 

Advantages-

 

Genetic Algorithms offer the following advantages-

 

Point-01:

 

  • Genetic Algorithms are better than conventional AI.
  • This is because they are more robust.

 

Point-02:

 

  • They do not break easily unlike older AI systems.
  • They do not break easily even in the presence of reasonable noise or if the inputs get change slightly.

 

Point-03:

 

While performing search in multi modal state-space or large state-space,

  • Genetic algorithms has significant benefits over other typical search optimization techniques.

 

To gain better understanding about Genetic Algorithm & its Working,

Watch this Video Lecture

 

Get more notes and other study material of Artificial Intelligence.

Watch video lectures by visiting our YouTube channel LearnVidFun.