用javascript制作递归回溯算法的动画

Animating a recursive backtracking algorithm in javascript

本文关键字：回溯算法 动画 递归 javascript      更新时间：2023-09-26

我正试图用javascript创建一个回溯算法的实时演示（带有简单的前向检查）。我已经将算法简化为递归形式，但现在我一直在尝试使用javascript的setTimeout或setInterval来动画化它，我认为这需要我将递归解决方案转换为迭代解决方案。以下是函数（重写为更通用一点）：

function solve(model) {
    if (model.isSolved()) return true;
    var chosen = chooseVariable(model); //could be random or least constrained
    var domain = model.getDomain(chosen);
    var i, assn;
    for (i = 0; i < domain.length; i++) {
        assn = domain[i];
        model.set(chosen, assn);
        if (solve(model)) return true;
        else model.undo();
    }
    return false;
}

正如你所看到的，我这样做是为了让模型可以撤消它自己的操作，而不是有一个单独的操作堆栈或在每个递归级别克隆模型。有没有办法将上面的函数转换为可以与setTimeout或setInterval一起使用的函数？我是否必须大幅更改模型/添加另一个堆栈来跟踪所选变量/尝试的赋值？我需要一个带有可变变量的闭包吗？我主要是在寻找伪代码来指引我正确的方向。

我假设这需要我将递归解决方案转换为迭代解决方案。

不，正好相反。您的在某些部分（for-循环）仍然是迭代的。

您必须使这些步骤异步，这样每个步骤都会有一个回调，该回调在动画完成时触发，您可以继续。由于您希望为每一个迭代步骤设置动画，因此必须使用类似递归的回调-延续传递样式使它们异步。

方法如下：

function solve(model, callback) {
    if (model.isSolved())
        return callback(true);
    var chosen = chooseVariable(model); // could be random or least constrained
    var domain = model.getDomain(chosen);
    var i = 0, assn;
    (function nextStep() {
        if (i < domain.length) {
            assn = domain[i];
            model.set(chosen, assn);
            solve(model, function(solved) {
                if (solved)
                    callback(true);
                else {
                    model.undo();
                    i++;
                    nextStep();
                }
            });
        } else
            callback(false);
    })();
}

现在，您可以通过在需要的地方引入setTimeout（通常在显示model状态之后）来简单地使这个递归变体异步：

function solve(model, callback) {
    if (model.isSolved())
        return callback(true);
    var chosen = chooseVariable(model); // could be random or least constrained
    var domain = model.getDomain(chosen);
    var i = 0, assn;
    (function nextStep() {
        if (i < domain.length) {
            assn = domain[i];
            model.set(chosen, assn);
            solve(model, function(solved) {
                if (solved)
                    callback(true);
                else {
                    model.undo();
                    i++;
                    setTimeout(nextStep, 100);
                }
            });
        } else
            setTimeout(callback, 100, false);
    })();
}

您可以使用例如deferred对其进行异步编程。jQuery提供了延迟的实现，您可以看看这个使用超时的示例：

http://api.jquery.com/deferred.promise/#example-0

当然，你只需要一个超时，它总是能解决（成功）。

相关文章：