Rayon TSP 求解器的 TSPLIB 数据集解析与实战指南-平芜编程栈

【免费下载链接】rayon

Rayon: A data parallelism library for Rust

项目地址：https://gitcode.com/gh_mirrors/ra/rayon

导读

本文围绕 Rayon 仓库中 rayon-demo 的旅行商问题（TSP）求解器的输入数据集展开，聚焦 data/tsp 目录下的三个 TSPLIB 格式数据文件：dj10.tsp、dj15.tsp与dj38.tsp。读完本文，你将掌握 TSPLIB 文件格式的字段语义、Rayon 解析器对格式的严格校验规则、坐标到加权图的转换过程，以及如何直接运行并行求解器并用基准测试验证最优解。

一、数据集概览：三个 TSPLIB 输入文件

根据 data/tsp/README.md 的说明，该目录存放的是 TSP 求解器的输入文件，全部采用TSPLIB 格式：

文件	节点数（DIMENSION）	来源
dj10.tsp	10	从`dj38.tsp`中选取的 10 个地点
dj15.tsp	15	从`dj38.tsp`中选取的 15 个地点
dj38.tsp	38	吉布提（Djibouti）38 个地点，源自美国国家影像与测绘局（National Imagery and Mapping Agency）数据

从文件头注释可以确认血缘关系：dj38.tsp是对早期dj89数据集的修正版本（去除了重复地点），而dj10与dj15分别是对该数据集的子集抽取，便于快速演示与测试。三个文件的坐标数值完全相同（前 10 个、前 15 个节点与dj38.tsp一一对应），只是规模不同，这为验证并行求解器的扩展性提供了天然的数据梯度。

二、TSPLIB 文件格式详解

TSPLIB 是 TSP 领域的标准数据交换格式。以 dj10.tsp 为例，完整内容如下：

NAME: dj10 COMMENT : 10 locations in Djibouti; chosen from dj38.tsp TYPE: TSP DIMENSION: 10 EDGE_WEIGHT_TYPE: EUC_2D NODE_COORD_SECTION 1 11003.611100 42102.500000 2 11108.611100 42373.888900 3 11133.333300 42885.833300 4 11155.833300 42712.500000 5 11183.333300 42933.333300 6 11297.500000 42853.333300 7 11310.277800 42929.444400 8 11416.666700 42983.333300 9 11423.888900 43000.277800 10 11438.333300 42057.222200

整个文件分为**头部（Header）与坐标段（NODE_COORD_SECTION）**两部分，各字段语义如下：

字段	含义	本仓库数据集取值
`NAME`	实例名称	`dj10`/`dj15`/`dj38`
`COMMENT`	说明性注释，可重复多行	描述地点数量与数据来源
`TYPE`	问题类型	固定为`TSP`
`DIMENSION`	节点数量	10 / 15 / 38
`EDGE_WEIGHT_TYPE`	边权计算方式	固定为`EUC_2D`（二维欧氏距离）
`NODE_COORD_SECTION`	坐标段起始标记	之后每行格式：`节点编号 X坐标 Y坐标`

坐标行格式为节点编号横坐标纵坐标，编号从 1 开始，坐标是带 6 位小数的浮点数（如1 11003.611100 42102.500000）。

三、解析器：TSPLIB 的严格校验逻辑

求解器通过 parser.rs 中的parse_tsp_data函数将文件文本解析为内存图结构。该解析器对格式要求非常严格，任何不符合规范的输入都会返回带行号的错误信息。

3.1 头部解析

头部通过正则表达式([A-Z_]+)\s*:(.*)匹配，即"大写字段名 + 冒号 + 值"，定义于 parser.rs 第 27 行。解析器对各字段的校验规则：

NAME、COMMENT：直接忽略（COMMENT可重复出现）；
TYPE：值必须精确等于TSP，否则报错expected "TSP" for TYPE；
DIMENSION：必须能解析为usize整数，且文件中必须出现，否则报错never found DIMENSION header；
EDGE_WEIGHT_TYPE：值必须精确等于EUC_2D，否则报错；
任何其他字段名：报错unknown header type。

3.2 坐标解析

坐标行通过正则表达式([0-9]+) ([0-9.]+) ([0-9.]+)匹配（parser.rs 第 29-30 行）。坐标段必须以NODE_COORD_SECTION行开头；节点编号必须为正整数（内部转换为从 0 开始的Node索引）；文件末尾只允许空行，多余内容会触发expected EOF错误。

3.3 EUC_2D 距离计算

EUC_2D表示两节点间的旅行成本为欧氏距离四舍五入到最近整数。解析器在 parser.rs 第 121-127 行的实现为：

let distance = (coord_i.0 - coord_j.0).powi(2) + (coord_i.1 - coord_j.1).powi(2); let distance = distance.sqrt(); let distance = distance.round(); let weight = Weight::new(distance as usize);

即：平方差之和开方，再round取整，最终封装为Weight类型。这正是 TSPLIB 官方文档所述 "the TSPLIB EUC_2D-norm" 的约定。

四、从坐标到加权图：内存中的图结构

解析完成后，数据被加载为 graph.rs 定义的Graph：

