cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release./GraphColoring <limit_time> <seed> [tabu_iterations]
测试用例请使用标准输入传入程序。
参数说明：
limit_time：程序的总运行时间上限，单位为秒。seed：随机数种子。不同种子可能导致明显不同的搜索路径和运行时间。tabu_iterations：每次 Tabu Search 的最大迭代次数，默认为80000。
tabu_iterations 会直接影响运行时间和求解效果：
- 迭代次数越小，单次局部搜索结束越快，总体运行时间通常更短。
- 迭代次数越大，单次局部搜索探索得更充分，更容易找到更好的解，但运行时间通常也会增加。
- 对于较容易的颜色数，适当减小该参数通常仍能较快找到可行解。
- 对于接近最优或更困难的颜色数，过小的迭代次数可能导致搜索不充分，成功率下降，或者需要更多代才能找到可行解。
建议：
- 如果目标是快速得到一个可行解，可以先从较小的
tabu_iterations开始测试。 - 如果目标颜色数较紧，或者多次运行仍未找到可行解，可以逐步增大
tabu_iterations。 - 建议固定实例和颜色数后，使用多个随机种子测试平均运行时间，而不是只看单次结果。
例如，instance/5.txt 在当前实验中：
48色使用8000次迭代，5 个随机种子的平均耗时约为20.858s。49色使用4000次迭代，5 个随机种子的平均耗时约为1.414s。
这说明不同颜色数对应的合适迭代次数可能不同；迭代次数并不是越大越好，而是需要在运行时间和求解效果之间权衡。
下表中的 Iter_TC 表示该测试所使用的单次 Tabu Search 最大迭代次数，对应命令行参数 tabu_iterations。
| instance | k | Iter_TC | time |
|---|---|---|---|
| 0 | 5 | Tabucol | 0.001 s |
| 1 | 17 | Tabucol | 0.114 s |
| 2 | 44 | Tabucol | 0.004 s |
| 3 | 8 | Tabucol | 0.032 s |
| 4 (dsjc250.5) | 28 | 6000 | 0.478 s |
| 5 (dsjc500.5) | 49 | 8000 | 2.028 s |
| 48 | 8000 | 35.434 s | |
| 6 (dsjc1000.5) | 83 | 40000 | 188.3 s |
| 7 (C2000.5) | 146 | 140000 | 225.9 min |
| 8 | 409 | 140000 | 20.9 min |
| 9 (C4000.5) | 270 | 140000 | 775 min |
所有算例的节点从 0 开始连续编号.
第一行给出 3 个由空白字符分隔的整数, 分别表示节点数 N, 无向边数 E (有向边数为 2E), 以及参考颜色数 C (相对容易求得可行解, 非最优颜色数). 接下来连续 E 行, 每行包含 2 个由空白字符分隔的整数, 表示一条无向边的两个端点.
例如, 以下算例文件表示节点数为 4, 无向边数为 3, 参考颜色数为 2; 其中: 节点 0 分别与 1, 2, 3 相邻.
4 3 2
0 1
0 2
3 0
- L. Moalic and A. Gondran, “Variations on memetic algorithms for graph coloring problems,” Journal of Heuristics, vol. 24, no. 1, pp. 1–24, 2018, doi: 10.1007/s10732-017-9354-9.