Scribd
Upload
45 views3 pages

Data Structures and Algorithms

A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently directed path between multiple points, called nodes. It enjoys widespread use due to its performance and accuracy.

Uploaded by

zainab
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
Download as docx, pdf, or txt
45 views3 pages

Data Structures and Algorithms

A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently directed path between multiple points, called nodes. It enjoys widespread use due to its performance and accuracy.

Uploaded by

zainab
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
Download as docx, pdf, or txt
Download as docx, pdf, or txt
You are on page 1/ 3

DATA STRUCTURES AND ALGORITHMS

LAB PROJECT REPORT


12 DECEMBER 2017
INTRODUCTION
A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of
plotting an efficiently directed path between multiple points, called nodes. It enjoys widespread use
due to its performance and accuracy. However, in practical travel-routing systems, it is generally
outperformed by algorithms which can pre-process the graph to attain better performance, although
other work has found A* to be superior to other approaches.
OBJECTIVE
The objective of this project is to implement a star algorithm for finding shortest path for a plane to
different geographical areas around the globe .The objective is to implement a code which is both time
efficient and space efficient
DESIGN
GRAPH
In graph there are two things:
1. A finite set of vertices also called as nodes
2.  A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is
not same as (v, u) in case of directed graph(di-graph). The pair of form (u, v) indicates that there
is an edge from vertex u to vertex v. The edges may contain weight/value/cos
An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[].
An entry array[i] represents the linked list of vertices adjacent to the  ith vertex. This representation can
also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists

MINIMUM HEAP
Min heap is implemented by array
Operations on Min Heap:
1) getMini(): It returns the root element of Min Heap. Time Complexity of this operation is O(1).

2) extractMin(): Removes the minimum element from Min Heap. Time Complexity of this Operation is
O(Logn) as this operation needs to maintain the heap property (by calling heapify()) after removing root.

3) decreaseKey(): Decreases value of key. Time complexity of this operation is O(Logn). If the decreases
key value of a node is greater than parent of the node, then we don’t need to do anything. Otherwise,
we need to traverse up to fix the violated heap property.

4) insert(): Inserting a new key takes O(Logn) time. We add a new key at the end of the tree. IF new key
is greater than its parent, then we don’t need to do anything. Otherwise, we need to traverse up to fix
the violated heap property.

5) delete(): Deleting a key also takes O(Logn) time. We replace the key to be deleted with minum infinite
by calling decreaseKey(). After decreaseKey(), the minus infinite value must reach root, so we call
extractMin() to remove key.

A*ALGORITHM

The heuristic used to evaluate distances in A* is:


f(n) = g(n) + h(n)
where g(n) represents the cost (distance) of the path from the starting point to any vertex n, and h(n)
represents the estimated cost from vertex n to the goal.
Euclidean distance (straight line distance) is a common method to used for h(n).
 x2 = coordinate of the destination location
 x1 = coordinate of the source location
 y2 = coordinate of the destination location
 y1 = coordinate of source location
 dx = | x2 - x1 |
 dy = | y2 - y1 |

Distance = sqrt(dx2 + dy2)


There are two sets, OPEN and CLOSED. The OPEN set contains those nodes that are candidates for
examining. Initially, the OPEN set contains just one element: the starting position. The CLOSED set
contains those nodes that have already been examined. Initially, the CLOSED set is empty. Graphically,
the OPEN set is the "frontier" and the CLOSED set is the "interior" of the visited areas. Each node also
keeps a pointer to its parent node so that we can determine how it was found.
There is a main loop that repeatedly pulls out the best node n in OPEN (the node with the lowest f value)
and examines it. If n is the goal, then we're done. Otherwise, node n is removed from OPEN and added to
CLOSED. Then, its neighbors n' are examined. A neighbor that is in CLOSED has already been seen, so
we don't need to look at it. A neighbor that is in OPEN will be examined if its f value becomes the lowest
in OPEN. Otherwise, we add it to OPEN, with its parent set to n. The path cost to n', g(n'), will be set to
g(n) + cost(n, n').

IMPLEMENTATION
The project is implemented by different data structures.Minimum heap is used to find the smallest
distant from the adjacent node.it is implemented by the array.Graphs are used to store the vertices and
the edges it is implemented by the linked list.An input file is also used which contains the source or the
staring positions and destinations the weight are also included in the file and the
APPLICATIONS
A* is commonly used for the common pathfinding problem in applications such as games, but was
originally designed as a general graph traversal algorithm.It finds applications to diverse problems,
including the problem of parsing using stochastic grammars in NLP. Other cases include an
Informational search with online learning.
ISSUES
There were no issues in the project .The minor issues were solved
CONCLUSION
A star algorithm is successfully implemented.A star uses heuristic. This heuristic helps to reach nearer.
Efficiency of this algorithm depends on heuristic function, which can be either complete or optimal. This
algorithm is faster than Dijkstra and more efficient.

You might also like