simulated annealing is really old, and sounds like a similar effect: http://en.wikipedia.org/wiki/Simulated_annealing

Though explicitly representing back-steps in a search is an interesting idea. It doubles the order of complexity, which will result in the square root of the depth available.