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?