1

我正在尝试在 javascript 中创建回溯算法（带有简单的前向检查）的实时演示。我已经以递归形式对算法进行了优化，但现在我一直在尝试使用 javascript 的setTimeoutor对其进行动画处理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;

}

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

4

2 回答 2

1

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

不，恰恰相反。您的在某些部分仍然是迭代的（for-loop）。

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

就是这样：

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);
    })();
}
于 2013-07-18T12:40:23.353 回答
0

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

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

当然，您只需要一个总是解决（成功）的超时。

于 2013-07-18T11:42:38.710 回答