tsp-rs

旅行商问题算法库。

示例

基本

用于 2D 点数据集

use std::time;

use tsp_rs::Tour;
use tsp_rs::point::Point;

let tour: Vec<Point> = vec![
    Point::new(0., 0.),
    Point::new(0., 1.),
    Point::new(1., 0.),
    Point::new(1., 1.),
];

let mut tour = Tour::from(&tour);

tour.optimize_kopt(std::time::Duration::from_secs(1));

使用特性

与上述相同，但不是使用 tsp::point::Point，而是为你的类型 T 实现 tsp::metrizable::Metrizable 特性，通过定义两个 T 之间的距离函数。你的类型还需要 Clone、Borrow，也许还需要其他... 编译器会记住。

性能

Path::solve_kopt 使用 2-opt 启发式，如果遇到很长时间的障碍，则抛出 3-opt。对于 b52，平均在 solve_nn + 1 秒的优化后达到最优解的 ~8%，对于 qa194，平均达到 ~10%。问题越大，你应该允许的优化时间越长。

对于构造性解决方案 Path::solve_nn，平均在最优解的 ~15%。

注释

仅供我学习 Rust 时的娱乐，但不保证实现正确。