---
title: '核心技巧 - 回朔 & DFS'
disqus: kyleAlien
---
核心技巧 - 回朔 & DFS
===
## OverView of Content
[TOC]
## 回朔 & DFS
DFS 是一種 **概念**，是深度為優先的概念
回朔是實現 DFS 的一種手段
### 回朔 - 概述
* 回朔的重點在於 **==列舉==**，這是不是跟 [**動態規劃**](https://hackmd.io/ty1Hyx-kQ5S3vg30Z6uqpQ?view) 有點像？ 但它 **比動態規劃更簡單，可以當作動態規劃的特例版本**
:::success
- 複習動態規劃，列出 **轉移方程** 需要以下準備
- base case
- 題目狀態
- 每個狀態可做的選擇
- dptable 優化（可選）
> 
:::
### 回朔 - 重點
* 其實回朔就是解決一個 多元樹問題，更精確得來說是一個 **==決策樹的尋訪==**，**複雜度高，Big O(n!)**
> 
:::info
* 經典問題：`全排列`、`N 皇后`，這些問題都是需要 **列舉出全部答案**
:::
* 回朔需要思考三個問題 (要點)
1. **路徑紀錄**：已做出的選擇
2. **選擇清單**：目前還可以做的選
3. **結束條件**：達到底層，無法再做選擇
> 
### DFS & 回朔 - 框架
* 回朔 框架如下：**使用遞歸**，重點有 `路徑紀錄`、`結束條件`、`選擇清單`，其核心在於 **++在遞歸之前做選擇++、++遞歸後移除選擇++**
```java=
// 路徑紀錄
List<路徑> pathRecord = new ArrayList<>();
int backtrack(路徑, 選擇清單) {
if(結束條件) { // 結束條件
return;
}
for(選擇：選擇清單) { // 遍歷選擇清單
if(可選擇列表判斷) { // 已走過路徑不再走
continue;
}
TODO: 做選擇，紀錄到 pathRecord // 做選擇！
backtrack(路徑, 選擇清單); // 更新選擇清單
TODO: 撤銷選擇，從 pathRecord 移除 // 移除選擇！
}
}
```
## 全排列問題
排列組合問題，n 個不重複的全排列共有幾組組合？ `n!` 個
> 5! = 5 * 4 * 3 * 2 * 1
以下全排列問題也不包含重複數字
### [1 , 2 , 3] 全排列
* `[1 , 2 , 3]` 最簡單的就是按照順序：將每種可能繪出，繪出後就會發現它就是一個 **多元樹**，這棵樹又可以稱為回朔演算法的 **==決策樹==**
> 以下框框內是可選擇 (每有可選擇的項目，就是其中一個解答)，路徑則是已選擇
>
> 
:::warning
* 啥是 **決策樹** ?
每個節點 (Tree Node) 都是決策，所以是決策樹
:::
* 前面框架鎖定義的 `backtrace` 函數就像是一個指標，**透過 ==遞迴== (for、while...)** 在多元樹上移走，當走到底層沒有選擇時（結束條件），就是全排列的一個答案
> 
### 樹 - 回朔尋訪
* 其實從 **回朔模組** 來看，它就是一個多元樹的尋訪，而回朔就是在尋訪的過程中，在 `前序`、`後序` 做處理
```java=
// 多元樹模組
public class BaseModule {
private static final class TreeNode {
TreeNode[] children;
int value;
}
public void recursive(TreeNode node) {
for(TreeNode item : children) {
// 前序
recursive(item);
// 後序
}
}
}
```
* 選擇在 `前序`、`後序` 做處理的原因是因為，**要 ++維護節點的屬性++**
- 前序：在進入節點之前進行處理
- 後續：在退出節點時處理
> 
### 全排列 - 遞迴 + 迭代實做
* 這邊我們假設有一組 **不重複** 的數字 Array (這裡使用 `[1 , 2 , 3]`)，要針對它進行排序
1. 紀錄列表：使用 `LinkedList` 紀錄走過得位置
2. 結束條件：`紀錄列表長度` ＝ `提供的 Array`；這代表已走到底端，Array 被消耗完畢
3. 選擇清單：去除當前不可選的選項（從紀錄列表判斷），**在前序時進行選擇、後序時移除選擇**
```java=
public List<List<Integer>> getCompleteRange(int[] array) {
List<List<Integer>> result = new ArrayList<>();
// 協助函數
_getCompleteRange(array, new Stack<>(), result);
return result;
}
private void _getCompleteRange(int[] array,
Stack<Integer> memo, // 紀錄已走過路徑
List<List<Integer>> result) {
// base case 結束遞迴的條件
if(array.length == memo.size()) { // 已走過的路 == 數組長度
// 已全排列完成
List<Integer> tmp = new ArrayList<>(memo);
result.add(tmp);
return;
}
// status choose
// 遍歷 Array 的所有路徑
for(int item : array) {
// 判斷避免重複
if(memo.contains(item)) { // 排除已走過的路徑，判斷（維護）節點的選
continue;
}
// 前序選擇
memo.push(item);
// 修改 memo (條整狀態)，遞迴呼叫
_getCompleteRange(array, memo, result);
// 後續移除選擇
memo.pop();
}
}
```
:::info
這裡使用 **`Stack` 數據結構 紀錄路徑** 來達成 `O(1)` 的效能
:::
* 測試全排列 DFS 回朔
```java=
public static void main(String[] args) {
CompleteRange completeRange = new CompleteRange();
int[] test = {
1, 2, 3
};
List<List<Integer>> result = completeRange.getCompleteRange(test);
for(List<Integer> subResult: result) {
System.out.println(subResult);
}
}
```
> 
<!--
### 全排列 - 全迭代實做
* 除了使用遞迴實作以外，我們也可透使用迭代 (while、for...) 來替代遞迴的功能
-->
### DFS 效能、特性
* DFS 的特性是列舉出所有可能，但 **DFS 無法保證探索路徑的長度 ! (無法找出最短路徑)**
* 回朔的 Big O 時間複雜度，這裡我們可以跟動態規劃比對，**==兩者都是必須列舉==**
| 演算法 | 時間複雜度 | 可否優化 | 優化後的複雜度 |
| -------- | -------- | -------- | - |
| 動態規劃 | O(分支^n^) | 可，使用 dptable、memo，空間換時間 | 解決子結構重疊 O(n) |
| 回朔 | O(n!) | 不可 | - |
:::warning
從這裡我們可以知道，**回朔演算法一般 ++複雜度都很高++**
:::
## N 皇后
:::success
西洋棋的皇后（棋子），可以攻擊同一行、列、左上、左下、右上、右下（就是米字形的攻擊方式）
- 現在要在 N\*N 的棋盤上放置 N 個皇后，並且 **要讓它們不能相互攻擊**，計算全部結果
:::
### N 皇后 - 解法步驟
Rows/Columns 定義
1. **Debug 訊息 ＆ 初始化方法**：以下方法用來 `初始化`、`查看` Java 二維陣列
```java=
// 初始化
private void debugOrInit(Character[][] array, Supplier<Character> supplier) {
for (Character[] characters : array) {
for (int i = 0; i < array.length; i++) {
if(supplier == null) {
System.out.print("[" + characters[i] + "]");
continue;
}
characters[i] = supplier.get();
}
System.out.println();
}
System.out.println("------------------");
}
// debug 方法
private void debug(Character[][] array) {
debugOrInit(array, null);
}
// 複製 棋盤
private Character[][] copy(Character[][] array) {
int size = array.length;
Character[][] result = new Character[size][size];
for (int i = 0; i < array.length; i++) {
System.arraycopy(array[i], 0, result[i], 0, array.length);
}
return result;
}
```
2. **套用回朔（backtrace）框架**：套用框架寫出 N 皇后的程式主幹
* **結束回朔的條件**：判斷 `Row` 是否到達棋盤的尾端，到達尾端就結束 `backtrace` 遞迴
:::info
* 使用遞迴，如同 動態拓展，須思考進入下次的遞迴時 **==可變狀態是誰==**？
> 已當前案例，進入遞迴改變者為 `row`，這樣才能對應到結束條件
:::
* **紀錄路徑**：^1.^ 進入下一個回朔前（前序）加入 `Q` 到棋盤中、^2.^ 結束回朔時（後續）移除 `Q` 的位置改為 `.`（也就是未經過的路）
* **進行選擇**：這邊使用 迭代 `iterate` 棋盤的 `Colume`，並在迭代中進入遞迴傳入 `Row + 1` 來改變狀態
:::info
* N 皇后使用的遞迴概念如下
```java=
// 先 colume
for(int colume = 0; colume < N; colume++) {
// 在每個 colume 條件下，迭代 row
for(int row = 0; row < N; row++) { // 遞歸使用 function 代替
// TODO: 條件判斷
}
}
```
:::
```java=
// N 皇后實做
public LinkedList<Character[][]> backtrace_nQueens(int n) {
// 創建 N 皇后的棋盤 ！
Character[][] board = new Character[n][n];
// 初始化二維陣列
debugOrInit(board, () -> '.');
// debug(board);
// 儲存結果
LinkedList<Character[][]> result = new LinkedList<>();
// 進入回朔方法
backtrace(0, board, result);
return result;
}
private void backtrace(int row,
Character[][] board,
LinkedList<Character[][]> result) {
// 1. 結束回朔（遞迴）的條件
if(row == board.length - 1) {
result.addLast(copy(board));
return;
}
// 2. 進行選擇
for(int col = 0; col < board.length; col++) {
if(!isValid(board, row, col)) { // isValid 等等講
continue;
}
// 放入 Queen
board[row][col] = 'Q';
// 這裡的可變狀態為 row，所以 row + 1 再進入遞迴
backtrace(row + 1, board, result);
board[row][col] = '.';
}
}
```
3. **判斷是否進入遞迴的條件**：在這裡就可以判斷目前的點，是否可以符合 皇后的條件（條件是不可與皇后攻擊的道路相同）
:::info
皇后攻擊的路線是 **米字型**
:::
```java=
// 判斷是否進入遞迴的條件
private boolean isValid(Character[][] board, int row, int col) {
// 1. row 從 0 判斷橫向
for(int i = 0; i < row; i++) {
if(board[i][col] == 'Q') {
return false;
}
}
// 2. 斜方左下判斷
int boardLimit = board.length;
for(int i = row - 1, j = col + 1;
i >= 0 && j < boardLimit; i--, j++) {
if(board[i][j] == 'Q') {
return false;
}
}
// 3. 斜方左上判斷
for(int i = row - 1, j = col - 1;
i >= 0 && j >= 0; i--, j--) {
if(board[i][j] == 'Q') {
return false;
}
}
return true;
}
```
概念圖，可正常加入：則如下 (預想注入點是傳入的 row、col 參數)
> 
概念圖，不可正常加入：如下左上斜方衝突
> 
### 回朔 - 結論
* 回朔演算法就是 **多元樹尋訪**（同動態規劃）
1. 回朔在樹中是使用到 **`前序`、`後序`**
2. 回朔另一個重點是 **維護路徑**，在 `前序` 把路經添加進去，`後序` 把路徑移除
```java=
boolean backtrace(...狀態) {
for(選擇) {
做選擇
backtrace(改變狀態)
移除選擇
}
}
```
* 回朔 & 動態規劃的關係
| 回朔 | 動態規劃 |
| -------- | -------- |
| 結束遞迴條件 | base case |
| 迭代選擇清單 | 選擇 |
| 路徑紀錄 | 改變狀態 |
## Appendix & FAQ
:::info
:::
###### tags: `資料結構`
Sign in with Wallet
Connect another wallet