我正试图用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
当然,你只需要一个超时,它总是能解决(成功)。