回溯算法 - 簡書

1.基本概念

回溯算法實(shí)際上一個(gè)類似枚舉的搜索嘗試過程昙啄，主要是在搜索嘗試過程中尋找問題的解穆役，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)，就“回溯”返回梳凛，嘗試別的路徑耿币。
回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索韧拒，以達(dá)到目標(biāo)淹接。但當(dāng)探索到某一步時(shí)十性，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇塑悼，這種走不通就退回再走的技術(shù)為回溯法劲适，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。
許多復(fù)雜的拢肆，規(guī)模較大的問題都可以使用回溯法减响，有“通用解題方法”的美稱。

2.基本思想

在包含問題的所有解的解空間樹中郭怪，按照有限搜索的策略支示，從根節(jié)點(diǎn)出發(fā)深度探索解空間樹。當(dāng)探索到某一接點(diǎn)時(shí)鄙才，要先判斷該結(jié)點(diǎn)是否包含問題的解颂鸿，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索攒庵，如果該結(jié)點(diǎn)不包含問題的解嘴纺，則逐層想其祖先結(jié)點(diǎn)回溯。（回溯法就是對(duì)隱式的深度優(yōu)先搜索算法）
若用回溯法求解問題的所有解時(shí)浓冒，要回溯到根栽渴，且根節(jié)點(diǎn)的所有可行的子樹都已經(jīng)被所有遍才結(jié)束。而使用回溯法求解任一個(gè)解時(shí)稳懒，只要搜索到問題的一個(gè)解就可以結(jié)束闲擦。

3.解空間的樹結(jié)構(gòu)

使用回溯法的解空間一般有兩種解空間：子集樹和排列樹

3.1子集樹

當(dāng)所給的問題從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹场梆。常用于0-1問題墅冷，如0-1背包問題。

如下圖:

image.png

3.2排列樹

當(dāng)所給的問題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)或油，相應(yīng)的解空間樹稱之為排列樹寞忿。排序樹通常有n！葉結(jié)點(diǎn)顶岸。

如下圖:

image.png

4.用回溯法解題的一般步驟

針對(duì)所給問題腔彰，確定問題的解空間：
首先明確定義問題的解空間，問題的解空間應(yīng)該至少包含問題的一個(gè)解
確定結(jié)點(diǎn)擴(kuò)展搜索規(guī)則
以深度優(yōu)先方式搜索解空間辖佣，并在搜索過程中用剪枝函數(shù)避免無效搜索

5.算法框架

1.問題框架

  設(shè)問題的解是一個(gè)n維向量(a1,a2,………,an),約束條件是ai(i=1,2,3,…..,n)之間滿足某種條件萍桌，記為f(ai)。

2.遞歸回溯框架

回溯法是對(duì)解空間的深度優(yōu)先搜索凌简，在一般情況下使用遞歸函數(shù)來實(shí)現(xiàn)回溯法比較簡單，其中i為搜索的深度恃逻，框架如下：

void backtrack (int t) //t表示遞歸深度
{
       if (t>n) output(x); //n表示深度界限
       else
         for (int i=f(n,t);i<=g(n,t);i++) // f(n,t)雏搂，g(n,t)分別表示當(dāng)前擴(kuò)展結(jié)點(diǎn)未搜索過的子樹的起始編號(hào)和終止編號(hào)
           {
           x[t]=h(i); 
           if (constraint(t)&&bound(t)) //滿足約束函數(shù)和限界函數(shù)
              backtrack(t+1);
           }
}

3.非遞歸的算法框架

void iterativeBacktrack ()
{
  int t=1;
  while (t>0) {
    if (f(n,t)<=g(n,t)) 
      for (int i=f(n,t);i<=g(n,t);i++) {
        x[t]=h(i);
        if (constraint(t)&&bound(t)) {
          if (solution(t)) output(x);
          else t++;}
        }
    else t--;
    }
}

6.舉個(gè)例子

現(xiàn)在舉個(gè)例子藕施，給定一組數(shù)組nums，再給定一個(gè)目標(biāo)值target,找出集合nums的所有子集使其之和剛好為目標(biāo)值凸郑，nums中的數(shù)只能使用一次裳食。

例如：給定數(shù)組nums = {1,2,3,4,5},給定目標(biāo)值target = 9,那么所能得到的結(jié)果有:

[0, 1, 1, 1, 0]
[0, 0, 0, 1, 1]

也即是：2+3+4和4+5

