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

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.

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

• 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 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

### 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-

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.