本项目是并行程序设计课程的优化作业，题目来自 Kaggle Santa Workshop Tour 2019。
目标是在每日人数约束下，为 5000 个家庭分配 100 天中的参观日期，最小化总成本。
本仓库强调工程实现而不是算法重构，具体为：
- 使用 C 语言实现可控的并行搜索（
pthread+ 共享全局最优） - 通过增量评分降低候选评估开销
- 保留课程最终提交版本的主体结构，并补齐关键逻辑一致性
- 中文完整题面：
docs/problem_zh.md - 速查版：
docs/problem_quickref_zh.md - 英文原题：
https://www.kaggle.com/c/santa-workshop-tour-2019https://www.kaggle.com/competitions/santa-workshop-tour-2019
simple greedy：快速生成可行解（约 50 万量级）complex greedy：更复杂的启发式初始解（约 134 万量级）
- 全量评分：
src/cost_full.c - 增量评分：
src/cost_delta.c - 预计算矩阵：
src/precompute.c
- 串行随机局部搜索：
src/search_serial.c - 并行混合搜索（simple + batch）：
src/search_thread.c
choice_9 / otherwise计分一致性修复
按“最终分配日期在原始 top-10 中的排名”计分；若不在原始 top-10，按otherwise计算。- 并行批搜索重复采样修复
batch_search每批候选内保证family索引唯一。 - 跨平台休眠与线程边界保护
新增 Windows/Linux 休眠封装；线程数超过统计上限时自动裁剪并给出提示。
来源：课程报告.pdf（课程最终提交，日期 2025-07-16）。
| 线程数 | 分数 |
|---|---|
| 初始（未优化） | 1,349,619 |
| 2 线程 | 171,243 |
| 4 线程 | 135,446 |
| 8 线程 | 134,133 |
| 线程数 | 分数 |
|---|---|
| 初始（未优化） | 502,487 |
| 2 线程 | 141,748 |
| 4 线程 | 123,922 |
| 8 线程 | 122,269 |
趋势结论：线程数增加后，搜索吞吐与最终分数均有明显改善；4 到 8 线程仍有收益，但边际变小。
Linux/macOS（有 make）：
makeWindows MinGW（无 make 时可直接编译）：
gcc -Wall -Wextra -std=c99 -I./include -O2 src/*.c -lm -lpthread -o santa19.exe生成基线解（只验证，不做搜索）：
./santa19.exe --validate --greedy simple多线程优化（示例：4 线程、300 秒）：
./santa19.exe --greedy simple -t 4 -s 300输出：submission.csv
src/：核心 C 代码include/：头文件data/：输入数据与历史提交文件docs/：题目中文文档与速查文档comparison/：串行/并行实验对比图与可视化脚本validate_simple_based_visualization/：基线验证可视化脚本与结果visualization_performance/：性能分析与综合可视化结果课程报告.pdf：课程最终报告（历史结果来源）
- 这是启发式搜索工程实现，不保证全局最优。
- 当前仓库已做后续修复，重新运行时分数可能与历史提交略有差异。
- README 中表格分数均为“课程最终提交历史结果”，非本次修复后的重新基准。
- 历史数据统一来源：
课程报告.pdf。 - 规则解释以 Kaggle 官方英文页面为准。