下载文档原格式
回溯算法原理和几个常用的算法实例回溯算法是一种基于深度优先的算法，用于解决在一组可能的解中找到满足特定条件的解的问题。
其核心思想是按照特定的顺序逐步构造解空间，并通过剪枝策略来避免不必要的。
回溯算法的实现通常通过递归函数来进行，每次递归都尝试一种可能的选择，并在达到目标条件或无法继续时进行回溯。
下面介绍几个常用的回溯算法实例：1.八皇后问题：八皇后问题是一个经典的回溯问题，要求在一个8×8的棋盘上放置8个皇后，使得每个皇后都不能相互攻击。
即每行、每列和对角线上都不能有两个皇后。
通过在每一列中逐行选择合适的位置，并进行剪枝，可以找到所有满足条件的解。
2.0-1背包问题：0-1背包问题是一个经典的组合优化问题，要求在一组物品中选择一些物品放入背包，使得其总重量不超过背包容量，同时价值最大化。
该问题可以通过回溯算法进行求解，每次选择放入或不放入当前物品，并根据剩余物品和背包容量进行递归。
3.数独问题：数独问题是一个经典的逻辑推理问题，要求在一个9×9的网格中填入数字1-9，使得每行、每列和每个3×3的子网格中都没有重复数字。
该问题可以通过回溯算法进行求解，每次选择一个空格，并依次尝试1-9的数字，然后递归地进行。
4.字符串的全排列：给定一个字符串，要求输出其所有可能的排列。
例如，对于字符串"abc"，其所有可能的排列为"abc"、"acb"、"bac"、"bca"、"cab"和"cba"。
可以通过回溯算法进行求解，每次选择一个字符，并递归地求解剩余字符的全排列。
回溯算法的时间复杂度通常比较高，因为其需要遍历所有可能的解空间。
但是通过合理的剪枝策略，可以减少的次数，提高算法效率。
在实际应用中，可以根据具体问题的特点来设计合适的剪枝策略，从而降低算法的时间复杂度。
回溯法一、回溯法：回溯法是一个既带有系统性又带有跳跃性的的搜索算法。
它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。
否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。
这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。
二、算法框架：1、问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。
问题的解空间应到少包含问题的一个（最优）解。
2、回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点，同时也成为当前的扩展结点。
在当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的活结点，并成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。
换句话说，这个结点不再是一个活结点。
此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；3、递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：procedure try(i:integer);varbeginif i>n then 输出结果else for j:=下界 to 上界 dobeginx[i]:=h[j];if 可行{满足限界函数和约束条件} then begin 置值；try(i+1); end;end;end;说明：i是递归深度；n是深度控制，即解空间树的的高度；可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；二、习题：1、0-1背包：n=3,w=[16,15,15],p=[45,25,25],c=302、旅行售货员问题：某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。
回溯法的基本介绍以及原理
回溯法是一种通过逐步试探、回溯到上一步来寻找问题解的方法。
它适用于在一个问题的解空间中搜索所有可能的解，通过深度优先的方式进行搜索。
回溯法的基本原理是：从问题的初始状态开始，不断地进行选择，当发现选择导致了无效的解或者无法继续选择时，就回溯到上一步重新进行选择。
在回溯的过程中，保存了每一步的选择，这样可以在找到一个解或者搜索完整个解空间后，利用已经保存的选择恢复出解。
具体来说，回溯法一般包含以下步骤：
1. 定义问题的解空间：也就是问题的所有可能的解组成的空间。
2. 制定问题的解空间的搜索规则：决定了在解空间中搜索的顺序和方式。
3. 利用深度优先的方式进行搜索：从问题的初始状态开始，逐步进行选择，如果选择导致了无效的解或者无法继续选择，则回溯到上一步。
4. 终止条件：当搜索完整个解空间或者找到一个解时，终止搜索。
回溯法的时间复杂度一般很高，因为它需要搜索整个解空间。
但是，通过合理的剪枝策略，可以减少搜索的路径，降低时间
复杂度。
回溯法常常应用于解决组合问题、排列问题、子集问题等涉及组合选择的问题，也可以用于解决图的遍历问题等其他类型的问题。
回溯法与分支限界法
回溯法和分支限界法是两种常见的搜索算法，它们被广泛应用于解决优化问题、约束满足问题以及决策问题等。
1. 回溯法：
回溯法是一种基于试错的搜索算法。
它通过搜索解空间树来寻找问题的解。
在搜索过程中，回溯法会尝试不同的分支，也就是不同的可能解，直到找到解或者确定无解。
如果一条路径上无法得到解，回溯法就会回溯到上一步，尝试其他的分支。
回溯法的优点是它可以找到问题的所有解，而且对于一些问题，它能够找到最优解。
然而，它的缺点是如果问题的解空间树太大，那么回溯法可能会需要大量的时间和空间。
2. 分支限界法：
分支限界法是一种有约束的深度优先搜索算法。
它也是一种用于求解优化问题的算法。
在分支限界法中，搜索过程被分为两个阶段：扩展阶段和限界阶段。
在扩展阶段，算法会生成所有可能的候选解，并将它们加入到候选解集中。
在限界阶段，算法会根据一些启发式信息对候选解进行排序，并只考虑排在最前面的候选解。
这样可以大大减少搜索的时间和空间复杂度。
分支限界法的优点是它可以找到问题的最优解，而且它的时间复杂度是可以控制的。
然而，它的缺点是如果问题的解空间树太大，那么它可能需要大量的内存来存储候选解。
总的来说，回溯法和分支限界法都是非常重要的搜索算法，它们在不同的场景下都有各自的优势和适用性。
回溯性方案引言回溯法是一种常用于解决组合问题的算法，它通过逐步构建解决方案，并在达到某个不可行解时进行回溯，寻找其他可行解。
回溯法在求解组合、排列、子集、图的遍历等问题中都有广泛的应用。
本文将介绍回溯算法的基本原理、应用场景以及一些常见的优化技巧。
基本概念回溯法是一种通过尝试所有可能的解决方案来求解问题的算法。
它遵循以下基本步骤：1.定义问题的解空间：确定问题的解空间，表示问题可能的解决方案。
2.确定约束条件：确定问题的约束条件，这些条件将约束解的可行性。
3.定义搜索策略：确定一种搜索策略，以确定如何选择下一个可行候选解。
4.回溯搜索：按照搜索策略，逐步构建解决方案，并在达到不可行解时进行回溯，寻找其他可行解。
应用场景回溯法在以下场景中有广泛的应用：1. 组合问题回溯法常用于求解组合问题，即从给定的一组元素中选取若干个元素进行组合。
比如，在一个数组中找到所有可能的组合，使得它们的和等于一个给定的目标值。
2. 排列问题回溯法也可以用于求解排列问题，即从给定的一组元素中选取若干个元素进行排列。
与组合问题不同的是，排列要求选取的元素按照一定的顺序排列。
3. 子集问题回溯法可用于求解子集问题，即从给定的一组元素中选取若干个元素进行组合，不考虑元素的顺序。
4. 图的遍历回溯法在图的遍历问题中也有应用，它通过逐步搜索图中的节点来寻找解决方案。
常见的图的遍历问题有深度优先搜索和广度优先搜索。
优化技巧为了提高回溯算法的效率，可以采用以下一些优化技巧：1. 剪枝操作在每一步的搜索过程中，可以进行剪枝操作，即根据约束条件排除一些明显不可行的解。
这样可以减少搜索空间，提高算法的效率。
2. 使用动态规划保存中间结果对于某些需要重复计算的子问题，可以使用动态规划保存中间结果，避免重复计算，提高算法效率。
3. 优化搜索顺序通过优化搜索顺序，可以使得更有可能找到可行解，从而提高算法的效率。
具体的优化策略可以根据问题的特点进行选择。
回溯法原理
回溯法是一种用于解决问题的算法，它的核心思想是在解空间中进行深度优先搜索，通过不断地试错和回溯，找到问题的解。
回溯法通常应用于求解组合优化问题、排列组合问题、图论问题等。
回溯法的具体实现过程，一般包括以下几个步骤：
1. 定义问题的解空间：首先需要明确问题的解空间，即指所有可能的解构成的空间。
2. 确定扩展解策略：在解空间中选择一个可行解作为起点，然后通过一定的扩展策略生成新的可行解，这些新的可行解将被加入到搜索树中。
3. 搜索解空间：从起点开始，按照扩展策略不断生成新的可行解，并将这些新的可行解加入到搜索树中，然后深入搜索直到找到问题的解或者搜索完整个解空间。
4. 回溯：如果某个可行解无法继续扩展，或者扩展后发现不合法，那么就需要回溯到上一个可行解，重新选择扩展策略，并继续搜索。
回溯法的优点在于能够找到所有解，但缺点也很明显，就是时间复杂度很高，因为需要搜索整个解空间。
为了减少搜索时间，可以采用一些剪枝技巧，如约束传播、可行性剪枝等。
总之，回溯法是一种通用的求解算法，它的基本思想和实现方式可以应用于各种类型的问题，但要注意在实际应用中需要根据具体问题进行合理的优化和改进。
索夫克勒斯回溯法摘要：1.索夫克勒斯回溯法的定义与原理2.索夫克勒斯回溯法的应用领域3.索夫克勒斯回溯法的优缺点分析4.我国在索夫克勒斯回溯法方面的研究与发展正文：一、索夫克勒斯回溯法的定义与原理索夫克勒斯回溯法（Sofkleis Backtracking Method）是一种启发式搜索算法，用于解决组合优化问题。
该算法起源于古希腊数学家索夫克勒斯的研究，其主要思想是在搜索过程中尝试所有可能的解决方案，当发现当前解决方案不符合要求时，就回溯到上一个节点，继续尝试其他分支。
通过这种方式，可以在较短时间内找到问题的一个可行解。
二、索夫克勒斯回溯法的应用领域索夫克勒斯回溯法广泛应用于组合优化、人工智能、运筹学等领域，具体包括：1.旅行商问题（Traveling Salesman Problem）：这是一种经典的组合优化问题，旨在找到一个访问一系列城市并返回出发点的最短路径。
2.装载问题（Loading Problem）：该问题涉及到在有限的空间内合理安排物品的摆放方式，以便使得总重量最小或空间利用率最高。
3.0-1 背包问题（0-1 Knapsack Problem）：该问题描述的是在给定的一组物品中，选择若干个物品放入背包，使得背包内物品总价值最大，同时不超过背包的容量限制。
三、索夫克勒斯回溯法的优缺点分析1.优点：- 搜索过程中充分利用了问题的约束条件，减少了无效搜索的次数；- 可以在较短时间内找到问题的一个可行解；- 算法结构简单，易于实现和理解。
2.缺点：- 当问题规模较大时，搜索树可能会变得非常庞大，导致计算量过大；- 索夫克勒斯回溯法只能找到一个可行解，而不一定是最优解；- 可能存在重复计算的情况，降低了算法的效率。
四、我国在索夫克勒斯回溯法方面的研究与发展我国在索夫克勒斯回溯法方面的研究起步较晚，但发展迅速。
近年来，我国学者在理论研究和实际应用方面取得了一系列成果，包括：1.对索夫克勒斯回溯法的原理进行了深入探讨，提出了一系列改进算法，提高了算法的搜索效率；2.将索夫克勒斯回溯法应用于实际问题的求解，取得了显著的效果；3.积极开展国际学术交流与合作，与国际同行共享研究成果，共同推动了索夫克勒斯回溯法的发展。
回溯算法原理今天来聊聊回溯算法原理，这可是个很有趣的东西呢。
你们有没有玩过走迷宫的游戏呀？我小时候可喜欢玩了。
当我们走进一个迷宫的时候，其实就面临很多条路可以选择。
假设我们从迷宫的入口进去，一进去就有好几条岔路对吧。
回溯算法呀，就有点像我们在走这个迷宫时的策略。
打个比方，我们在迷宫里先选择了左边的一条路走，走着走着发现前面是死胡同了，这时候怎么办呢？如果这是在回溯算法里呀，我们就会退回到上一个岔路口，然后选择另外一条路继续走。
就像是我们走错了，然后原路返回去重新尝试其他可能的路径一样。
回溯算法呢，其实就是一种在搜索问题解空间时的策略。
在解决好多问题的时候，问题的全部可能解可能会组成一个树状结构，就像家族树那样，每一个节点就代表一种状态或者解的一部分。
老实说，我一开始也不太明白，为什么要有这样一种算法呢？直到我遇到过这样一个实际例子。
比如说要安排一个活动时间表，有好几个活动，每个活动有开始和结束时间，我们要在有限的时间里尽可能多的安排活动，又不能有冲突。
解决这个问题的时候就可以用回溯算法。
我们从第一个活动开始尝试安排，就像从迷宫入口选择了一条路出发一样，如果后面发现安排了这个活动会导致后面的活动无法安排，也就是像在迷宫里走到死胡同了，那就回退到还没有安排这个活动的时候，尝试其他活动的安排。
说到这里，你可能会问，那怎么知道什么时候该回退呢？这就是回溯算法的一个关键判断点了。
当我们发现按照当前选择的路径走下去，不能找到满足要求的解的时候，就需要回退。
比如说在活动安排那个例子里，你发现按照现有的安排，后面会有活动完全没法安排，那就得改前面的安排，这就是回退了。
我自己的理解是，回溯算法其实就是一种“不断尝试- 失败回退- 再尝试”的过程。
它的好处就是只要解存在，就一定能够找到最终的解（如果搜索空间是有限的）。
不过呢，我也意识到它的一个小缺点，那就是如果解空间特别大的话，可能要花费很多时间在回退和重新尝试上，就像在一个巨大无比的迷宫里，我们可能要不断走回头路很多次才能找到出口。
回溯算法原理和几个常用的算法实例回溯算法是一种通过不断尝试和回退的方式来进行问题求解的算法。
它的基本思想是在过程中，当发现当前的选择并不符合要求时，就进行回退，尝试其他的选择，直到找到符合要求的解或者遍历完所有可能的选择。
回溯算法通常用于问题求解中的和排列组合问题，比如求解八皇后问题、0-1背包问题、数独等。
下面将介绍几个常用的回溯算法实例。
1.八皇后问题：八皇后问题是指在一个8×8的国际象棋棋盘上，放置八个皇后，使得任意两个皇后都不在同一行、同一列或同一斜线上。
可以通过递归的方式依次尝试每一行的位置，并判断当前位置是否满足条件。
如果满足条件，则进入下一行尝试；否则回溯到上一行，并尝试其他的位置，直到找到解或遍历完所有的可能。
2.0-1背包问题：0-1背包问题是指在给定一组物品和一个容量为C的背包，每个物品都有自己的重量和价值，求解在不超过背包容量时，如何选择物品使得背包中物品的总价值最大。
可以通过递归的方式依次考察每个物品，并判断是否选择当前物品放入背包。
如果放入当前物品，则背包容量减小，继续递归考察下一个物品；如果不放入当前物品，则直接递归考察下一个物品。
直到遍历完所有物品或背包容量为0时，返回当前总价值。
3.数独问题：数独是一种通过填充数字的方式使得每一行、每一列和每一个九宫格内的数字都满足一定条件的谜题。
可以通过递归的方式依次尝试填充每一个空格，并判断当前填充是否符合条件。
如果符合条件，则继续递归填充下一个空格；如果不符合条件，则回溯到上一个空格，并尝试其他的数字，直到找到解或遍历完所有的可能。
回溯算法的时间复杂度一般较高，通常为指数级别。
因此，在实际应用中，可以结合剪枝等优化策略来提高算法的效率。
此外，回溯算法也可以通过非递归的方式进行实现，使用栈来存储当前的状态，从而避免递归带来的额外开销。
总之，回溯算法是一种非常有效的问题求解方法，通过不断尝试和回退，可以在复杂的空间中找到符合要求的解。
Backtracking(回溯法)1 The generic methodWe have many searching problems that ask for an optimal solution satisfying some conditions (constraints) in a well defined searching space.Backtracking and branch-and-bound deal with a large class of searching problems, where a solution is represented by an n-tuple:(x1, x2, …, x n), where x i∈S i and S i is a finite set.Therefore, a solution is a point in an n-dimensional space. The searching space is a set of points bounded by S i. In addition, a criterion function P(x1, x2, …, x n), is given, which is used to define a desired solution(s). For example, the solution must maximize value of P, orminimize value of P, ormake P = 0, etc.The conditions x i∈S i(1≤i≤n) are called explicit constraints. The constraints imposed by P are called implicit constraints.Usually, such a searching space can be organized by a tree called search tree, where a path from the root to a node represents a partial solution:(x1, x2, …, x i), i ≤n.A backtracking algorithm (or branch-and-bound algorithm) uses a bounding function B(x1, x2, …, x i) to evaluate the partial solution (x1, x2, …, x i) to see if this partial solution has any chance to develop to a desired solution. If not, the algorithm prunes the subtree rooted at this node and will not search any solutions in this subtree. By doing so, we can save great deal of time.Therefore, a backtracking algorithm (or branch-and-bound algorithm) is to traverse the search tree and check each node until a solution is found. Because the structure of the tree is usually known in advance, we need not explicitly build the tree before the traversal starts. We only need to know how to find the next node from the current one. Moreover, the size of the tree is usually prohibitively large to be explicitly built and stored.It is possible that a path from the root to an internal node in the search tree represents a solution. If a node satisfies the explicit constraints, it is called a solution node. If a solution node satisfies the implicit constraints also, then it is called a answer node.The difference between backtracking and branch-and-bound algorithms is the way to conduct the search. A backtracking algorithm uses DFS (Depth-First-Search) together with a bounding function while a branch-and-bound algorithm uses BFS (Breadth-First Search) with a bounding function. Sometimes, a branch-and-bound algorithm uses D-search instead of BFS. The D-search is a combination of BFS and DFS. We will discuss in another chapter.During searching, a node is called a live node if this node has been generated but not all its children have been generated.A node is called the E-node if it is a live node and its children are currently being generated. A node is called a dead node if all of its children have been generated.Note. If we use DFS, the live nodes are those that are currently stored in the stack, the E-node is the node on top of the stack and the dead nodes are those that have been popped from the stack. If we use BFS, then the live nodes are those in the queue, the E-node is the node in the head of the queue. The dead nodes are those that have been de-queued.In this chapter, we will discuss backtracking only.Let us present a general algorithm first, then, we use several examples to illustrate this searching method.Suppose (x1, x2, …, x i) be a path from the root to a node which represents a partial solution. LetT(x1, x2, …, x i) = { x i+1 | (x1, x2, …, x i, x i+1) is a node in the tree} We assume that a bounding function B i is used for level i. That is, B i(x1, x2, …, x i) will produce true or false. If yes, then search will continue from the node (x1, x2, …, x i), otherwise, all nodes in the subtree rooted at this node will not be searched.A general (recursive) backtracking algorithm is given as follows.Backtrack (k)//input: x[1], x[2], …, x[k-1], which represents a partial solution. //output: all answer nodes from this node.for each x[k] T(x[1], x[2], …, x[k-1])do if B k(x[1], x[2], …, x[k-1], x[k]) = truethen {if (x[1], x[2], …, x[k-1], x[k])is an answer node.then output x[1..k];if k < nthen Backtracking(k+1)}End.The search problem can be solved by calling Backtrack (1). Note that this algorithm is the same as DFS except that the DFS will stop and backup at dead nodes, where a dead node (x1, x2, …, x i) is a node where we have B i(x[1], x[2], …, x[i]) = false.2 The 8-queen problemThe 8-queen problem is a well-known combinatorial problem. A solution to this problem is to place 8 queens in an 8 8 chessboard such that no two of them are on the same row, or same column, or same diagonal. In other words, among the 8 queens, any queen cannot attack any other queen. Obviously, we can extend this problem to n-queen problem. Fig. 1 shows a solution.1 2 3 4 5 6 7 8ColumnRow 1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 QFig. 1 An illustration of a solution of the 8-queen problem.Let x i be the column number of a queen at i th row, then the solution in Fig. 1 can be represented by a 8-tuple (4, 6, 8, 2, 7, 1, 3, 5). Obviously, the searching space (the tree) has 88 different 8-tuples if S i = {1, 2, 3, 4, 5, 6, 7, 8}. If we do not allow x i to repeat a value in partial solution of (x1, x2, …, x i-1), then the searching space (the tree) has 8! different 8-tuples. This kind of tree is called permutation tree.Fig. 2 shows the search tree (also called state space tree) for the 4-queen problem, where the numbers in nodes indicate the ordering in DFS.12 36 4 57 811 9 10 12 1316 14 15 17 18 1922 20 21 23 2427 25 26 28 2932 30 31 33 34 35 38 36 37 39 4043 41 42 44 4548 46 47 49 50 51 54 52 53 55 5659 57 58 60 616462 63 65x 1 = 1 x 1 = 2 x 1 = 3 x 1 = 423 4 3 3 3 3 3 4 4 4 4 2 4 2 3 2 32 134 3 1 4 4 1 1 4 33 1 1 24 2 4 4 2 1 4 1 22 4 1 1 1 2 2 13 1 23 2 3 1 2 1 Fig. 2 The permutation tree for the 4-queen problem.A bounding function we use is Place(k , l ). This function will check if we can place k th queen in the location (k , l ) (k th row and l th column) without conflicting with previously placed (k -1) queens. We notice that queens at location (i , j ) and (k , l ), i < k , conflict if and only if (j = l or |i - k | = |j - l |). Function Place(k , l ); 1 for i 1 to k -12 do { if (x [i ] = l ) or (|i - k | = |x [i ] - l |)3 then return (false )4 }5 return (true )6 EndThe backtracking algorithm for n -queens is as follows.N-queens(k , n )//input: x [1..k -1] for l 1 to n do if Place(k , l ) = true then { x [k ] = l ; if k = n then output (x [1..n ]) else N-queens(k +1, n ) } End.The n -queen problem can be solved by calling N-queens(1, n ). Fig. 3 shows the portion of the permutation tree generated by the backtracking algorithm N-queens(1, 4).12 3811 9 1316 14 15 18 19 24 29 30 31 34 35 38 39 40 45 50 51 54 52 53 56 59 57 61 36 x 1 = 1 x 1 = 2 x 1 = 3 x 1 = 42 3 4 3 3 3 2 4 3 2 3 1 1 4 3 1 2 4 42 1 2 2 13 2 2 332 BBB BBBB B BBB B B BB BXXFig. 3 The portion of the permutation tree of Fig. 2 that isgenerated during backtracking.3 The subset sum problem In a subset-sum problem, we are given a finite set S of positive integers and a target number t . We ask whether there is a subset A ⊆ S whose elements sum to t . For example, if S = {3, 5, 7, 8}, t = 15, then A = {3, 5, 7} is a solution. Another solution is {7, 8}. Let S = {a 1, a 2, …, a n } be the set of numbers. Any subset of S can be represented by an n -tuple (x 1, x 2, …, x n ), where x n ∈{0, 1}, 1≤i ≤n . Moreover, x i = 0 if x i ∉ A and x i = 1 if x i ∈ A. Another way to represent a solution is to use a k -tuple that contains only those indices of chosen numbers. For example, S = {a 1, a 2, a 3, a 4} = {3, 5, 7, 8}, one solution is (1, 2, 3), another is (3, 4). Obviously, k is a variable. In the following solution, we use the fixed-sized tuples. Suppose x a i ki i ∑=1 = t then (x 1, x 2, …, x k ) is a solution, wherex a i ki i ∑=1= sum of the numbers in partial solution (x 1, x 2, …, x k ).If x a i ki i ∑=1< t , then a simple bounding function isB k (x 1, x 2, …, x k ) = true if and only ifx a i ki i ∑=1+ ∑+=nk i i a 1≥ twhere∑+=nk i i a 1= sum of all remaining numbers we can add to the partialsolution.If we assume the n numbers are sorted initially, a 1≤ a 2≤ …≤ a n , then the bounding function can be strengthened tox a i k i i ∑=1+ ∑+=n k i i a 1≥ t and x a i ki i ∑=1+ a k +1 ≤ t .The backtracking algorithm for subset sum problem is as follows.Subset-sum(S , k , n )//input: sorted array a [1..n ], x [1..k -1], where x a i k i i ∑-=11<t andx a i k i i ∑-=11+ ∑=nki i a > t .1 sum ← x a i k i i ∑-=112 r ← ∑=nki i a3 x [k ] = 1;4 if sum + a [k ] = t // a [k ] = a k5 then output solution x [1..k ]6 else { if sum + a [k ] + a [k +1] ≤ t7 then Subset-sum(S , k +1, n )8 if (sum + r - a [k ] ≥ t ) and sum + a [k +1] ≤ t 9then { x [k ] = 0;10Subset-sum(S, k+1, n)11}12}13End.The subset sum problem can be solved by calling Subset-sum(S, 1, n).4 Estimate the searching spaceWe usually use Monte Carlo method to estimate the searching space. The method is to randomly create a search path from a root to an answer node or to a dead node. Specifically, we do two things at each node:(1) Compute the number of child nodes that satisfy thebounding functions.(2) Randomly select a child from the set of children as the nextnode.Suppose the path has i levels deep, not counting the last level. Level 0 consist of a single node that is the root of the search. Let the number of child nodes at level j (≤ i ) is m j . Fig. 4 illustrates the situation. Level i is the level before reaching the dead node.Root has m 0 child nodes at level 1 a has m 1 child nodes at level 2∙ root∙ ∙ ∙ ∙ dead nodeab kk has m i child nodes at level i +1 Fig. 4 An illustration of the Monte Carlo method.Then, we can use the formula 1 + m 1⋅ m 2 ⋅ ⋅ ⋅ m i to estimate the search space. To be more accurate, we often try several paths and use the average to estimate. For example, if we take threepaths, path(1, 19), path (1, 39), and path(1, 52) in Fig. 3. Then we get three estimates:1+4⨯3 = 13, 1+4⨯3⨯2⨯1= 25, and 1+4⨯3⨯2= 25.The average is (25+25+13)/3 = 21.When n is larger, we will get much smaller estimate for the backtracking algorithm for n-queens.。
