jidao-chap16+回溯算法設(shè)計(jì)

1、 jidao-chap16+回溯算法設(shè)計(jì)116.2 回溯算法設(shè)計(jì)回溯算法設(shè)計(jì)計(jì)算機(jī)導(dǎo)論與程序設(shè)計(jì)基礎(chǔ)計(jì)算機(jī)導(dǎo)論與程序設(shè)計(jì)基礎(chǔ) jidao-chap16+回溯算法設(shè)計(jì)2一一. 回溯算法的含義回溯算法的含義二二. 用回溯算法解決問題的一般步驟用回溯算法解決問題的一般步驟三三. 回溯法解題思路應(yīng)用遞歸函數(shù)求解回溯法解題思路應(yīng)用遞歸函數(shù)求解提綱提綱 jidao-chap16+回溯算法設(shè)計(jì)3一一. 回溯算法的含義回溯算法的含義 以組合問題為例：找出從自然數(shù)以組合問題為例：找出從自然數(shù)1、2、n中中任取任取r個(gè)數(shù)的所有組合個(gè)數(shù)的所有組合(要求要求r個(gè)數(shù)從小到大排列個(gè)數(shù)從小到大排列)。例如例如n=5，r=3

2、的所有組合為：的所有組合為：（1）1，2，3（2） 1，2，4（3）1，2，5 (4） 1，3，4（5）1，3，5（6） 1，4，5（7）2，3，4（8） 2，3，5（9）2，4，5 (10） 3，4，5一一. 回溯算法的含義回溯算法的含義 jidao-chap16+回溯算法設(shè)計(jì)4一一. 回溯算法的含義回溯算法的含義求求n=5，r=3的所有組合的所有組合 算法算法1：使用前面學(xué)的窮舉算法：使用前面學(xué)的窮舉算法 羅列出羅列出3個(gè)數(shù)字剔重之后的個(gè)數(shù)字剔重之后的54360種候種候選解。選解。 利用限制條件（利用限制條件（r個(gè)數(shù)從小到大排列）來剔個(gè)數(shù)從小到大排列）來剔除不符合要求的解。除不符合要求的解

3、。 算法評(píng)價(jià)：計(jì)算量大，可能候選解中只有一算法評(píng)價(jià)：計(jì)算量大，可能候選解中只有一小部分解是符合要求的解。小部分解是符合要求的解。 jidao-chap16+回溯算法設(shè)計(jì)5一一. 回溯算法的含義回溯算法的含義求求n=5，r=3的所有組合的所有組合 算法算法2：使用回溯算法：使用回溯算法 回溯算法也叫試探法，它回溯算法也叫試探法，它是一種系統(tǒng)地搜索問題的是一種系統(tǒng)地搜索問題的解的方法。解的方法。 回溯算法的基本思想是：回溯算法的基本思想是：在搜索問題的解時(shí)，從一在搜索問題的解時(shí)，從一條路往前走，能進(jìn)則進(jìn)，條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退（回溯）回來，不能進(jìn)則退（回溯）回來，換一條路再試。換一條路再

4、試。迷宮迷宮展示一下使用回溯法如何求排列的問題 jidao-chap16+回溯算法設(shè)計(jì)6一一. 回溯算法的含義回溯算法的含義二二. 用回溯算法解決問題的一般步驟用回溯算法解決問題的一般步驟三三. 回溯法解題思路應(yīng)用遞歸函數(shù)求解回溯法解題思路應(yīng)用遞歸函數(shù)求解提綱提綱 jidao-chap16+回溯算法設(shè)計(jì)7二二. 用回溯算法解決問題的一般步驟用回溯算法解決問題的一般步驟二二. 用回溯算法解決問題的一般步驟：用回溯算法解決問題的一般步驟： 針對(duì)所給問題，定義問題的解空間，它至少針對(duì)所給問題，定義問題的解空間，它至少包含問題的一個(gè)（最優(yōu)）解。包含問題的一個(gè)（最優(yōu)）解。 確定易于搜索的解空間結(jié)構(gòu)確定易

5、于搜索的解空間結(jié)構(gòu),使得能用回溯法使得能用回溯法方便地搜索整個(gè)解空間方便地搜索整個(gè)解空間 。 以深度優(yōu)先的方式搜索解空間，并且在搜索以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索。過程中用剪枝函數(shù)避免無效搜索。 問題的解空間通常是在搜索問題解的過程中動(dòng)態(tài)問題的解空間通常是在搜索問題解的過程中動(dòng)態(tài)產(chǎn)生的，這是回溯算法的一個(gè)重要特性。產(chǎn)生的，這是回溯算法的一個(gè)重要特性。 jidao-chap16+回溯算法設(shè)計(jì)8 第第1步步. 例：求例：求n=5，r=3的所有組合的所有組合二二. 用回溯算法解決問題的一般步驟用回溯算法解決問題的一般步驟 解空間中共有解空間中共有54360種可能的

6、解，其中符合要求種可能的解，其中符合要求的解為（列舉法）：的解為（列舉法）： (1,2,3)，(1,2,4)，(1,2,5)，(1,3,4)，(1,3,5)， (1,4,5)，(2,3,4)，(2,3,5)，(2,4,5)，(3,4,5) 符合要求的解為（描述法）：符合要求的解為（描述法）： E=（x1，x2，x3） xiS ， 1 i3 ， 且且x1x2x3 其中：其中：S=1，2，3，4，5 jidao-chap16+回溯算法設(shè)計(jì)9 第第1步步. 可用回溯法求解的問題可用回溯法求解的問題P， 下述集合下述集合E中的中的n元元組組成了問題組組成了問題P的解空間：的解空間： 其中其中Si是是x

7、i的定義域，且的定義域，且 Si中元素個(gè)數(shù)中元素個(gè)數(shù) 有限。有限。 問題問題P的解：的解：E中所有中所有 二二. 用回溯算法解決問題的一般步驟用回溯算法解決問題的一般步驟 jidao-chap16+回溯算法設(shè)計(jì)10二二. 用回溯算法解決問題的一般步驟用回溯算法解決問題的一般步驟第第2步步.確定易于搜索的解空間結(jié)構(gòu)。確定易于搜索的解空間結(jié)構(gòu)。通?？梢詫⒔饪臻g組織成一棵樹，使得能用回溯法方通?？梢詫⒔饪臻g組織成一棵樹，使得能用回溯法方便地搜索整個(gè)解空間便地搜索整個(gè)解空間 。 問題的解：問題的解： (1,2,3)，(1,2,4)，(1,2,5)，(1,3,4)，(1,3,5)， (1,4,5)，(2

8、,3,4)，(2,3,5)，(2,4,5)，(3,4,5) x1x2x3 1235435445115122根結(jié)點(diǎn)根結(jié)點(diǎn)34545131415161718519320 2445232254 215525 jidao-chap16+回溯算法設(shè)計(jì)11二二. 用回溯算法解決問題的一般步驟用回溯算法解決問題的一般步驟第第3步步.以深度優(yōu)先的方式搜索解空間以深度優(yōu)先的方式搜索解空間回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方溯法就從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。這個(gè)開始結(jié)點(diǎn)就成為一個(gè)活結(jié)

9、點(diǎn)，式搜索整個(gè)解空間。這個(gè)開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)

10、展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，點(diǎn)?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止。直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止。 jidao-chap16+回溯算法設(shè)計(jì)12 從根結(jié)點(diǎn)移至結(jié)點(diǎn)從根結(jié)點(diǎn)移至結(jié)點(diǎn)1，此時(shí)，此時(shí)x11 移至結(jié)點(diǎn)移至結(jié)點(diǎn)2，此時(shí)，此時(shí)x22n移至結(jié)點(diǎn)移至結(jié)點(diǎn)3，由于結(jié)點(diǎn)，由于結(jié)點(diǎn)3是是葉子結(jié)點(diǎn)，故得到一個(gè)解葉子結(jié)點(diǎn)，故得到一個(gè)解 (1,2,3)。n由于結(jié)點(diǎn)由于結(jié)點(diǎn)3不能向縱深擴(kuò)展，故是死結(jié)點(diǎn)，故回溯至不能向縱深擴(kuò)展，故是死結(jié)點(diǎn)，故回溯至結(jié)點(diǎn)結(jié)點(diǎn)2n從結(jié)點(diǎn)從結(jié)點(diǎn)2移至結(jié)點(diǎn)移至結(jié)點(diǎn)4，由于結(jié)點(diǎn)，由于結(jié)點(diǎn)4是

11、葉子結(jié)點(diǎn)，故得到是葉子結(jié)點(diǎn)，故得到一個(gè)解一個(gè)解 (1,2,4）n由于結(jié)點(diǎn)由于結(jié)點(diǎn)4是死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)是死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)2n從結(jié)點(diǎn)從結(jié)點(diǎn)2移至結(jié)點(diǎn)移至結(jié)點(diǎn)5，由于結(jié)點(diǎn)，由于結(jié)點(diǎn)5是葉子結(jié)點(diǎn)，故得到是葉子結(jié)點(diǎn)，故得到一個(gè)解一個(gè)解 (1,2,5）n由于結(jié)點(diǎn)由于結(jié)點(diǎn)5是死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)是死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)2。由于結(jié)點(diǎn)。由于結(jié)點(diǎn)2不能不能再向縱深擴(kuò)展，故成為死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)再向縱深擴(kuò)展，故成為死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)1搜索問題解，建立解空間搜索問題解，建立解空間1x1x2x3 12354 jidao-chap16+回溯算法設(shè)計(jì)13 回溯至結(jié)點(diǎn)回溯至結(jié)點(diǎn)1 從結(jié)點(diǎn)從結(jié)點(diǎn)1移至結(jié)點(diǎn)移至結(jié)點(diǎn)6，此時(shí)，此時(shí)x