現(xiàn)在我們來考慮一下如何求解這個(gè)題，要找出所有子集芙沥，這顯然有點(diǎn)“窮舉搜索”的感覺诲祸，回溯就是這樣一種“搜索”算法。

那么按照回溯步驟：

6.1 確定問題的解空間

用0/1表示是否是用集合中某個(gè)元素而昨，那么對(duì)于整個(gè)集合救氯，我們可以定義一個(gè)數(shù)組x,x[i]=0，則表示不使用第i個(gè)元素歌憨；x[i]=1着憨，表示是用該元素。這樣就將問題轉(zhuǎn)化問了經(jīng)典的0-1問題务嫡，而二叉樹天然具有這樣的性質(zhì)（左子樹對(duì)應(yīng)1甲抖，右子樹對(duì)應(yīng)0，當(dāng)然也可以反過來定義）心铃。構(gòu)造出的解空間樹如上文中的子集樹准谚。這里就不贅述了。

6.2 確定結(jié)點(diǎn)擴(kuò)展搜索規(guī)則

這個(gè)沒什么好說的去扣，大多數(shù)回溯問題均使用深度遍歷柱衔。

6.3 進(jìn)行搜索，必要時(shí)加入剪枝函數(shù)

什么是剪枝函數(shù)厅篓？其實(shí)這是一個(gè)很形象的名詞秀存，在上文中我們構(gòu)造了一個(gè)解空間樹，那么這顆樹就有很多分支羽氮。在搜索過程中或链，我們可以將一些明顯不可能產(chǎn)生解的分支給去掉，降低搜索次數(shù)档押。如果我們不使用剪枝函數(shù)澳盐，那么就會(huì)全部進(jìn)行遍歷，這往往不是我們想要的令宿。

首先貼上不加剪枝函數(shù)的代碼：

import java.util.Arrays;

public class Main {

    /**
     * 回溯法
     *
     */
    static int[] nums = {1,2,3,4,5};
    static int target = 9;
    static int n = nums.length;
    static int[] currentX = new int[n];
    public static void main(String[] args) {
        backTrack(0);
    }

    static int iter = 0;
    static void backTrack(int i ) {
        if(i == n) {
            //結(jié)束
            return;
        }
        //求和
        int currentSum = sum(currentX);
        if(currentSum+nums[i] < target) {
            //滿足約束條件
            currentX[i] = 1;
            backTrack(i+1);
        }else if(currentSum+nums[i]  == target) {
            //滿足約束條件
            currentX[i] = 1;
            System.out.println(Arrays.toString(currentX));
            return;
        }
        //準(zhǔn)備進(jìn)入右子樹叼耙，不一定能進(jìn)入
        currentX[i] = 0;
        //不滿足約束條件,加入剪枝函數(shù)，減低遍歷次數(shù)
        //設(shè)計(jì)規(guī)則：當(dāng)前和只加上右子樹的最大值都無法達(dá)到target粒没，則不用進(jìn)入右子樹
       // if(currentSum + bound(i+1) >= target) {
            System.out.println(++iter);
            backTrack(i+1);
        //}

    }
    static int bound(int i) {
        int sum = 0;
        for(;i<n;i++) {
            sum+=nums[i];
        }
        return sum;
    }
    static int sum(int[] x) {
        int sum = 0;
        for (int i = 0; i < x.length; i++) {
            if(x[i] == 1) {
                sum+=nums[i];
            }
        }
        return sum;
    }

}

這里我將代碼中的剪枝函數(shù)注釋掉了筛婉，下面是運(yùn)行結(jié)果:

1
2
3
4
5
6
7
8
9
[1, 0, 1, 0, 1]
10
11
12
13
[0, 1, 1, 1, 0]
14
15
16
17
18
19
20
21
[0, 0, 0, 1, 1]
22
23

進(jìn)入右子樹23次，一共有三個(gè)解癞松。

現(xiàn)在我們將注釋刪掉爽撒，運(yùn)行結(jié)果如下：

1
2
3
4
[1, 0, 1, 0, 1]
5
6
7
[0, 1, 1, 1, 0]
8
9
10
11
[0, 0, 0, 1, 1]

可以看到入蛆，進(jìn)入右子樹的次數(shù)只有11次了，也就是加入剪枝函數(shù)后硕勿，我們的搜索次數(shù)減少了12次哨毁。顯然這是很可觀。

7.最后

回溯法的介紹大概就這么多了源武，回溯法能夠找到所有滿足約束條件的解扼褪，還有一種常用求解優(yōu)化問題的算法-分支限界法，用來求解滿足約束條件的一個(gè)解粱栖。