本文主要是介绍南开大学软件学院2021年秋季学期研究生算法课程（复习）算法设计思想和状态空间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
可计算性与可计算问题
- 判定问题Decision problem：判断一个问题的解是否存在
- 优化问题Optimization problem：找到问题的最优解
- 组合优化问题
- 连续优化问题
一个重要的转化：任何优化问题都可以表示为一个判定问题
算法
求解问题的一系列数学或计算机操作（输入➡算法➡输出）
状态与状态空间
状态State：对可计算问题的一种建模
状态转移State transition：问题中不同状态的转化关系
状态空间State space：状态（点）和状态转移（边）构造的图
状态变量State variable：求解问题过程中，对于一系列状态变化的变量建模
价值函数Cost function：用以衡量当前状态的一个状态到值的映射，该值会伴随着状态转移而更新，该值可以是：布尔值，整数，实数等等
翻转开关问题：
有一个4✖4的灯阵，每个灯上均有一个开关，每次拨动开关都会使当前灯和相邻灯的开关状态改变。请设计某种算法，判断给出某种开关图案是否可以通过操作开关使全部灯都打开？
状态压缩State compression，State encoding，Bitmask
- 利用二进制等，压缩状态表示时的存储空间占用（比如上面这个4✖4矩阵）
- 利用位运算等技巧，加速状态转移计算时的时间消耗（比如乘法运算变成位运算）
- 对于上例，只要16个二进制位即可，但是转移会很复杂
状态哈希Hashing
可计算问题的本质
- 判别问题：判断初始状态与目标状态是否可达
- 优化问题：计算从初始状态转移至目标状态的最优价值
搜索算法
深度优先搜索DFS
- 应用场景：判断是否存在解或对所有可能性计数
- 实现：递归或栈
- 主要瓶颈：运行时间和递归额外开销
广度优先搜索BFS
- 应用场景：计算到达目标状态的最少转移次数
- 实现：队列
- 主要瓶颈：内存消耗
搜索算法
埃及分数问题：
古埃及数学的分数表示十分特殊，不允许分子不为1的存在，比如2/3在古埃及数学中只能表示为1/2+1/6。请设计算法，对给定真分数a/b，请计算满足以下条件的埃及分数表示：
- 和式中的分数互不相同；
- 和式中的分数个数最少；
- 满足条件2的情况下，保留和式中最小分数最大的解。例如，19/45=1/5+1/6+1/18。
- 如何定义状态？即需被分解位和式的分数
- 深度优先搜索？不好使，因为要找最优解。
- 广度优先搜索？不好使，因为宽度时无穷大的。
搜索优化：迭代加深搜索Iteratively Deepenning DFS
- 限定DFS的搜索深度，并逐步增加
- 即搜索深度也作为状态的一部分（优化与判定间的转换）
八数码问题：
九个格子中放入了数字1到8方块，利用空位移动方块，问使数字恢复顺序所需最少移动次数？
- 如何定义状态？10^10，但这样最精简么？康托展开
- 康托展开使一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。
- 果断广度优先搜索：9！=3.6✖10^5，最坏情况下内存不够
搜索优化：双向广度优先搜索Bidirectional BFS，Meet-in-the-mid
- 可以从初始状态和目标状态同时进行广度优先搜索
- 内存优化（优化比取决于相邻状态数）
- 仅当初始状态和目标状态可以直接确定的情况
更多搜索优化技巧（取决于问题的特殊性质，见招拆招）
- 启发式搜索：A*，IDA*
- 最佳优先搜索Best-first search
- 分支界限法Branch and bound
- 剪枝Pruning
- Ad hoc方法
最关键的两个优化思路
- 用最简单的状态刻画问题，缩减状态空间
- 想尽办法避开不必要的状态转移
- 经典方法：动态规划、分治、贪心
这篇关于南开大学软件学院2021年秋季学期研究生算法课程（复习）算法设计思想和状态空间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
