Backtracking algorithm

Future_Language · 2023-09-01 22:31:05 · 个人记录

最近很多人都在问我回溯算法的原理是什么（Depth-First-Search）

回溯要涉及到递归，回溯就是在函数套函数的语句下面

void print(int k) {
    if (k == INT_MAX) {
        cout << k;
        return;
    }
    print(k+1);
    a[k] = k;
}

那么这个语句中 a[k] = k 就是一个回溯语句

回溯顾名思义就是到头回过来，所以在递归到最深处的时候，我们的这一层递归会彻底终止返回上一层递归，最上层（栈底）就是调用这个函数时的第一层

但是又有很多人问，循环的dfs是什么意思

其实循环下的 dfs 就是循环个数的 dfs

for (int i = 0; i < 3; i++) {dfs()}
---
dfs()
dfs()
dfs()

其实就是三次 dfs，在第一个 dfs 结束后会返回到当前这一层来执行第二个 dfs，以此类推

我们可以更加直观的了解深搜（回溯算法）

{第一层
  {第二层
     {第三层
       碰到终止条件结束，返回到第二层
     }
     第三层结束执行的语句
  }
  第二层结束执行的语句
}
Accepted