第一章 动态规划基础理论
#
1.1 动态规划基本概念
#
- 最优子结构性质
- 重叠子问题性质
- 状态转移方程
- 记忆化搜索与递推实现
1.2 经典动态规划模型
#
- 背包问题系列
- 最长公共子序列
- 最短路径问题
- 区间动态规划
- 树形动态规划
第二章 博弈论基础
#
2.1 博弈论基本概念
#
- 博弈参与者与策略
- 收益函数与支付矩阵
- 纳什均衡
- 帕累托最优
2.2 博弈分类
#
- 合作博弈与非合作博弈
- 零和博弈与非零和博弈
- 完全信息博弈与不完全信息博弈
- 静态博弈与动态博弈
第三章 组合游戏理论
#
3.1 公平组合游戏
#
- 必胜态与必败态
- 游戏图与状态转移
- 游戏的和与分解
- 对称策略与模仿策略
3.2 经典组合游戏
#
- 取石子游戏
- Nim游戏及其变种
- 威佐夫博弈
- 巴什博奕
第四章 动态规划在博弈中的应用
#
4.1 状态设计与分析
#
- 游戏状态表示方法
- 状态空间压缩技巧
- 状态转移优化策略
- 边界条件处理
4.2 典型博弈问题的DP解法
#
第五章 博弈树与极小化极大算法
#
5.1 博弈树构建
#
- 节点类型与层次结构
- 分支因子与深度
- 剪枝策略
- 启发式评估函数
5.2 搜索算法
#
- 极小化极大算法
- Alpha-Beta剪枝
- 蒙特卡洛树搜索
- 迭代深化搜索
第六章 特殊类型博弈的DP解法
#
6.1 图论博弈
#
- 有向图游戏
- 无环图博弈
- 循环图处理
- 图博弈的必胜策略
6.2 数学博弈
#
第七章 实际应用与案例分析
#
7.1 棋类游戏分析
#
- 围棋的局部定式
- 象棋的残局分析
- 五子棋的必胜策略
- 跳棋的战术规划
7.2 电子游戏AI设计
#
- 回合制游戏AI
- 实时策略游戏AI
- 卡牌游戏AI
- 角色扮演游戏AI
第八章 高级专题与前沿发展
#
8.1 强化学习与博弈
#
- Q-learning在博弈中的应用
- 深度强化学习
- 多智能体强化学习
- 对抗性学习
8.2 计算复杂性分析
#
- 博弈问题的复杂度分类
- PSPACE完全问题
- EXPTIME完全问题
- 近似算法设计
第九章 实践技巧与优化方法
#
9.1 代码实现技巧
#
- 状态压缩技术
- 记忆化搜索优化
- 并行计算应用
- 缓存策略设计
9.2 性能分析与调优
#
- 时间复杂度分析
- 空间复杂度优化
- 算法选择策略
- 实际测试与验证