算法设计与分析复习05：回溯及分支限界

曾经终败给现在 2024-03-30 13:33 68阅读 0赞

> 作者：非妃是公主  
> 专栏：《算法》  
> **个性签：顺境不惰，逆境不馁，以心制境，万事可成。——曾国藩**
> 
> ![在这里插入图片描述][7cea80270e124c7faeb5f6b5fd8ac41a.jpeg]
> 
> ### 专栏系列文章 ###
> 
> [算法设计与分析复习01：主方法求递归算法时间复杂度][01]
> 
> [算法设计与分析复习02：分而治之算法][02]
> 
> [算法设计与分析复习03：动态规划算法][03]  
> [算法设计与分析复习04：贪心算法][04]
> 
> [算法设计与分析复习05：回溯及分支限界][05]
> 
> [算法设计与分析复习06：随机化算法][06]
> 
> [算法设计与分析复习07：样题][07]
> 
> #### 文章目录 ####
> 
>  *   *  专栏系列文章
>      *  复习重点
>      *  回溯及分支限界
>      *   *  0-1背包
>          *  TSP问题
>          *  皇后问题

### 复习重点 ###

![在这里插入图片描述][16ee73d314d24fd7a218b4b65604a9f6.png]

### 回溯及分支限界 ###

![在这里插入图片描述][18f5bb59df884b11a7cf1a07753ac390.png]  
![在这里插入图片描述][b2ccb28db2644d16b34a7c6515bca384.png]  
![在这里插入图片描述][c299a0b8544f45978455f6b02dd9f7f6.png]  
回溯法与深搜的不同点：  
![在这里插入图片描述][3e866eb2cc064c6897373c4105f49db5.png]

![在这里插入图片描述][7ad7d1187cf74934804aaf167d85febc.png]

#### 0-1背包 ####

![在这里插入图片描述][927f805acc5a4b21bc25244ebf792644.png]

#### TSP问题 ####

![在这里插入图片描述][3581e102de584928a1869518313124c8.png]  
![在这里插入图片描述][57d106b79d1a473d89def27b5e34598c.png]  
解空间描述：排列树  
![在这里插入图片描述][27fbcc2189c542e79e1eacdbfe7be96d.png]

#### 皇后问题 ####

![在这里插入图片描述][f34ce5a499e54d30b53694f8a96b8c22.png]  
![在这里插入图片描述][2d9b83fbb4f54bcd98f9536f872b16ba.png]  
[8皇后问题详解][8]

[7cea80270e124c7faeb5f6b5fd8ac41a.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dee78b6282774a9a94d68780d4608178.jpeg
[01]: https://blog.csdn.net/myf_666/article/details/128509102
[02]: https://blog.csdn.net/myf_666/article/details/128509126
[03]: https://blog.csdn.net/myf_666/article/details/128509143
[04]: https://blog.csdn.net/myf_666/article/details/128509159
[05]: https://blog.csdn.net/myf_666/article/details/128509168
[06]: https://blog.csdn.net/myf_666/article/details/128509174
[07]: https://blog.csdn.net/myf_666/article/details/128509183
[16ee73d314d24fd7a218b4b65604a9f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/aeca2f04d50e4690a6212df0fd65b1b8.png
[18f5bb59df884b11a7cf1a07753ac390.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b449a392370549d083fe7e1a00ab5f09.png
[b2ccb28db2644d16b34a7c6515bca384.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/174530bc36f542d0ac1cca44aad0a009.png
[c299a0b8544f45978455f6b02dd9f7f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/847445c2efcf4c25a63ff97eb9dfa727.png
[3e866eb2cc064c6897373c4105f49db5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a12666aae1a24589a3a2126f836e0c0b.png
[7ad7d1187cf74934804aaf167d85febc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c00070ec42aa426ba980b48a8e707071.png
[927f805acc5a4b21bc25244ebf792644.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7f1cbc448d104cd0a8b35e0b7dd34eec.png
[3581e102de584928a1869518313124c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/415f74d041844408a61da11b66a6baa0.png
[57d106b79d1a473d89def27b5e34598c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6bdd0e2917ed420fb0dc80eaae91aa58.png
[27fbcc2189c542e79e1eacdbfe7be96d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a1cc74c49c30432aad7ace857804b0e0.png
[f34ce5a499e54d30b53694f8a96b8c22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/136fe68772f64aca96b969e4971cdd36.png
[2d9b83fbb4f54bcd98f9536f872b16ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8253e5087ed54fd7b4937ddec0b6d7b4.png
[8]: https://blog.csdn.net/myf_666/article/details/114795432