Tag Archives: closed

The A* Algorithm

As a child I remember traveling on road trips, sitting in the back of a car trying to do my best to keep myself busy for what would occupy the next six to ten hours of my life. One of the things I grew to like were the simple maze books that were sold on the magazine racks at some of the gas stations where we’d stop for food. There are two basic strategies I employed for solving these mazes: For simpler mazes, I could generally just take a look at the overall maze structure, decide upon a path through the maze, then write a path without any mistakes. For more complex mazes though, I would generally begin a route that looks the most promising. If that route reaches a point where I can see that it will be impossible to finish, then I’d go back to where the decision was made, exclude the route I had just tried, and select the “most promising” remaining route. I’d continue this process until I had completed the maze, or until it became simple enough for me to solve the maze using only my memory.

The A* Algorithm works in a similar manner to the second approach I just described. We begin at a starting point, and consider where to move next from that starting point. The set of possible options for this next move is determined by the neighbor function for a given cell. For each neighbor the algorithm estimates the length of the route through that cell by calculating the sum of two values, f(n) = g(n) + h(n), where

g(n) is the (known) cost to travel from the starting point to the cell n.
h(n) is the (approximate) cost to travel from the cell n to the final cell.

The sum g(n) + h(n) allows us to approximate the total cost of a route through the cell n.

The A* algorithm begins at the starting position of the maze. There are two sets we will be considering throughout the process of determining the optimal route, called the closedSet and the openSet. The elements of closedSet are the nodes whose total distance from the starting position has been calculated, whereas the elements of openSet represents nodes whose total distance is still under consideration. There is also a map called prev which is used to reconstruct the path. Below is how the algorithm operates:

A* Algorithm Pseudocode
closedSet is the empty set
openSet = {start}
prev is the empty set

While there are still elements in openSet,
     Find the element c* in openSet with the lowest value f(c).
     If c* is the target position
          Reconstruct the path.
     Else If c* is not the target position,
          Remove c* from openSet
          Add c* to closedSet
          For each neighbor n of c* that is not in closedSet,
               Calculate a temporary g value, temp_g(n) = g(c*) + dist(c*, n).
               If n is not in openSet, or if n is in openSet and temp_g(n) < g(n),
                    Set prev(n) = c*
                    Set g(n) = temp_g(n)
                    Set f(n) = g(n) + h(n).
                    if n is not in openSet
                         add n to openSet.
     End If
End While
End Algorithm

An important question becomes what makes a good heuristic function to approximate the distance to the goal. This can lead to an in depth discussion based on the word "good", but the necessary condition for any heuristic is that it NEVER over-estimates the cost of the path from the cell to the goal. Some examples of possible heuristics for mazes are the Euclidean Distance (the square root of the sum of the squares of the horizontal and vertical differences in distances, i.e. dE(x, y) = (i(xi – yi)2) and TaxiCab Distance (the sum of the differences in the horizontal and vertical dimensions, i.e. dT(x, y) = i|xi – yi|). Both of these are feasible metrics for heuristics on a maze. Other herusitics, like h(n) = 0 for all n are possible, but doing this would make the algorithm treat all cells equally and ignore the heuristic part of the A* algorithm, turning it into Dijkstra’s algorithm.

I’ve written a script that generates random mazes and uses the A* algorithm to find the optimal path through this maze. For this script, I used the taxicab distance heuristic.

Check it out and let me know what you think.

Learn About “the Other” Algebra

When I visit family for the holidays, the topic of my being a mathematician always seems to come up, and there’s always a child in the family struggling with maths, and when I ask the subject of their struggles the word “algebra” is always the culprit. I’ll save for another post my ideas on how this subject should be taught in high school and some of the main problems facing students.

I want to concentrate this post on a topic that few outside the mathematical world know about, but which many inside this world (myself included) hold dearly – the topic of modern or abstract algebra. I refer to this as “the other” algebra because a general conversation about the word “algebra” will generally revolve around concepts such as systems of equations, slopes, intercepts, intersection, rise-over-run, point-slope, and other terminology that limits algebra to a specific domain (the set of real or complex numbers) while at the same time ignoring the underlying beauty associated with this area.

I wrote previously about the area of set theory and the beauty associated with taking math out of the scope of a basic number line and into a much more undefined space. Abstract algebra is a continuation of set theory where in addition to our set, we have a (binary) operation defined on any two elements of this set. The inclusion of this binary operation allows us to consider several different structures based on the properties that this binary operation holds.

The structures I’d like to write about today are called groups. A group is a set along with an operation (or function) defined on any two elements of the set with the following properties:
– It is closed. This means that any time we run this function on two elements on the set, the function gives us a member of the set. In mathematical terms, for all a, b in the set A, f(a, b) must also be a member of A.
– There is an identity element. An identity element is defined as an element where is we include it in the binary operator with any other element, the operator will always return the other element. So if the element i is the identity element, then f(i, a) = a and f(a, i) = a for any other a in the set A. Any group must have an identity element.
– Every element has an inverse. Inverse elements are based on the identity element. What the inverse says is that for every element, there is a way to use the binary operator to get to the identity element. So for all elements a in the set A, there is an element b in the set A such that f(a, b) = i, where i is the identity element.
– The binary operator is associative. I described the associative property when I discussed the functions and relations of set theory. A function is associative if the way we group things (aka associate them) doesn’t matter. This means that for any elements a, b, and c of the set A, f(f(a, b), c) must be the same as f(a, f(b, c)).

If these four properties hold for a set A and a binary function f, then we say that the pair (A, f) is a group. We will generally use a common notation such as a · b, or a * b or simply ab to represent f(a, b).

Another important concept in group theory is the idea of a Cayley table. These are similar to multiplication tables that we drew out when we were first learning our “times tables”. For a group with n elements, we form a table with n rows and n columns. Each element of the group is written out to the left of each row and above each column (so really we can think of it as an n+1 by n+1 table with the first row and column being descriptive rows). Each cell of the table is the binary operator applied to the two elements indicated by the row and column (with an understanding of whether we have row before column or vice versa). Obviously, we can only do this for finite groups as we cannot write out all the elements of an infinite set.

The script I’ve added is a tester to allow users to input the information for a possible group (size, name of each element, and a Cayley table) and with this information the user is informed whether or not it forms a group. If it does not form a group, the reasons why it does not form one are also given. There are also some sample groups given to give insight into this area.