本仓库记录深圳大学“算法设计与分析”课程一个学期的实验与编程学习过程，学习时间为 2025—2026 学年第二学期。内容按课程知识递进顺序整理为六次实验，涉及 Python、C++、算法复杂度分析、分治、回溯、动态规划、并查集和最大流。
本仓库主要用于保存课程学习成果。代码基本保留完成练习和实验时的原始状态，没有按照生产项目标准重新设计或重构，也不保证在所有新版本环境中直接运行。
| 目录 | 实验主题 | 核心知识点 | 主要入口 |
|---|---|---|---|
| 01-实验1-AI推荐系统Top-k优化 | 推荐系统中的 Top-k 查询 | 余弦相似度、排序、最小堆、稀疏向量、复杂度分析 | code.py、ConsoleApplication1.cpp |
| 02-实验2-最近点对与分治法 | 平面最近点对 | 蛮力法、分治法、递归、性能比较、可视化 | closest_pair0.py |
| 03-实验3-地图着色与回溯法 | 图着色问题 | 回溯、约束检查、MRV、前向检查、剪枝 | main.py |
| 04-实验4-鸡蛋掉落与动态规划 | 鸡蛋掉落问题 | 状态设计、状态转移、最坏情况最优化 | 实验报告 |
| 05-实验5-图的桥与并查集 | 无向图中的桥 | DFS、连通分支、生成森林、并查集、路径压缩 | bridge.cpp |
| 06-实验6-棒球淘汰与最大流 | 棒球淘汰问题 | 流网络建模、增广路、Edmonds–Karp、最大流最小割 | 1.cpp |
- 实验 1 从实际推荐场景出发，比较全量排序、部分选择和最小堆等方案，建立算法效率与数据规模之间的联系。
- 实验 2 使用最近点对问题练习分治设计，将一个几何问题拆分为规模更小的子问题。
- 实验 3 进入组合搜索问题，使用回溯法解决图着色，并加入变量选择和约束传播等剪枝策略。
- 实验 4 使用动态规划保存子问题结果，通过状态转移最小化鸡蛋掉落问题的最坏试验次数。
- 实验 5 转向图论算法，比较按定义逐边验证的基准算法与结合并查集的高效算法。
- 实验 6 将比赛结果分配建模为流网络，使用最大流判断球队是否已被淘汰。
algorithm-design-and-analysis/
├── README.md
├── .gitignore
├── 01-实验1-AI推荐系统Top-k优化/
├── 02-实验2-最近点对与分治法/
├── 03-实验3-地图着色与回溯法/
├── 04-实验4-鸡蛋掉落与动态规划/
├── 05-实验5-图的桥与并查集/
└── 06-实验6-棒球淘汰与最大流/
每个实验目录均包含一份导航 README，并按实际材料划分为 src/、report/、results/、data/ 或 notes/。并非所有实验都拥有这些子目录；例如实验 4 的原始文件中没有发现独立源码，因此只保留报告，没有重新补写实现。
- 算法分析：时间复杂度、理论效率与实测效率比较
- 基础策略：蛮力法、排序、堆与 Top-k 查询
- 递归策略：分治法与最近点对
- 搜索策略：回溯、剪枝、MRV 和前向检查
- 动态规划：状态定义、边界条件和状态转移
- 图论算法：DFS、连通性、桥、并查集和路径压缩
- 网络流：残量网络、增广路、Edmonds–Karp 和最大流最小割
- 想了解整个课程的学习顺序，可以依次阅读六个实验目录的 README。
- 想查看可执行逻辑，可以从各实验索引中的“主要入口”开始。
- 想了解当时的问题描述、测试过程和实验结论，应以
report/中的原始报告为准。 - 报告中的环境、结果和运行说明反映课程完成时的情况，本次整理没有重新运行实验，也没有重做测试。
仓库保留本人或课程小组完成的源码、报告、自制数据表、实验结果图和必要数据。教师 PPT、教材、期末复习资料、报告模板、同学源码备份、IDE 配置、编译产物、缓存和完全重复的副本未纳入。部分报告由课程小组共同完成，报告中保留了原始署名信息。
- 黄瑜
- GitHub：@Kevin87654