下载文档原格式
算法设计与分析——批处理作业调度（回溯法）之前讲过⼀个相似的问题流⽔作业调度问题，那⼀道题最开始⽤动态规划，推到最后得到了⼀个Johnson法则，变成了⼀个排序问题，有兴趣的可以看⼀下本篇博客主要参考⾃⼀、问题描述给定n个作业的集合{J1,J2,…,Jn}。
每个作业必须先由机器1处理，然后由机器2处理。
作业Ji需要机器j的处理时间为t ji。
对于⼀个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。
所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度⽅案，使其完成时间和达到最⼩。
例：设n=3，考虑以下实例：看到这⾥可能会对这些完成时间和是怎么计算出来的会有疑问，这⾥我拿123和312的⽅案来说明⼀下。
对于调度⽅案（1,2,3）作业1在机器1上完成的时间是2，在机器2上完成的时间是3作业2在机器1上完成的时间是5，在机器2上完成的时间是6作业3在机器1上完成的时间是7，在机器2上完成的时间是10所以，作业调度的完成时间和= 3 + 6 + 10这⾥我们可以思考⼀下作业i在机器2上完成的时间应该怎么去求？作业i在机器1上完成的时间是连续的，所以是直接累加就可以。
但对于机器2就会产⽣两种情况，这两种情况其实就是上图的两种情况，对于（1,2,3）的调度⽅案，在求作业2在机器2上完成的时间时，由于作业2在机器1上还没有完成，这就需要先等待机器1处理完；⽽对于（3,1,2）的调度⽅案，在求作业2在机器2上完成的时间时，作业2在机器1早已完成，⽆需等待，直接在作业1被机器1处理之后就能接着被处理。
综上，我们可以得到如下表达式if(F2[i-1] > F1[i])F2[i] = F2[i-1] + t[2][i]elseF2[i] = F1[i] + t[2][i]⼆、算法设计类Flowshop的数据成员记录解空间的结点信息，M输⼊作业时间，bestf记录当前最⼩完成时间和，数组bestx记录相应的当前最佳作业调度。
沈阳理工大学算法实践与创新论文摘要对于计算机科学来说，算法的概念是至关重要的，算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
为了更加的了解算法，本篇论文中，我们先研究一个算法---回溯法。
回溯法是一种常用的重要的基本设计方法。
它的基本做法是在可能的范围之内搜索，适于解一些组合数相当大的问题。
圆排列描述的是在给定n个大小不等的圆 C1,C2,…,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。
圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。
图着色问题用数学定义就是给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。
其优化版本是希望获得最小的K值。
符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。
在本篇论文中，我们将运用回溯法来解决着图的着色问题，符号三角形问题，图排列问题，将此三个问题进行深入的探讨。
关键词: 回溯法图的着色问题符号三角形问题图排列问题目录第1章引言 (1)第2章回溯法的背景 (2)第3章图的着色问题 (4)3.1 问题描述 (4)3.2 四色猜想 (4)3.3 算法设计 (5)3.4 源代码 (6)3.5 运行结果图 (10)第4章符号三角形问题 (11)4.1 问题描述 (11)4.2 算法设计 (11)4.3 源代码 (12)4.4 运行结果图 (16)第5章圆的排列问题 (17)5.1 问题描述 (17)5.2 问题分析 (17)5.3 源代码 (18)5.4 运行结果图 (22)结论 (23)参考文献 (24)第1章引言在现实世界中，有相当一类问题试求问题的全部解或求问题的最优解。
最基本的方法是通过枚举法搜索问题的解空间。
但许多问题解空间的大小随问题规模n的增长呈指数规律增长，这就使问题理论上可解而实际不可行。
回溯法概述与穷举的“笨拙”搜索相较，回溯法那么是一种“伶俐”的求解效益更高的搜索法。
下面介绍回溯设计及其应用，体会回溯法相关于穷举的特点与优势。
回溯的概念有许多问题，当需要找出它的解集或要求回答什么解是知足某些约束条件的最正确解时，往往利用回溯法。
回溯法是一种试探求解的方式：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，假设试探成功，即取得解；假设试探失败，就慢慢往回退，换其他线路再往前试探。
因此，回溯法能够形象地归纳为“向前走，碰鼻转头”。
回溯法的大体做法是试探搜索，是一种组织得井井有条的、能幸免一些没必要要搜索的穷举式搜索法。
回溯法在问题的解空间树中，从根结点动身搜索解空间树，搜索至解空间树的任意一点，先判定该结点是不是包括问题的解；若是确信不包括，那么跳过对该结点为根的子树的搜索，逐层向其父结点回溯；不然，进入该子树，继续搜索。
从解的角度明白得，回溯法将问题的候选解按某种顺序进行列举和查验。
当发觉当前候选解不可能是解时，就选择下一个候选解。
在回溯法中，舍弃当前候选解，寻觅下一个候选解的进程称为回溯。
倘假设当前候选解除不知足问题规模要求外，知足所有其他要求时，继续扩大当前候选解的规模，并继续试探。
若是当前候选解知足包括问题规模在内的所有要求时，该候选解确实是问题的一个解。
与穷举法相较，回溯法的“伶俐”的地方在于能适时“转头”，假设再往前走不可能取得解，就回溯，退一步另找线路，如此可省去大量的无效操作。
因此，回溯与穷举相较，回溯更适宜于量比较大，候选解比较多的问题。
5.1.2 回溯描述1．回溯的一样方式下面简要论述回溯的一样方式。
回溯求解的问题P，通常要能表达为：关于已知的由n元组(x1,x2,…,x n)组成的一个状态空间E={(x1,x2,…,x n)|x i∈s i,i=1,2,…,n}，给定关于n元组中的一个分量的一个约束集D，要求E中知足D的全数约束条件的所有n元组。
算法设计与分析中的贪心算法与回溯法算法设计与分析领域中，贪心算法和回溯法是两种常用的解题方法。
本文将介绍这两种算法，并比较它们在不同场景下的优势和劣势。
一、贪心算法贪心算法是一种在每一步都选择当前最优解的策略，希望通过局部最优解的选择最终达到全局最优解。
贪心算法的实现较为简单，时间复杂度较低，适用于解决一些最优化问题。
贪心算法的基本思想是每次都选择当前状态下的最优解，并将其加入到解集中。
例如，在求解最小生成树的问题中，贪心算法会选择当前具有最小权值的边，并将其添加到最终结果中，直到生成树完成。
然而，贪心算法的局限性在于它只考虑了当前的最优解，无法保证找到全局最优解。
在某些问题中，贪心算法可能会陷入局部最优解而无法跳出。
因此，需要在具体问题中综合考虑问题的性质和约束条件来确定是否适合采用贪心算法。
二、回溯法回溯法是一种通过不断尝试可能的步骤来寻找问题解的方法。
它通常基于递归的思想，在每一步都尝试所有的可能选择，并逐步构建解空间，直到找到解或确定无解。
回溯法的核心思想是深度优先搜索，通过遍历解空间树来寻找解。
在每一步，回溯法都会考虑当前状态下的所有可能选择，并递归地进入下一步。
如果某一步的选择无法达到目标，回溯法会回退到上一步进行其他可能的选择。
回溯法常用于解决一些全排列、子集和组合等问题。
例如，在解决八皇后问题时，回溯法通过逐个放置皇后并进行合法性判断，直到找到所有解或遍历完所有可能的情况为止。
然而，回溯法的缺点在于其时间复杂度较高，其搜索过程包含了大量的重复计算。
因此，在使用回溯法解决问题时，需注意适当剪枝以减少搜索空间，提高算法效率。
三、贪心算法与回溯法的比较贪心算法和回溯法都是常用的算法设计与分析方法，但其适用场景和效果有所差异。
贪心算法在解决问题时能够快速找到局部最优解，并且具有较低的时间复杂度。
它适用于一些满足最优子结构性质的问题，例如最小生成树、单源最短路径等。
然而，贪心算法无法保证一定能找到全局最优解，因此需根据具体问题的特点来判断是否使用。
回溯法详解回溯法（Backtracking）是一种解决问题的算法，也称为试探法。
它是一种基于深度优先策略的搜索方法，用于在一个大型的搜索空间中找到所有可能的解。
回溯法常用于解决组合问题、优化问题、排列问题、路径问题等等。
回溯法的实现方法是：从一个初始状态开始，不断地向前搜索，直到找到一个合法的解或者所有的搜索空间都被遍历结束。
在搜索的过程中，如果发现当前的搜索路径不可能得到合法的解，就会回溯到上一个状态，继续向其他方向搜索。
回溯法仍然是一种穷举算法，但它通过剪枝操作排除大部分不必要的搜索路径，从而减少了搜索的时间和空间复杂度。
回溯法的实现过程中，我们需要完成以下三个步骤：1. 选择基于当前的状态，选择一个可能的方向，继续向前搜索。
这意味着我们需要对问题进行建模，找到一些限制条件或者选择条件，来指导我们如何选择下一个状态。
2. 约束在选择方向之后，我们需要考虑当前方向是否可行。
这称为约束条件。
如果当前的方向违反了某些约束条件，那么我们需要回溯到上一个状态，重新选择一个合法的方向。
3. 回溯如果当前方向无法得到一个合法解，我们就需要回溯到上一个状态，并尝试其他的方向。
回溯操作的核心是恢复状态，也就是将当前状态的改变撤回。
这意味着我们需要记录每一个状态的改变，从而能够正确地回溯。
回溯法的优点在于它的适用范围比较广泛，在解决复杂问题时能够得到很好的效果。
但同时回溯法也存在一些缺点，例如在搜索效率方面并不是最优的，在搜索空间比较大的情况下，时间和空间复杂度也会非常高。
因此，在实践中，我们需要结合具体问题来选择合适的算法。
五个回路溯源分析
1. 回溯法的基本概念
用回溯法求解问题时，应明确问题的解空间，问题的解空间至少应包含问题的一个最优解，确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间，这个开始结点成为活结点，同时成为当前的扩展结点，在当前扩展结点处，如果在当前扩展结点处不能在向纵深方向移动，则当前扩展结点就成为死结点，此时应往回移动（回溯）至最近的一个活结点处，并让这个活结点成为当前的扩展结点，回溯法以这种工作方式递归的在解空间中搜索，直至找到所要求的的解或解空间中已无活结点时为止
2. 回溯法搜索空间树时，通常采用两种策略来避免无效的搜索，提高回溯法的搜索效率
是用约束函数在扩展结点剪去不满足约束的子树
是用限界函数剪去得不到最优解的子树，这两类函数称之为剪枝函数
3. 回溯法的基本算法框架
递归回溯
迭代回溯
子集树算法框架
排列树算法框架
5. 采用回溯法解决的经典问题
转载问题
批处理作业二调度问题
符号三角形问题
n后问题
0-1背包问题
最大团问题
图的m着色问题
旅行售货员问题
圆排列问题
电路板排列问题
连续邮资问题。
一、实验目的1. 理解回溯法的概念和原理；2. 掌握回溯法的基本算法设计思想；3. 通过实例验证回溯法的正确性和效率；4. 深入了解回溯法在实际问题中的应用。
二、实验内容1. 实验一：八皇后问题2. 实验二：0/1背包问题3. 实验三：数独游戏三、实验原理回溯法是一种在解空间树中搜索问题解的方法。
其基本思想是：从问题的起始状态开始，通过尝试增加约束条件，逐步增加问题的解的候选集，当候选集为空时，表示当前路径无解，则回溯到上一个状态，尝试其他的约束条件。
通过这种方法，可以找到问题的所有解，或者找到最优解。
四、实验步骤与过程1. 实验一：八皇后问题（1）问题描述：在一个8x8的国际象棋棋盘上，放置8个皇后，使得任意两个皇后都不在同一行、同一列和同一斜线上。
（2）算法设计：- 定义一个数组，用于表示棋盘上皇后的位置；- 从第一行开始，尝试将皇后放置在第一行的每一列；- 检查当前放置的皇后是否与之前的皇后冲突；- 如果没有冲突，继续将皇后放置在下一行；- 如果冲突，回溯到上一行，尝试下一列；- 重复上述步骤，直到所有皇后都放置完毕。
（3）代码实现：```pythondef is_valid(board, row, col):for i in range(row):if board[i] == col or abs(board[i] - col) == abs(i - row):return Falsereturn Truedef solve_n_queens(board, row):if row == len(board):return Truefor col in range(len(board)):if is_valid(board, row, col):board[row] = colif solve_n_queens(board, row + 1):return Trueboard[row] = -1return Falsedef print_board(board):for row in board:print(' '.join(['Q' if col == row else '.' for col in range(len(board))]))board = [-1] 8if solve_n_queens(board, 0):print_board(board)2. 实验二：0/1背包问题（1）问题描述：给定一个背包容量为W，n件物品，每件物品的重量为w[i]，价值为v[i]，求在不超过背包容量的前提下，如何选取物品，使得总价值最大。
回溯法-数据结构与算法定义：回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
1、回溯法适用：有许多问题，当需要找出它的解集（全部解）或者要求回答什么解是满足某些约束条件的最优解时，往往要使用回溯法。
2、有组织的穷举式搜索：回溯法的基本做法是搜索或者有的组织穷尽搜索。
它能避免搜索所有的可能性。
即避免不必要的搜索。
这种方法适用于解一些组合数相当大的问题。
3、搜索解空间树：回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。
如果肯定不包含（剪枝过程），则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
为了实现回溯，我们先弄明白以下两个问题：1）首先应该明确问题的解空间。
2）其次是组织解空间以便它能用以被搜索到。
这个空间必须至少包含一个解（可能是最优的）。
一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以看作是由若干个小的决策组成。
很多时候它们构成一个决策序列。
解决一个问题的所有可能的决策序列构成该问题的解空间。
解空间中满足约束条件的决策序列称为可行解。
一般说来，解任何问题都有一个目标，在约束条件下使目标值达到最大（或最小）的可行解称为该问题的最优解。
在解空间中，前k项决策已经取定的所有决策序列之集称为k定子解空间。
0定子解空间即是该问题的解空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
解空间的确定与我们对问题的描述有关。
如何组织解空间的结构会直接影响对问题的求解效率。
这是因为回溯方法的基本思想是通过搜索解空间来找到问题所要求的解。
一般地，可以用一棵树来描述解空间，称为解空间树。
回溯法概述与穷举的“笨拙”搜索相比，回溯法则是一种“聪明”的求解效益更高的搜索法。
下面介绍回溯设计及其应用，体会回溯法相对于穷举的特点与优势。
回溯的概念有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往使用回溯法。
回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。
因此，回溯法可以形象地概括为“向前走，碰壁回头”。
回溯法的基本做法是试探搜索，是一种组织得井井有条的、能避免一些不必要搜索的穷举式搜索法。
回溯法在问题的解空间树中，从根结点出发搜索解空间树，搜索至解空间树的任意一点，先判断该结点是否包含问题的解；如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其父结点回溯；否则，进入该子树，继续搜索。
从解的角度理解，回溯法将问题的候选解按某种顺序进行枚举和检验。
当发现当前候选解不可能是解时，就选择下一个候选解。
在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。
倘若当前候选解除了不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。
如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。
与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。
因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题。
5.1.2 回溯描述1．回溯的一般方法下面简要阐述回溯的一般方法。
回溯求解的问题P，通常要能表达为：对于已知的由n元组(x1,x2,…,x n)组成的一个状态空间E={(x1,x2,…,x n)|x i∈s i,i=1,2,…,n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。
其中s i是分量x i的定义域，且|s i|有限，i=1,2,…,n。
称E中满足D的全部约束条件的任一n元组为问题P的一个解。
解问题P的最朴素的方法就是穷举法，上面已经作了介绍，即对E中的所有n元组逐一地检验其是否满足D的全部约束，若满足，则为问题P的一个解。
显然，其计算量是相当大的。
对于许多问题，所给定的约束集D具有完备性，即i元组(x1,x2,…,x i)满足D中仅涉及到x1,x2,…,x i的所有约束，意味着j(j<i)元组(x1,x2,…,x j)一定也满足D中仅涉及到x1,x2,…,x j的所有约束，i=1,2,…,n。
换句话说，只要存在0≤j≤n-1，使得(x1,x2,…,x j)违反D中仅涉及到x1,x2,…,x j的约束之一，则以(x1,x2,…,x j)为前缀的任何n元组(x1,x2,…,x j,x j+1,…,x n)也一定违反D中仅涉及到x1,x2,…,x j的一个约束，n≥i＞j。
因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组(x1,x2,…,x j)违反D中仅涉及x1,x2,…,x j的一个约束，就可以肯定，以(x1,x2,…,x j)为前缀的任何n元组(x1,x2,…,x j,x j+1,…,x n)都不会是问题P的解，因而就不必去搜索它们，即省略了对部分元素(x j+1,…,x n)的操作与测试。
回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比穷举法效率更高的算法。
2. 4皇后问题的回溯实施为了具体说明回溯的实施过程，先看一个简单实例。
如何在4×4的方格棋盘上放置4个皇后，使它们互不攻击，即任意两个皇后不允许处在同一横排，同一纵列，也不允许处在同一与棋盘边框成45°角的斜线上。
图5-1所示为应用回溯的实施过程，其中方格中的×表示试图在该方格放置一个皇后,但由于受前面已放置的皇后的攻击而放弃的位置。
图5-1 4皇后问题回溯实施求解图（a）为在第1行第1列放置一个皇后的初始状态。
图（b）中，第2个皇后不能放在第1、2列，因而放置在第3列上。
图（c）中，表示第3行的所有各列均不能放置皇后，则返回第2行，第2个皇后需后移。
图（d）中，第2个皇后后移到第4列，第3个皇后放置在第2列。
图（e）中，第4行的所有各列均不能放置皇后，则返回第3行；第3个皇后后移的所有位置均不能放置皇后，则返回第2行；第2个皇后已无位可退，则返回第1行；第1个皇后需后移。
图（f）中，第1个皇后后移至第2格。
图（g）中，第2个皇后不能放在第1，2，3列，因而放置在第4列上。
图（h）中，第3个皇后放在第1列；第4个皇后不能放置1，2列，于是放置在第3列。
这样经以上回溯，得到4皇后问题的一个解：2413。
继续以上的回溯探索，可得4皇后问题的另一个解：3142。
3．回溯算法框架描述(1) 回溯描述对于一般含参量m,n的搜索问题，回溯法框架描述如下：输入正整数n,m,(n≥m)i=1;a[i]=<元素初值>;while (1){for(g=1,k=i-1;k>=1;k--)if( <约束条件1> ) g=0; // 检测约束条件,不满足则返回if(g && <约束条件2>)printf(a[1-m]); // 输出一个解if(i<n && g) {i++;a[i]=<取值点>;continue;}while(a[i]==<回溯点> && i>1) i--; // 向前回溯if(a[i]==n && i==1) break; // 退出循环，结束else a[i]=a[i]+1;}具体求解问题的试探搜索范围与要求不同，在应用回溯设计时，需根据问题的具体实际确定数组元素的初值、取值点与回溯点，同时需把问题中的约束条件进行必要的分解，以适应上述回溯流程。
其中实施向前回溯的循环while(a[i]==<回溯点> && i>1) i--;是向前回溯一步，还是回溯两步或更多步，完全根据a[i]是否达到回溯点来确定。
例如，回溯点是n，i=6，当a[6]=n时回溯到i=5；若a[5]=n时回溯到i=4；依此类推，到a[i]达到回溯点则停止。
图5-1所示的4皇后问题迭代回溯过程描述为：n=4;i=1;a[i]=1;while (1){g=1;for(k=i-1;k>=1;k--)if(a[i]=a[k] && abs(a[i]-a[k])=i-k)g=0; // 检测约束条件,不满足则返回if(g && i==4)printf(a[1-4]); // 输出一个解if(i<n && g) {i++;a[i]=1;continue;}while(a[i]==n && i>1) i--; // 向前回溯if(a[i]==n && i==1) break; // 退出循环结束else a[i]=a[i]+1;}以上回溯体现在迭代式i=i-1，因而又称为迭代回溯。
此外，递归也能实现回溯。
（2）递归回溯int put(int k){ int i,j,u;if( k<=问题规模 ){ u=0;if( <约束条件> )u=1; // 当k时不可操作if(u==0) // 当k时可操作{ if(k==规模) // 若已满足规模，则打印出一个解printf( <一个解> );else put(k+1); // 调用 put(k+1)}}}在调用put(k)时，当检测约束条件知不可操作（记u=1），即再往前不可能得解，此时当然不可能输出解，也不调用put(k+1)，而是回溯，返回调用put(k)之处。
这就是递归回溯的机理。
如果是主程序调用put(1)，最后返回到主程序调用put(1)的后续语句，完成递归。
图5.1所示的4皇后问题迭代回溯过程描述为：int put(int k){ int i,j,u;if(k<=4){ for(i=1;i<=4;i++) // 探索第k行从第1格开始放皇后{ a[k]=i;for(u=0,j=1;j<=k-1;j++)if(a[k]==a[j] || abs(a[k]-a[j])==k-j )u=1; // 若第k行第i格放不下,则置u=1if(u==0) // 若第k行第i格可放,则检测是否满4行 { if(k==4) // 若已放满到4行时，则打印出一个解{ s++; printf(" ");for (j=1;j<=4;j++)printf("%d",a[j]);}else put(k+1); // 若没放满4行,则放下一行 put(k+1)}}}}4. 回溯法的效益分析应用回溯设计求解实际问题，由于解空间的结构差异，很难精确计算与估计回溯产生的结点数，因此回溯法的复杂度是分析回溯法效率时遇到的主要困难。
回溯法产生的结点数通常只有解空间结点数的一小部分，这也是回溯法的计算效率大大高于穷举法的原因所在。
回溯求解过程实质上是一个遍历一棵“状态树”的过程，只是这棵树不是遍历前预先建立的。
回溯算法在搜索过程中，只要所激活的状态结点满足终结条件，应该把它输出或保存。
由于在回溯法求解问题时，一般要求输出问题的所有解，因此在得到结点后，同时也要进行回溯，以便得到问题的其他解，直至回溯到状态树的根且根的所有子结点均已被搜索过为止。
组织解空间便于算法在求解集时更易于搜索，典型的组织方法是图或树。
一旦定义了解空间的组织方法，这个空间即可从开始结点进行搜索。
回溯法的时间通常取决于状态空间树上实际生成的那部分问题状态的数目。
对于元组长度为n 的问题，若其状态空间树中结点总数为n!，则回溯算法的最坏情形的时间复杂度可达O(p(n)n!)；若其状态空间树中结点总数为2n，则回溯算法的最坏情形的时间复杂度可达O(p(n)2n )，其中p(n)为n 的多项式。
对于不同的实例，回溯法的计算时间有很大的差异。
对于很多具有大n 的求解实例，应用回溯法一般可在很短的时间内求得其解，可见回溯法不失为一种快速有效的算法。
对于某一具体实际问题的回溯求解，常通过计算实际生成结点数的方法即蒙特卡罗方法（Monte carlo ）来评估其计算效率。
蒙特卡罗方法的基本思想是在状态空间树上随机选择一条路径(x 0,x 1,…,x n-1)，设X 是这一路径上部分向量(x 0,x 1,…,x k-1)的结点，如果在Ｘ处不受限制的子向量数是m k ，则认为与X 同一层的其他结点不受限制的子向量数也都是m k 。
