解空间的算法

‘壹’ 解空间的维数和向量空间的维数算法一样吗

维数计算方法都是一样的，不过两个题目表达的不是同一个意思。

向量组span的空间维数是向量组中最大线性无关的向量个数，你可以认为是向量组对应矩阵的秩;而线性方程组解空间的维数指的是对应基础解系中所含的最大线性无关的向量个数，换句话说，这时候要判断的是span出解空间的向量组中的最大线性无关的向量个数，而不是拿系数矩阵列向量span出的空间维数判断，一个是零空间/核空间，一个是列空间/值域，表达的根本不是一个意思。

线性代数中，向量空间的维数和解空间维数没有区别。解空间也是向量空间，是针对线性方程组而言的解空间，维数就是基础解系中线性无关的向量数。

而向量的维数指的向量分量的个数。用大白话来讲就是描述一个向量需要用到好几个元素，有几个元素这个向量就有几维。比如最直观的三维向量，分别用x、y、z描述，所以这个向量就是三维的。

‘贰’ 分支限界法

分支限界法是一种在解空间树中搜索最优解的算法。基本思想是结合广度优先遍历（BFS）或最佳优先搜索方式，并利用部分最优解的信息进行剪枝，以提升搜索效率。在每个活结点处，计算一个函数值（优先值），然后根据这些函数值选择最有利的节点进行扩展，从而加速搜索过程，找出最优解。与回溯法相比，分支限界法专注于尽快找到一个满足约束条件的解，而回溯法则尝试找出满足所有约束条件的所有解。分支限界法采用宽度优先或最佳优先搜索方式，而回溯法则采用深度优先搜索。在扩展结点时，分支限界法会一次性产生所有儿子结点，与回溯法不同。由于分支限界法要求较大的存储空间，当内存有限时，回溯法可能有更高的成功可能性。

分支限界法的求解步骤包括：定义解空间、确定解空间的树结构、按照BFS等方法搜索、删除不可能导出最优解的结点、将剩余结点加入活动表（队列）中、选择结点进行扩展，直到活动表为空。活结点的扩展方式有两种：先进先出队列（FIFO）和优先队列。在优先队列中，可以根据耗费或收益的大小来选择扩展结点，以加速搜索过程。

分支限界法在实际应用中有多种示例，如判断重量是否超过背包容量来确定是否为死节点。此外，分支限界法也常用于解决8谜问题、装载问题等。在装载问题中，解空间树描述了各种装载方案，通过分支限界法搜索，最终找到最优装载方案。

‘叁’ 五大基本算法——回溯法

回溯法是一种选优搜索法（试探法）。

基本思想：将问题P的状态空间E表示成一棵高为n的带全有序树T，把求解问题简化为搜索树T。搜索过程采用 深度优先搜索 。搜索到某一结点时判断该结点是否包含原问题的解，如果包含则继续往下搜索，如果不包含则向祖先回溯。

通俗来说，就是利用一个树结构来表示解空间,然后从树的根开始深度优先遍历该树，到不满足要求的叶子结点时向上回溯继续遍历。

几个结点：
扩展结点：一个正在产生子结点的结点称为扩展结点
活结点：一个自身已生成但未全部生成子结点的结点
死结点：一个所有子结点已全部生成的结点

1、分析问题，定义问题解空间。

2、根据解空间，确定解空间结构，得 搜索树 。

3、从根节点开始深度优先搜索解空间（利用 剪枝 避免无效搜索）。

4、递归搜索，直到找到所要求的的解。

1、子集树
当问题是：从n个元素的集合S中找出满足某种性质的子集时，用子集树。
子集树必然是一个二叉树。常见问题：0/1背包问题、装载问题。

遍历子集树时间复杂度：O（2^n）

2、排列树
当问题是：确定n个元素满足某种排列时，用排列数。常见问题：TSP旅行商问题，N皇后问题。

遍历排列树时间复杂度：O（n!）

通俗地讲，结合Java集合的概念，选择哪种树其实就是看最后所得结果是放入一个List（有序）里，还是放入一个Set（无序）里。

剪枝函数能极大提高搜索效率，遍历解空间树时，对于不满足条件的分支进行剪枝，因为这些分支一定不会在最后所求解中。

常见剪枝函数：

约束函数（对解加入约束条件）、限界函数（对解进行上界或下界的限定）

满足约束函数的解才是可行解。

1、0/1背包问题

2、TSP旅行商问题

3、最优装载问题

4、N-皇后问题

具体问题可网络详细内容。