steiner-tree

快速基于查找表的矩形 Steiner 最小树（RSMT）计算。

此包实现了 'FLUTE' 算法，包括生成查找表以及基于查找表创建树。最多 9 个引脚的查找表可以在 16 秒内生成。

对于更高引脚数，已经实现了网络断裂启发式算法，但仍然不如 FLUTE 3.0 算法。

基准测试

可以使用 cargo bench 使用简单的基准测试基础设施。

待办事项

[ ] 实现 FLUTE 3.0 中的网络断裂算法。[ ] 读写查找表。生成大于 8 度的查找表在实时生成中速度太慢。

lib.rs:

快速基于查找表的矩形 Steiner 最小树（RSMT）计算。

示例

use steiner_tree;

// Generate a lookup-table for up to 3 points.
// This is an expensive computation.
// Up to 8 points, this runs in less than a second on a laptop from 2011.
// For 9 points takes 16 seconds.
let lut = steiner_tree::gen_lut::gen_full_lut(3);

let points = vec![(1, 2).into(), (3, 4).into(), (5, 6).into()];

// Up steiner trees with up to 5 pins can be computed by direct lookup.
// This method will panic if it is called with too many points.
let (small_tree, small_tree_weight) = lut.rsmt_low_degree(points);

// If the number of points exceeds the size of the lookup-table, a net-breaking heuristic will be used.
let points = vec![(1, 2).into(), (3, 4).into(), (5, 6).into(), (7, 8).into()];
// An accuracy value must be provided for the heuristic.
// Larger values lead to better results but also to longer computations.
let accuracy = 3;
let (medium_tree, medium_tree_weight) = lut.rsmt_medium_degree(points, accuracy);

参考

• FLUTE, Chris Chu and Yiu-Chung Wong, 2008 (存档)