java – 为什么这称为回溯？

发布时间：2020-12-15 02:05:36 所属栏目：Java 来源：网络整理

导读：我在维基百科上读过,也用Google搜索过, 但我无法弄清楚“回溯算法”是什么意思. 我从“破解代码访谈”中看到了这个解决方案并且想知道为什么这是一个回溯算法？解决方法 “回溯”是枚举算法中出现的术语. 您构建了一个“解决方案”(这是一个为每个变量赋值

我在维基百科上读过,也用Google搜索过,

但我无法弄清楚“回溯算法”是什么意思.

我从“破解代码访谈”中看到了这个解决方案

并且想知道为什么这是一个回溯算法？

解决方法

“回溯”是枚举算法中出现的术语.

您构建了一个“解决方案”(这是一个为每个变量赋值的结构).

然而,在构造期间,您可能意识到解决方案不成功(不满足某些约束),然后您回溯：您撤消对变量的某些值赋值,以便重新分配它们.

例：

根据您的示例,您希望在2D网格中构建路径.所以你开始从(0,0)生成路径.例如：

(0,0)
(0,0) (1,0) go right
(0,1) go up
(0,1) (0,1) go left
(0,0) go down
Oops,visiting a cell a second time,this is not a path anymore
Backtrack: remove the last cell from the path
(0,1)
(0,1) (1,1) go right
Oops,this is not a path anymore
Backtrack: remove the last cell from the path
....

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!