1
$\begingroup$

I'm reading the paper Enhanced Simplified Memory-bounded A Star (SMA*+). In short, the authors propose a limited-memory version of A* where we cull nodes if we are out of memory, to re-expand them later on.

To do this they choose the worst node to cull. And they propose a heuristic to maximize to choose what is considered the worst node:

For example, a culling heuristic based on the ratio between f-cost and depth, given as $c(n) = f(n) / \ln(d(n) + e)$, where $e$ is Euler’s number, can improve performance on problems with many similar f-costs, if we can reasonably assume that the goal has a high depth.

A quick reminder, $f(n) = g(n) + h(n)$ where $g(n)$ is the cost to reach node $n$ and $h(n)$ is the heuristic to estimate the distance from $n$ to the goal node. $d(n)$ is the depth of the node.

The authors don't further elaborate on this. Is there some logical justification I'm missing for the formula $c(n)$, in particular the natural logarithm and adding $e$ to $d(n)$?

$\endgroup$
1
$\begingroup$

From what I can tell the function $c(n)$ was just chosen as a reasonably simple trade-off between f-cost and depth.

It appears that $e$ is added to simply have the denominator $\ln(d(n) + e)$ always be $\geq 1$ and prevent $\ln(0)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.