12、23n移至結(jié)點(diǎn)移至結(jié)點(diǎn)7，由于結(jié)點(diǎn)，由于結(jié)點(diǎn)7是是葉子結(jié)點(diǎn)，故得到一個(gè)解葉子結(jié)點(diǎn)，故得到一個(gè)解 (1,3,4)。n由于結(jié)點(diǎn)由于結(jié)點(diǎn)7是死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)是死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)6n從結(jié)點(diǎn)從結(jié)點(diǎn)6移至結(jié)點(diǎn)移至結(jié)點(diǎn)8，由于結(jié)點(diǎn)，由于結(jié)點(diǎn)8是葉子結(jié)點(diǎn)，故得到是葉子結(jié)點(diǎn)，故得到一個(gè)解一個(gè)解 (1,3,5）n由于結(jié)點(diǎn)由于結(jié)點(diǎn)8是死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)是死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)6。由于結(jié)點(diǎn)。由于結(jié)點(diǎn)6不能不能再向縱深擴(kuò)展，故成為死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)再向縱深擴(kuò)展，故成為死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)1 從結(jié)點(diǎn)從結(jié)點(diǎn)1移至結(jié)點(diǎn)移至結(jié)點(diǎn)9，此時(shí)，此時(shí)x24n移至結(jié)點(diǎn)移至結(jié)點(diǎn)10，得到一個(gè)解，得到一個(gè)解 (1,4,5)。n由于結(jié)點(diǎn)由于結(jié)點(diǎn)1

