iT邦幫忙

2021 iThome 鐵人賽

DAY 27
0
自我挑戰組

每日攝取一點資料結構和演算法系列 第 27

Day27:Backtracking -回溯法

https://ithelp.ithome.com.tw/upload/images/20210927/20128604vWlQfrzeXz.jpg

回溯法是暴力破解法的一種,在列出各種可能的組合時,如果遇到不符合條件的就不再繼續向下查找,而是回到上層繼續尋找其他可能,聽起來有點抽象,可以想像有很多條岔路可以做選擇,不過已經知道有些岔路不會得到我們需要的結果,就沒有必要繼續往下找,而是折返到上個路口,繼續探索其他還沒訪問過的岔路,如同下圖所示
https://ithelp.ithome.com.tw/upload/images/20210927/20128604cwJ2gb2wGV.png

圖片來源:backtracking-introduction

在理解回溯法之前需要先認識permutation排列法

甚麼是permutation排列法?

是將相異物件或符號根據確定的順序重排。每個順序都稱作一個置換或排列。例如,從一到六的數字有720種排列,對應於由這些數字組成的所有不重複亦不闕漏的序列,例如"4, 5, 6, 1, 2, 3" 與1, 3, 5, 2, 4, 6。(引用自wikipedia)

假設現在有個字串ABC,試問會有幾種排列組合? 所有可能的排列組合如下圖,可以推論出公式 = 階乘 
Ex.字串長度為3的話,就會有3*2*1=6種可能

https://ithelp.ithome.com.tw/upload/images/20210927/20128604m2F7ryEqK7.png

用js實作

const arr = ["A", "B", "C"];

const permutation = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            for (let k = 0; k < arr.length; k++) {
                if (i === j || j === k || k === i) {
                    continue;
                }
                console.log(arr[i], arr[j], arr[k]);
            }
        }
    }
};

permutation(arr);
//A B C
//A C B
//B A C
//B C A
//C A B
//C B A

利用三個迴圈列出所有排列組合,假設字串當中任意兩個單字相同,就排除掉該組合,將程式流程畫成圖的話,會發現紫色三角形的範圍其實全部都不符合條件,(非ABC的排列組合)
https://ithelp.ithome.com.tw/upload/images/20210927/201286046KnGvXpQ0t.png

因此在i=0, j=0的時候就要喊停了,回溯到i=0這一個步驟,這個中斷向下查找往回走的動作就是Backtracking
https://ithelp.ithome.com.tw/upload/images/20210927/20128604GoDloYqOAp.png

提早設定中止條件,向上回溯的程式碼如下

const arr = ["A", "B", "C"];
const permutation = (arr) => {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (i === j) {
                continue;
            }
            for (let k = 0; k < arr.length; k++) {
                if (j === k || k === i) {
                    continue;
                }
                console.log(arr[i], arr[j], arr[k]);
            }
        }
    }
};

permutation(arr);

嘗試用雙指針的概念來解這題,利用start與i兩個指針互換位置來取得不同的排列組合,執行的步驟如下

  1. start跟i都從0開始
  • start=0,i=0,獲得以A為開頭的組合,ex. ABC
  1. i前進一格之後與start交換位置
  • start=0,i=1,獲得以B為開頭的組合,ex. BAC
  1. i前進一格之後與start交換位置
  • start=0,i=2,獲得以C為開頭的組合,ex. CBA

當i=2的時候意謂著i指針已經走到最後一步,這時start指針必須前進一步,i指針則退回與start指針相同的位置,依循先前的規則,start和i兩個指針所指向的字母作交換,交換完畢後 i+1

字串ABC

  • start=1,i=1,兩個指針指向同個字母,交換後維持不變,依然是ABC
  • start=1,i=2,兩個指針互換後,獲得ACB

字串BAC

  • start=1,i=1,兩個指針指向同個字母,交換後維持不變,依然是BAC
  • start=1,i=2,兩個指針互換後,獲得BCA

字串CBA

  • start=1,i=1,兩個指針指向同個字母,交換後維持不變,依然是CBA
  • start=1,i=2,兩個指針互換後,獲得CAB

用js實作

let result = [];
const permutation = (arr, start) => {
    if (start >= arr.length) {
        //因為arr最後會被換回原本的字串ABC 需要用淺拷貝的方式複製當下已經交換過的陣列 
        result.push([...arr]);
    } else {
        for (let i = start; i < arr.length; i++) {
            //將start與i作交換
            swap(arr, start, i);
            permutation(arr, start + 1);
            //交換完之後要再換回來才會是原本的字串ABC
            swap(arr, start, i);
        }
    }
};

const swap = (arr, n1, n2) => {
    [arr[n1], arr[n2]] = [arr[n2], arr[n1]];
};

permutation(["A", "B", "C"], 0);
console.log("result", result);

執行結果如下
https://ithelp.ithome.com.tw/upload/images/20210927/201286049yXBce8BKf.png


上一篇
Day26:Dynamic Programming(DP) - 動態規劃(下)
下一篇
Day28:八皇后問題- 8 Queens Puzzle
系列文
每日攝取一點資料結構和演算法30

尚未有邦友留言

立即登入留言