Reversible state updates have nothing to do with IDA.
The concept is completely orthogonal to choosing which node (next state) to expand next. It's about managing the internal representation of a state.
The concept is completely orthogonal to choosing which node (next state) to expand next. It's about managing the internal representation of a state.
> choosing which node (next state) to expand next
I know this is "heuristic search", a broader class of algorithms which includes A＊ and IDA＊ and many more. But the core selling point of IDA＊ is not the "heuristic search", but its compact linear-space memory usage (thus fast) compared to A＊. So I did not suggested IDA＊ because of its heuristic search aspect.
For an efficient implementation, reversible updates are just natural and common in IDA＊. Below is an excerpt from [1]. I believe this is equivalent to what you call reversible state updates.
* In-place Modification
The main source of remaining overhead in the expansion function is
the copy performed when generating each new successor (line 12 in Figure 1).
Since IDA＊ only considers a single node for expansion at a time, and because
our recursive implementation of depth-first search always backtracks to the
parent before considering the next successor, it is possible to avoid copying entirely.
We will use an optimization called in-place modification where the search
only uses a single state that is modified to generate each successor and
reverted upon backtracking.
By the way, this "local-changes-only" approach crops up in many other places too. In CS and nature, because it's just so damn energy-efficient.
For example, check out this (recent, July 2017) paper:
Gomez, Ren, Urtasun & Grosse: "The Reversible Residual Network: Backpropagation Without Storing Activations", https://arxiv.org/abs/1707.04585.
You can't help but think of the ancient programmer's trick for swapping two variables without a temp storage...
a = a + b;
b = a - b;
a = a - b;