13、0是死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)是死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)9。由于結(jié)點(diǎn)。由于結(jié)點(diǎn)9不不能再向縱深擴(kuò)展，故成為死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)能再向縱深擴(kuò)展，故成為死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)1搜索問題解，建立解空間搜索問題解，建立解空間2x1x2x3 1235435445 jidao-chap16+回溯算法設(shè)計(jì)14 回溯至結(jié)點(diǎn)回溯至結(jié)點(diǎn)1 從結(jié)點(diǎn)從結(jié)點(diǎn)1移至結(jié)點(diǎn)移至結(jié)點(diǎn)11，此時(shí)，此時(shí)x25n由于結(jié)點(diǎn)由于結(jié)點(diǎn)11不能再向縱深不能再向縱深擴(kuò)展，故成為死結(jié)點(diǎn)，回?cái)U(kuò)展，故成為死結(jié)點(diǎn)，回溯至結(jié)點(diǎn)溯至結(jié)點(diǎn)1n由于結(jié)點(diǎn)由于結(jié)點(diǎn)1不能再向縱深擴(kuò)不能再向縱深擴(kuò)展，故成為死結(jié)點(diǎn)，回溯展，故成為死結(jié)點(diǎn)，回溯至根結(jié)點(diǎn)至根結(jié)點(diǎn)n從根結(jié)點(diǎn)移至結(jié)點(diǎn)從根結(jié)點(diǎn)移至

14、結(jié)點(diǎn)12。搜索問題解，建立解空間搜索問題解，建立解空間3x1x2x3 1235435445115122根結(jié)點(diǎn)根結(jié)點(diǎn) jidao-chap16+回溯算法設(shè)計(jì)15搜索問題解，建立解空間搜索問題解，建立解空間4x1x2x3 1235435445115122根結(jié)點(diǎn)根結(jié)點(diǎn)34545131415161718519320 2445232254 215255 jidao-chap16+回溯算法設(shè)計(jì)16一一. 回溯算法的含義回溯算法的含義二二. 用回溯算法解決問題的一般步驟用回溯算法解決問題的一般步驟三三. 回溯法解題思路應(yīng)用遞歸函數(shù)求解回溯法解題思路應(yīng)用遞歸函數(shù)求解提綱提綱 jidao-chap16+回溯算法

