A Star: Fundamentals and Applications

By Fouad Sabry

What Is A Star

Because of its completeness, optimality, and optimal efficiency, the A* method, which is employed for graph traversal and path search, is utilized in a variety of subfields within the discipline of computer science. Because it saves all of the created nodes in memory, its space complexity is a significant disadvantage in practical terms. Consequently, in practical travel-routing systems, it is often outperformed by algorithms that can pre-process the graph to achieve higher speed, as well as by approaches that are memory-bounded; despite this, A* is still the best answer in many different scenarios.

How You Will Benefit

(I) Insights, and validations about the following topics:

Chapter 1: A* Search Algorithm

Chapter 2: Graph Theory

Chapter 3: Heuristic in Computer Science

Chapter 4: Best-First Search

Chapter 5: Dijkstra's Algorithm

Chapter 6: Any-Angle Path Planning

Chapter 7: Admissible Heuristic

Chapter 8: Consistent Heuristic

Chapter 9: Memory-Bound Function

Chapter 10: Pathfinding

(II) Answering the public top questions about a star.

(III) Real world examples for the usage of a star in many fields.

(IV) 17 appendices to explain, briefly, 266 emerging technologies in each industry to have 360-degree full understanding of a star' technologies.

Who This Book Is For

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of a star.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: Jun 28, 2023

Book preview

Chapter 1: A* search algorithm

A* is an algorithm for graph traversal and path search, and its name is pronounced A-star., which, due to the fact that it is so comprehensive, is used in a variety of subfields inside computer science, optimality, and utmost operational effectiveness.

One major practical drawback is its O(b^d) space complexity, because it keeps a record of all of the created nodes in memory.

Thus, within the realm of operational travel routing systems, In most cases, it is surpassed by algorithms that are able to pre-process the graph in order to get higher performance, It is possible to think of it as a continuation of Dijkstra's algorithm.

Heuristics are used to direct Asearch, *'s which helps the algorithm attain greater performance.

The A* method, in contrast to Dijkstra's algorithm, only finds the shortest route from a given source to a given goal. It does not discover the shortest-path tree from a given source to all and all potential objectives. Using a heuristic that is aimed toward a certain purpose requires that you make this compromise. Because the whole shortest-path tree is constructed by Dijkstra's method, any node in the tree may be thought of as a goal; hence, there is no specific-goal-directed heuristic that can be used.

A* was developed as a part of the Shakey project, which aimed to produce a mobile robot capable of planning its own activities. A* was one of the robots that came out of that research. The use of the Graph Traverser technique was first suggested by Nils Nilsson.

Because A* is an informed search algorithm, often known as a best-first search, its structure may be described in terms of weighted graphs, as follows: It seeks to locate, beginning from a certain starting node of a graph, a route to the specified target node that incurs the least amount of cost (least distance travelled, shortest time, etc.). It does this by preserving a tree of pathways that originate at the start node and extending those paths one edge at a time until its termination requirement is fulfilled. This continues until the tree is complete.

A* has to make a decision on which of its pathways to expand on each iteration of the main loop. It makes this determination based on the cost of the route itself as well as an estimate of the additional cost necessary to extend the path all the way to the target. To be more specific, A* chooses the route that results in the lowest cost.

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

where n is the next node on the route, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic function that predicts the cost of the cheapest path from n to the objective. g(n) is the cost of the path from the start node to n. A* comes to an end either when the route it chooses to extend is already a path leading from the start to the goal or when there are no more pathways that are qualified to be extended. The heuristic function is tailored to the given issue. If the heuristic function is acceptable, which means that it does not ever underestimate the real cost to reach the objective, A* is guaranteed to produce a route from the starting point to the goal that has the lowest possible cost.

A standard implementation of A* makes use of a priority queue to carry out the repeated selection of nodes with the smallest (estimated) cost at which to grow. The open set, fringe, or frontier is the name often given to this priority queue. At each stage of the method, the queue is advanced by removing the node that has the lowest f(x) value, after which the f and g values of the node's neighbors are adjusted appropriately, and the nodes that were previously neighbors are added to the queue. The process will keep going until a target node is found among the eliminated nodes (that is, the node with the lowest f value among all of the fringe nodes). Since h at the goal in an acceptable heuristic is considered to be zero, the value of that goal's f is likewise considered to be the cost of the shortest route.

Only the length of the route with the fewest steps is returned by the algorithm we have been discussing so far. The method may be readily modified in such a way that every node on the route remembers its predecessor in order to facilitate the process of determining the actual sequence of steps. The last node in the chain will, after this method has been executed, refer to the node that came before it, and so on, until one of the nodes' predecessors is the starting node.

As an example, while looking for the shortest route on a map, h(x) can indicate the distance in a straight line to the destination. This is because the straight-line distance is the physically shortest distance that can exist between any two places. When creating a grid map for a video game, it is best to use either the Manhattan distance or the octile distance depending on the set of moves that are accessible to the player (4-way or 8-way).

If the heuristic h satisfies the additional condition h(x) ≤ d(x, y) + h(y) for every edge (x, y) of the graph (where d denotes the length of that edge), If so, the letter h is said to be monotonous, or consistent.

Using a heuristic that is reliable, A* is guaranteed to identify an optimum route without processing any node more than once, and running A* is identical to running Dijkstra's algorithm with the decreased cost d'(x). A* may be found here, y) = d(x, y) + h(y) − h(x).

The algorithm is described by the pseudocode that is following:

function reconstruct_path(cameFrom, current)

total_path := {current}

while current in cameFrom.Keys:

current := cameFromcurrent

total_path.prepend(current)

return total_path

// A* finds a path from start to goal.

// h is the heuristic function. h(n) estimates the cost to reach goal from node n.

function A_Star(start, goal, h)

// The set of discovered nodes that may need to be (re-)expanded.

// Initially, only the start node is known.

// This is usually implemented as a min-heap or priority queue rather than a hash-set.

openSet := {start}

// For node n, cameFrom[n] is the node immediately preceding it on the cheapest path from the start

// to n currently known.

cameFrom := an empty map

// For node n, gScore[n] is the cost of the cheapest path from start to n currently known.

gScore := map with default value of Infinity

gScorestart := 0

// For node n, fScore[n] := gScore[n] + h(n). fScore[n] represents our current best guess as to

// how cheap a path could be from start to finish if it goes through n.

fScore := map with default value of Infinity

fScorestart := h(start)

while openSet is not empty

// This operation can occur in O(Log(N)) time if openSet is a min-heap or a priority queue

current := the node in openSet having the lowest fScore[] value

if current = goal

return reconstruct_path(cameFrom, current)

openSet.Remove(current)

for each neighbor of current

// d(current,neighbor) is the weight of the edge from current to neighbor

// tentative_gScore is the distance from start to the neighbor through current

tentative_gScore := gScorecurrent + d(current, neighbor)

if tentative_gScore < gScoreneighbor

// This path to neighbor is better than any