解空间

csuzhucong

已于 2023-10-09 14:22:05 修改

阅读量1.5w

点赞数 11

文章标签：算法

于 2021-01-07 00:21:37 首次发布

本文链接：https://blog.csdn.net/nameofcsdn/article/details/111885131

版权

本文深入探讨了解空间与对象空间的概念及其关系，特别是在算法设计中的应用。解空间是问题所有可能解的集合，而对象空间则是问题本身的研究范围。两者关系多样，如相等、子空间、判定生成等。通过二分法、搜索、动态规划和贪心算法的实例，阐述了解空间结构的相对性和重要性，并总结了各类算法的解空间特点。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

4，解空间是对象空间（或其子空间）的扩张域

解空间是对象空间由判定生成的空间（正向判定）

解空间是对象空间由判定生成的空间（正向判定）

解空间是对象空间由判定生成的空间（反向判定）

一，解空间

一个问题的解空间是它的所有可能的解构成的集合。

理论上来讲，任何能想到的数据结构，都可能是某个问题的解空间。

本文主要针对的是搜索类问题，即在一个空间S内寻找一个满足特定条件的点。

而对于贪心类问题和动态规划类问题，大致可以描述为，在一个空间S内任取一点A，求出f(A)，其中f并不是具有表达式的函数，而是问题描述的复杂映射。

二，解空间的相对性

“可能的解”这个概念具有相对性，对应的，解空间的范围也可大可小。

比如，求100到10000之间有多少素数，解空间既可以是100到10000之间的所有整数，也可以是100到10000之间的所有奇数。

稍微复杂点的例子：力扣254. 因子的组合

这个题目的一种思路是先做因式分解，难点在于如何分组去重，解空间是若干个因子的所有可能的分组方式。

另外一种思路是直接用整数进行搜索，解空间是所有递增的有限整数序列。

三，解空间结构

解空间的空间结构，叫解空间结构，比如数组、链表、树等等。

四，解空间结构的相对性

对于一个问题来说，不同的算法可能有不同的解空间结构，即使两个算法所用到的解的集合是相同的。

比如，查找1到9999里面，有多少个数的各位之和是9。

如果采用顺序查找，那么解空间结构是数组，从1到9999，如果采用树形查找，那么解空间结构是一颗5层的字典树。

五，对象空间

问题的研究对象本身所处的空间，叫对象空间。

一般来说，对象空间是最直观的一个概念，也是问题的内禀属性，与算法无关，而解空间是依赖于算法的。

六，对象空间和解空间的关系

对象空间和解空间的关系有很多种，根据多年ACM的经验，我觉得有如下几种常见的关系：

1，对象空间等于解空间

比如输入一个数组，找出其中最大的数。

对象空间是数组本身，解空间也是数组本身。

2，解空间是对象空间的子空间

比如输入n个数，找出其中的所有素数。

对象空间是n个数，解空间是其中的所有素数。

3，解空间是对象空间的子空间构成的集合

比如迷宫问题，对象空间是一个矩阵，解空间是所有可能的路径构成的集合。

再比如N皇后问题，对象空间是一个矩阵，解空间是每行每列选一个皇后的所有N！种选取方式构成的集合。

PS：上面这2种的区别在于，一个是个体的独立判定，一个的集体综合判定。

4，解空间是对象空间（或其子空间）的扩张域

比如输入n个实数，求他们的平均数。

对象空间是n个实数，解空间是全体实数。

5，解空间是对象空间由判定生成的空间

正向判定

比如输入n个正整数，从中任选k个数，求素数个数的均值x

反向判定

比如输入n个整数，求最小的正整数k，使得从中任选k个数，素数个数的均值至少为x

PS：或许未必k越大x越大，但是题目的表述并没有问题，只要有一个数满足，肯定就会有这么一个最小的k。

七，各类算法常见解空间总结

1，二分法

二分、三分_csuzhucong的博客-CSDN博客中的典型问题：

对象空间等于解空间

HDU 2141 Can you find it?（找三个数的和，二分）

解空间是对象空间（或其子空间）的扩张域

HDU 1969 PIE（求方程的解）

解空间是对象空间由判定生成的空间（正向判定）

CSU 1984: LXX的能力值

PS：正向判定类的二分法，通俗的理解就是直接对答案进行二分，但是不像求方程的解的二分法这么直观。

2，搜索

DFS、BFS_csuzhucong的博客-CSDN博客中的典型问题：

对象空间等于解空间

力扣OJ 111. 二叉树的最小深度

解空间是对象空间的子空间

CSU 1660 K-Cycle

解空间是对象空间的子空间构成的集合

HDU 1016 Prime Ring Problem（全排列问题)，对象空间是全体全排列，解空间是其中满足条件的排列。

HDU 1455 Sticks（组合）

HDU 2102 A计划（迷宫）

HDU 2553 N皇后问题

SGU454 Kakuro

POJ 3126 Prime Path（素数变换路径）

解空间是对象空间由判定生成的空间（正向判定）

HDU 1241 Oil Deposits（连通块的数量）

解空间是对象空间由判定生成的空间（反向判定）

CSU 1224: ACM小组的古怪象棋

3，动态规划

对于搜索类问题来说，对象空间很明确，解空间不那么明确，对象空间和解空间比较好区分。

但是对于动态规划来说，基本不区分对象空间和解空间了，所以我在其他场合（包括博客）所提到的动态规划的解空间，可能直接就是对象空间。

而在某些场合，我又用动态规划的良基集合来描述它，参考：区间DP 区间DP_csuzhucong的博客-CSDN博客

动态规划按照对象空间是否等于解空间，可以简单分为两类：

对象空间等于解空间

数列DP 数列DP_csuzhucong的博客-CSDN博客

区间DP 区间DP_csuzhucong的博客-CSDN博客

树形DP 树形DP_csuzhucong的博客-CSDN博客

对象空间不等于解空间

非对称DP 非对称DP_csuzhucong的博客-CSDN博客

数位DP 数位DP_csuzhucong的博客-CSDN博客_数位dp

4，贪心

同上，贪心和动态规划一样，都依赖于最优子结构性质，所以都在建立在良基集合之上。