15、設(shè)計(jì)17三三. 回溯法解題思路回溯法解題思路 就是求所有滿足條件就是求所有滿足條件D的的n元組元組(x ，x ，, x) 為求為求n元組元組(x ，x ，, x) ，可以先求出，可以先求出x ，然后，然后再求再求n-1元組元組( x ，, x）。這樣，求）。這樣，求(x ，x ，, x)的問題被轉(zhuǎn)化為規(guī)模小一級(jí)但同性質(zhì)的求的問題被轉(zhuǎn)化為規(guī)模小一級(jí)但同性質(zhì)的求( x ，, x)的問題。的問題。 同理，求同理，求( x ，, x)的問題可以轉(zhuǎn)化為求的問題可以轉(zhuǎn)化為求 ( x3，, x)的問題，如此不斷轉(zhuǎn)化，問題規(guī)模不的問題，如此不斷轉(zhuǎn)化，問題規(guī)模不斷減小。斷減小。 當(dāng)被轉(zhuǎn)化為求一元組當(dāng)被轉(zhuǎn)化為求一

16、元組(x)時(shí)，可以直接給出結(jié)果，時(shí)，可以直接給出結(jié)果，而不需要繼續(xù)轉(zhuǎn)化而不需要繼續(xù)轉(zhuǎn)化 。 這就是遞歸算法實(shí)現(xiàn)回溯法的思想。這就是遞歸算法實(shí)現(xiàn)回溯法的思想。三三. 回溯法解題思路回溯法解題思路 jidao-chap16+回溯算法設(shè)計(jì)18例例1. 求求n=5，r=3的所有組合。的所有組合。 問題分析：求組合其實(shí)就是求滿足條件的問題分析：求組合其實(shí)就是求滿足條件的3元元組組( x1,x2, x3)?？梢??？梢栽O(shè)計(jì)遞歸函數(shù)進(jìn)行求解元設(shè)計(jì)遞歸函數(shù)進(jìn)行求解元組組( xi, xn) 。 遞歸函數(shù)參數(shù)設(shè)計(jì)考慮：遞歸函數(shù)參數(shù)設(shè)計(jì)考慮： i肯定是作為一個(gè)參數(shù)，那么肯定是作為一個(gè)參數(shù)，那么n是作為參數(shù)還是作為參數(shù)

17、還是其他采用方式（如全局變量、常量）？是其他采用方式（如全局變量、常量）？ xi的取值范圍是遞歸函數(shù)必須要獲得的。的取值范圍是遞歸函數(shù)必須要獲得的。 求得的元組采用什么數(shù)據(jù)結(jié)構(gòu)存放？采用全求得的元組采用什么數(shù)據(jù)結(jié)構(gòu)存放？采用全局變量還是使用參數(shù)？局變量還是使用參數(shù)？三三.回溯法解題思路應(yīng)用遞歸函數(shù)求解回溯法解題思路應(yīng)用遞歸函數(shù)求解 jidao-chap16+回溯算法設(shè)計(jì)19遞歸函數(shù)設(shè)計(jì)：求元組遞歸函數(shù)設(shè)計(jì)：求元組( x，, x ) void try(int i,int n,int min,int max,int result,int size)參數(shù)說明：參數(shù)說明：i和和n：表示遞歸函數(shù)求元組：

18、表示遞歸函數(shù)求元組( x，, x ) min和和max：min x max result：存放元組：存放元組 size：result的長度的長度三三.回溯法解題思路應(yīng)用遞歸函數(shù)求解回溯法解題思路應(yīng)用遞歸函數(shù)求解 jidao-chap16+回溯算法設(shè)計(jì)20三三.回溯法解題思路應(yīng)用遞歸函數(shù)求解回溯法解題思路應(yīng)用遞歸函數(shù)求解 jidao-chap16+回溯算法設(shè)計(jì)21void try(int i,int n,int min,int max,int result,int size) int xi,j; for(xi=min; xi=max; xi+)/依次試探依次試探xi resulti=xi; /確

19、定確定xi if (i=n) /若本次是求一元組，則遞歸結(jié)束，輸出結(jié)果若本次是求一元組，則遞歸結(jié)束，輸出結(jié)果 for(j=1;j=size-1;j+) printf(%-5d,resultj); printf(n); else try(i+1,n,xi+1,max,result,size); /繼續(xù)求解繼續(xù)求解(xi+1, x ) resulti=0;/清空清空xi 組合問題遞歸函數(shù)組合問題遞歸函數(shù) jidao-chap16+回溯算法設(shè)計(jì)22組合問題主函數(shù)組合問題主函數(shù)#include#define N 3main() int resultN+1=0;/*記錄一個(gè)記錄一個(gè)N元組元組,ai記錄記

20、錄xi*/ try(1,3,1,5,result,N+1); /*調(diào)用遞歸函數(shù)求調(diào)用遞歸函數(shù)求3元組元組*/ system(pause); return 0; jidao-chap16+回溯算法設(shè)計(jì)23例例2. 跳馬問題跳馬問題 有一塊有一塊n*n的格子的棋盤，一位騎士放在初始的格子的棋盤，一位騎士放在初始坐標(biāo)為坐標(biāo)為的格子里的格子里, 并按照象棋的移動(dòng)規(guī)并按照象棋的移動(dòng)規(guī)則移動(dòng)。提出的問題是：是否可以找到可以走則移動(dòng)。提出的問題是：是否可以找到可以走遍整個(gè)棋盤的方案。即經(jīng)過一個(gè)遍整個(gè)棋盤的方案。即經(jīng)過一個(gè)n*n-1次移動(dòng)次移動(dòng)的巡游，使得棋盤上每一個(gè)格子恰好被訪問一的巡游，使得棋盤上每一個(gè)格

21、子恰好被訪問一次。輸出各方案及總方案數(shù)。次。輸出各方案及總方案數(shù)。三三.回溯法解題思路應(yīng)用遞歸函數(shù)求解回溯法解題思路應(yīng)用遞歸函數(shù)求解 jidao-chap16+回溯算法設(shè)計(jì)24(x-2,y-1)(x-2,y+1)(x-1,y-2)(x-1,y+2)(x,y)(x+1,y-2)(x+1,y+2)(x+2,y-1)(x+2,y+1)從從(x,y)出發(fā)，下一步可以走的八種選擇：出發(fā)，下一步可以走的八種選擇：三三.回溯法解題思路應(yīng)用遞歸函數(shù)求解回溯法解題思路應(yīng)用遞歸函數(shù)求解 jidao-chap16+回溯算法設(shè)計(jì)25第第1步：定義解空間步：定義解空間 假設(shè)是假設(shè)是55的棋盤的棋盤,則本題實(shí)際就是求解由

22、則本題實(shí)際就是求解由25元元組組成的狀態(tài)空間組組成的狀態(tài)空間E。 E=（x1，x2，,x25） xiS ， 25 其中：其中：S是棋盤上的是棋盤上的25個(gè)坐標(biāo)個(gè)坐標(biāo)組成的集合組成的集合 約束集約束集D為：為：x1x25互不相等互不相等三三.回溯法解題思路應(yīng)用遞歸函數(shù)求解回溯法解題思路應(yīng)用遞歸函數(shù)求解 jidao-chap16+回溯算法設(shè)計(jì)26三三.回溯法解題思路應(yīng)用遞歸函數(shù)求解回溯法解題思路應(yīng)用遞歸函數(shù)求解第第2步步. 采用一棵樹描述解空間，樹的深度為采用一棵樹描述解空間，樹的深度為25。第第3步步. 動(dòng)態(tài)搜索并建立解空間。動(dòng)態(tài)搜索并建立解空間。共共25個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) jidao-chap16+

