Comparing A* search to Simulated Annealing

Question

Good Afternoon,

I am comparing A* search to Simulated Annealing for an assignment, mainly the algorithms, memory complexity, choice of next actions, and optimality. Now, I am not 100% sure about my answer, and was wondering if someone could give me some input.

A*: Optimal, finds path of shortest distance to goal state based on heuristic.

SA: Complete, stochastic, randomly selects next state and either rejects/accepts based on change in energy state. If it is a bad move (less energy than previous state) then it either accepts/rejects based on probability.

Now, I understand that A* requires bookkeeping in order to track the path from goal state to start state. This is why I think that the memory requirements would be linear, where there are n nodes in the path from start to finish.

On the other hand SA doesn't require bookkeeping, since it's trying to find the state with the maximum "energy". Could someone explain exactly what "energy" would mean? Also, I am confused about comparing the functions of these two algorithms. A* is good at finding the path to a goal state (which is already known) with the lowest cost, whereas SA only finds a state that is most desirable. what is the point of comparing A* to SA when they seem to have two different purposes?

Answer 1

"Energy" is just the output of your cost function that you define for the SA problem. You are right that the two algorithms seem to have two different purposes, and in most cases, I would say that is true. However, you could pose a pathfinding problem as a simulated annealing problem, depending on how you define your cost (energy) function.

Let's say you have a cost function that equals the total cost to get from point A to point B. Your SA algorithm would try to find the minimum in this cost function, but imagine how difficult that may be. Your cost surface could potentially by many-dimensional. Plus, there is no guarantee that your cost surface is smooth, so finding that minimum on this enormous cost surface may be computationally intractable.

I think you've stated well many of the differences, but the next step is to try to understand the benefits/drawbacks of each algorithm solving the problem they are best suited for.