存储方式：num_nodes × num_nodes的一维权重矩阵，索引公式为source.index * num_nodes + target.index；
无向性表达：解析器会对所有i ≠ j的节点对计算双向边权（set_weight(i, j)与set_weight(j, i)），因此内存中是完全无向图；
无边的标记：Weight::max()（即usize::MAX）表示节点间不存在边，edge_weight据此返回Option<Weight>；
边集枚举：edges(source)迭代器惰性产出所有可达的Edge { source, target, weight }。

Weight类型定义于 weight.rs，是一个包装usize的新类型（newtype），支持加法、减法与比较运算，并可通过to_priority()将权重映射为优先级——权重越小、优先级越高（usize::MAX - weight），供搜索时决定先扩展哪条路径。

五、运行 TSP 求解器

5.1 命令用法

TSP 子命令的完整用法定义在 mod.rs 的 USAGE 常量：

Usage: tsp bench [--seq-threshold N] [--from N] <datafile>

仓库文档推荐的实际运行命令（在仓库根目录执行）：

cargo run --release -- tsp bench data/tsp/dj15.tsp --seq-threshold 8

5.2 参数说明

参数	默认值	说明
`bench`	必填	运行基准搜索并打印耗时
`<datafile>`	必填	TSPLIB 格式的输入文件路径
`--seq-threshold N`	`10`	剩余节点数小于等于 N 时回退到顺序搜索；N 越小并行度越高
`--from N`	`0`	搜索起始节点索引（0 起始），不能超过节点总数

其中--seq-threshold是控制并行度的核心旋钮：剩余节点多时并行分裂搜索空间，剩余节点少时转为顺序穷举，以降低任务调度开销。

5.3 输出格式

运行后输出示例（结构与 mod.rs 的run_solver对应）：

Graph size : 15 nodes. Seq threshold: 8 nodes. Total search time: 123.456ms Cheapest path cost: 3990 Cheapest path: 0 1 3 2 4 6 8 7 5 9 10 ...

程序依次打印图规模、顺序回退阈值、总搜索耗时、最优路径总权重（整数欧氏距离和）以及最优访问顺序。

六、基准测试：数据文件的最优解验证

bench.rs 内置了对dj10.tsp的验证基准，将求解结果与已知最优解断言比对，是"数据文件 + 求解器"正确性的完整闭环证据：

run_dir( b, "dj10.tsp", 4, 2577, vec![0, 1, 3, 2, 4, 6, 8, 7, 5, 9, 0], );

即：对 10 节点实例、顺序回退阈值 4 时，最优路径总权重必须等于 2577，最优路径为0 → 1 → 3 → 2 → 4 → 6 → 8 → 7 → 5 → 9 → 0。注释还提示该配置下每次运行会派生约6! = 720个并行任务，足以压测 Rayon 的任务调度能力。

七、并行求解原理：分支限界与 rayon::scope

了解数据格式后，再看求解器如何消费这些数据。搜索由 solver.rs 的search_from发起，核心并行机制在 step.rs：

统一入口：search_from将初始前缀（仅含起始节点）压入优先队列，然后调用rayon::scope(|s| step::step(s, self))进入并行迭代；
分裂或回退（step）：每次取出一个前缀，若剩余节点数<= seq_threshold则调用solve_tour_seq顺序穷举；否则调用split_tour并行扩展；
并行扩展（split_tour）：对当前节点的所有未访问邻居，若"前缀权重 + 边权"仍未超过当前已发现的最优解，则生成新前缀入队，并通过scope.spawn派生新任务继续step；
分支限界剪枝（compute_lower_bound）：对未访问节点求"最便宜的入边"之和作为下界，连同已走路程一起作为优先级依据——下界越小的前缀越优先扩展，从而快速逼近最优解；
结果汇聚（solver.rs 的add_complete_tour）：完整环路的权重通过原子变量与互斥锁安全记录，任何线程发现的更优解都会被保留。

TourPrefix（定义于 tour.rs）记录了当前前缀的优先级、已访问节点位图（FixedBitSet）、累计权重与回溯链，其Ord实现先按优先级、再按TourId（用于打破平局）排序，保证优先队列行为确定。

八、子命令接入与数据目录约定

在 rayon-demo/src/main.rs 中，tsp子命令被登记为 "Traveling salesman problem solver (sample data sets indata/tsp)"，并在 main.rs 第 87 行分发至tsp::main。数据文件约定存放于data/tsp/目录下（bench.rs 第 14-15 行通过CARGO_MANIFEST_DIR拼接定位），因此替换或新增实例时，只需将符合 TSPLIB 规范（TYPE: TSP、EDGE_WEIGHT_TYPE: EUC_2D）的文件放入该目录即可被求解器直接使用。

结语

从 data/tsp/README.md 的寥寥数行出发，我们完整梳理了 Rayon TSP 求解器的数据链路：TSPLIB 格式规范 → 严格解析校验 → 欧氏距离取整建图 → 分支限界并行搜索 → 基准验证。dj10、dj15、dj38三个数据集既是演示样例，也是验证并行算法正确性与性能的测试载体——读者可自行修改--seq-threshold观察并行度变化，或用符合格式的任意 TSPLIB 文件替换验证。