23、回溯算法設(shè)計(jì)27解題思路：解題思路：1）旗盤路線：用一個(gè)全局二維數(shù)組存儲(chǔ)）旗盤路線：用一個(gè)全局二維數(shù)組存儲(chǔ) int boardSIZESIZE; /SIZE表示棋盤的行和列數(shù)表示棋盤的行和列數(shù)三三. 回溯法解題思路回溯法解題思路1 16 21 10 2520 11 24 15 2217 2 19 6 912 7 4 23 143 18 13 8 5表示第表示第22步走步走到此位置到此位置 jidao-chap16+回溯算法設(shè)計(jì)28三三. 回溯法解題思路回溯法解題思路2）遞歸函數(shù)設(shè)計(jì)：用于求元組）遞歸函數(shù)設(shè)計(jì)：用于求元組(xixn )。 由于必須在由于必須在xi-1基礎(chǔ)上根據(jù)移動(dòng)規(guī)則確定基礎(chǔ)上根

24、據(jù)移動(dòng)規(guī)則確定xi，因，因 此需要將此需要將xi的坐標(biāo)的坐標(biāo)作為參數(shù)傳入。作為參數(shù)傳入。 void try(int i,int n,int x,int y) jidao-chap16+回溯算法設(shè)計(jì)29三三. 回溯法解題思路回溯法解題思路 jidao-chap16+回溯算法設(shè)計(jì)303）如何在）如何在xi-1坐標(biāo)坐標(biāo) 基礎(chǔ)上確定基礎(chǔ)上確定xi的各個(gè)可能坐標(biāo)的各個(gè)可能坐標(biāo)： int row8=1,2,2,1,-1,-2,-2,-1;/*8個(gè)方向上的個(gè)方向上的x增量增量*/ int col8=-2,-1,1,2,2,1,-1,-2; /*8個(gè)方向上的個(gè)方向上的y增量增量*/ for(dir=0;dir

25、=7;dir+) /*依次試遍依次試遍8個(gè)方向個(gè)方向*/ u=x+rowdir; /*得到的新坐標(biāo)得到的新坐標(biāo)*/ v=y+coldir; 4）遞歸結(jié)束條件：）遞歸結(jié)束條件： 第第i步有位置可走且步有位置可走且i等于等于25三三. 回溯法解題思路回溯法解題思路 jidao-chap16+回溯算法設(shè)計(jì)31s/函數(shù)功能：從函數(shù)功能：從stepi-1出發(fā)，求出發(fā)，求(stepistepSIZE*SIZE)。stepi-1坐標(biāo)為（坐標(biāo)為（x，y） void try(int i,int n,int x,int y) int dir,u,v; for(dir=0;dir=0) & (u=0) & (v=S

26、IZE-1) & (boarduv=0)boarduv=i;/*占據(jù)位置占據(jù)位置u,v*/ if(i=n) /已經(jīng)走完已經(jīng)走完25步，則統(tǒng)計(jì)方案個(gè)數(shù)，打印方案，跳出遞歸步，則統(tǒng)計(jì)方案個(gè)數(shù)，打印方案，跳出遞歸 num+; printSolution();/打印方案打印方案 else try(i+1,n,u,v); / 從從xi出發(fā)，遞歸求出發(fā)，遞歸求(xi+1, x ) boarduv=0;/清空位置清空位置 。不可少！。不可少！ / end of if /end of for 跳馬問題跳馬問題遞歸函數(shù)遞歸函數(shù) jidao-chap16+回溯算法設(shè)計(jì)32#include#define SIZE

