0027算法笔记——回溯法与装载问题

1、回溯法

** (1)描述:** 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为 回溯法 。

(2)原理

回溯法的基本策略是查找问题解决方案的一种有序方法，并非单纯依靠随机尝试的方式进行探索。它通过系统性地组织可能的候选集合，并通过避免冗余计算来提升效率，在求解复杂问题时表现出色。对于那些规模庞大且需要精准求解的问题组合优化类的问题而言，这种技术往往成为解决问题的关键工具之一；尤其当一个问题需要找到其全部可能解集或是确定满足特定约束条件下最佳单个解时，则会频繁运用这一方法

(3)问题的解空间

问题的解可以表示为：回溯法试图将问题的解表示为一个由变量x1到xn组成的元组

显约束：对分量xi的取值限定。

隐约束：为满足问题的解而对不同分量之间施加的约束。

在某个具体的问题实例下, 满足显式约束条件的全部多元组集合构成了该问题的一个全部可能的解集合.

注意：同一个问题可能有多种不同的表示形式，在这些表达方式中有一些更为简洁明了；所需表达的状态空间规模较小（意味着存储资源占用较低），并且其对应的搜索过程相对简便。

例1：n=3的0——1 背包问题的回溯法搜索过程。W=[16,15,15] p=[45,25,2