离散优化实用

实现各种有用的数据结构用于离散优化。这个crate正在积极开发中，欢迎提交Pull requests :)。

集合数据结构

各种数据结构以有效地维护集合

• 稀疏集合: 维护正整数的集合。允许O(1)的插入、删除、计数、删除除一个元素外的所有元素。这种数据结构创建成本较高，但操作非常快。更多信息请参阅这篇文章。

基准测试

子集/超集查询

允许快速执行子集或超集查询。

• 列表: 简单的列表存储。遍历整个列表以查找子集/超集
• 集合Trie: 更多信息请参阅这篇文章。对于子集查询非常快，对于超集查询较慢。如果集合中的元素数量较少，则效率较高。
• HAT-trie: 更多信息请参阅这篇文章。

基准测试

帕累托优先队列

用于在n维帕累托前沿上快速执行插入/删除/查找最小值/支配检查的数据结构。每个元素还提供了一个用于最小（分别是最小值）提取的"指南"值。

深受优秀的帕累托库（Python和C++） [1] 启发。每个帕累托前沿存储元素，使得没有元素支配另一个元素。主要区别在于，这个crate中的数据结构允许快速查找最小元素。此外，使用这个crate，可以定义比维度支配更一般的支配规则。

• 列表帕累托前沿: 简单的数据结构，使用向量简单地存储元素。这个数据结构很简单，通常适用于较小的
• Kd树: 每个节点包含一个元素并将空间分为两部分的树结构。对于许多点，这种数据结构效率很高。
• 点区域树: 每个节点将空间分为2**d个子区域的树结构。对于许多点，这种数据结构效率很高，但需要对维度进行初始的下限/上限约束。
• R树: 存储在边界框中的元素的数据结构。边界框可能相交。
• R*-tree

基准测试

随机n维点。

参考文献

Alan Freitas，基于空间数据结构的面向用户的Pareto前沿和Pareto存档，群体和进化计算，第65卷，2021年，100915，ISBN 2210-6502，https://doi.org/10.1016/j.swevo.2021.100915。（https://www.sciencedirect.com/science/article/pii/S2210650221000766）