27、5 int row8=1,2,2,1,-1,-2,-2,-1;/*8個(gè)方向上的個(gè)方向上的x增量增量*/int col8=-2,-1,1,2,2,1,-1,-2; /*8個(gè)方向上的個(gè)方向上的y增量增量*/int boardSIZESIZE=0;/*記錄走的路徑記錄走的路徑*/int num;/*記錄方案總個(gè)數(shù)記錄方案總個(gè)數(shù)*/ main()int row,col;/*初始化初始化*/num=0; board00=1; /*占據(jù)位置（占據(jù)位置（0,0）*/ try(2,SIZE*SIZE,0,0); /*從從(0,0)出發(fā)，尋找后續(xù)位置出發(fā)，尋找后續(xù)位置*/ /*輸出總方案數(shù)輸出總方案數(shù)*/ pr

28、intf(總方案數(shù)為總方案數(shù)為%d,num); system(pause); 跳馬問題跳馬問題主函數(shù)主函數(shù) jidao-chap16+回溯算法設(shè)計(jì)33三三. 回溯法解題思路回溯法解題思路例例3. 背包問題背包問題 有不同價(jià)值、不同重量的物品有不同價(jià)值、不同重量的物品n件，求從這件，求從這n件物品中件物品中選取一部分物品的選擇方案，使選中物品的總重量不選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價(jià)值之和最大。超過指定的限制重量，但選中物品的價(jià)值之和最大。weight=16,15,15value=45,25,25weightLimit=30則最優(yōu)解是則最優(yōu)解是(0,1,1) jidao-chap16+回溯算法設(shè)計(jì)34 jidao-chap16+回溯算法設(shè)計(jì)35背包問題1void try(int i,int n,int weight,int value,int weightLimit,int solution,int bestSolution) int xi; for(xi=0;xi=1;xi+) solutioni=