注意

此版本仍在开发中。特别是，它缺少一份描述所使用算法及其性能的 40 页正式报告。一旦允许发布，此注释将被删除。

Walky - 高度并行的 TSP 求解器（支持 MPI！）

Walky 是一个高度并行的旅行商问题（TSP）求解器。它具有以下特性

• 支持精确求解、近似求解和下界生成
• 与标准 TSPLIB-XML 格式 兼容
• 多种近似算法：最近邻算法、Christofides 算法
• 多种下界算法：最小生成树（MST）、1-tree
• 支持多线程和分布式内存，多节点并行使用 MPI
• 文档齐全，经过良好测试，高度优化

为了更好地了解该主题，强烈推荐观看 reducible 的 视频文章。

安装

要么使用 cargo（对于 MPI，请添加 --features mpi）

cargo install walky

或者从 git 构建

git clone https://github.com/lquenti/walky
cd walky
cargo build --release (--features mpi)

对于基准测试，可以使用 benchmarking 功能。

使用方法

$ walky --help
A TSP solver written in Rust

Usage: walky <COMMAND>

Commands:
  exact        Find the exact best solution to a given TSP instance
  approx       Find an approximate solution to a given TSP instance
  lower-bound  Compute a lower bound cost of a TSP instance
  help         Print this message or the help of the given subcommand(s)

Options:
  -h, --help     Print help
  -V, --version  Print version

精确算法

示例调用（算法 v5，多线程，示例生成）

$ walky exact v5 -p multi-threaded utils/gen_matrix_fast/results/8.xml
Best Cost: 47.85171352981164
Best Permutation: [0, 6, 1, 3, 5, 2, 7, 4]

完整使用方法

$ walky exact --help
Find the exact best solution to a given TSP instance

Usage: walky exact [OPTIONS] <ALGORITHM> <INPUT_FILE>

Arguments:
  <ALGORITHM>
          The Algorithm to use

          Possible values:
          - v0: Testing each possible (n!) solutions
          - v1: Fixating the first Element, so testing ((n-1)!) solutions
          - v2: Recursive Enumeration; Keep the partial sums cached
          - v3: Stop if partial sum is worse than previous best
          - v4: Stop if partial sum + greedy nearest neighbour graph is bigger than current optimum
          - v5: As V5, but use an MST instead of NN-graph as a tighter bound
          - v6: Cache MST distance once computed

  <INPUT_FILE>
          Path to the TSPLIB-XML file

Options:
  -p, --parallelism <PARALLELISM>
          Whether to solve it sequential or parallel

          [default: single-threaded]

          Possible values:
          - single-threaded: Run in a single threaded
          - multi-threaded:  Run in multiple threads on a single node

  -h, --help
          Print help (see a summary with '-h')

  -V, --version
          Print version

近似算法

示例调用（算法 christofides，多线程，示例生成）

$ walky approx christofides -p multi-threaded utils/gen_matrix_fast/results/8.xml
Christofides solution weight: 47.87647721988842

完整使用方法

$ walky approx --help
Find an approximate solution to a given TSP instance

Usage: walky approx [OPTIONS] <ALGORITHM> <INPUT_FILE>

Arguments:
  <ALGORITHM>
          The Algorithm to use

          Possible values:
          - nearest-neighbour: Starting at each vertex, always visiting the lowest possible next vertex
          - christofides:      The Christofides(-Serdyukov) algorithm

  <INPUT_FILE>
          Path to the TSPLIB-XML file

Options:
  -p, --parallelism <PARALLELISM>
          Whether to solve it sequential or parallel

          [default: single-threaded]

          Possible values:
          - single-threaded: Run in a single threaded
          - multi-threaded:  Run in multiple threads on a single node

  -l, --lower-bound <LOWER_BOUND>
          Whether to also compute a lower_bound. Optional

          Possible values:
          - one-tree: The one tree lower bound
          - mst:      The MST lower bound

  -h, --help
          Print help (see a summary with '-h')

  -V, --version
          Print version

下界

示例调用（算法 1-tree，示例生成）

$ walky lower-bound one-tree utils/gen_matrix_fast/results/8.xml
1-tree lower bound: 47.13382548327308

完整使用方法

$ walky lower-bound --help
Compute a lower bound cost of a TSP instance

Usage: walky lower-bound [OPTIONS] <ALGORITHM> <INPUT_FILE>

Arguments:
  <ALGORITHM>
          The Algorithm to use

          Possible values:
          - one-tree:  The one tree lower bound
          - mst:       The MST lower bound
          - mst-queue: The MST lower bound, computed with prims algorithm using a priority queue

  <INPUT_FILE>
          Path to the TSPLIB-XML file

Options:
  -p, --parallelism <PARALLELISM>
          Whether to solve it sequential or parallel
          
          [default: single-threaded]

          Possible values:
          - single-threaded: Run in a single threaded
          - multi-threaded:  Run in multiple threads on a single node

  -h, --help
          Print help (see a summary with '-h')

  -V, --version
          Print version

算法

算法可以在技术报告中找到（即将上传）

测试文件生成

可以使用 utils/gen_matrix_fast/{gen,gen_big}.sh 生成测试 XML 文件。

许可证

本项目采用 MIT 许可证。

第三方依赖项

此项目包含名为 priority-queue 的crate，它采用LGPLv3和MPLv2的双重许可。您可以在以下位置找到该项目的源代码：https://github.com/garro95/priority-queue。由于MPLv2允许这样做，我们可以将此项目包含在我们的项目中：https://www.mozilla.org/en-US/MPL/2.0/FAQ/