DOGS (离散优化全局搜索) 框架

在统一范式内实现各种搜索算法（目前主要是任何时间树搜索算法）。有关任何时间树搜索算法的更多信息，请参阅这篇论文。

实现组件

树搜索算法

• 部分扩展贪婪算法
• 束搜索
• 最佳优先搜索
• 深度优先搜索
• 迭代束搜索
• 有限差异搜索
• 部分扩展（迭代）束搜索

装饰器

• 边界装饰器：衡量对偶界限
• LDS装饰器：限制树探索到具有少量差异的节点
• G-cost优势装饰器：实现g-cost优势
• 剪枝装饰器：剪枝被最佳已知解支配的节点
• 统计装饰器：报告搜索的各种统计数据

路线图：接下来是什么？

• 如果在搜索进行某些启发式深入之前超过时间限制，则“is_optimal”中可能存在错误。在这种情况下，算法将报告“最优”而实际上不是。
• 每个组件（搜索算法、装饰器等）都可以生成一个JSON对象。然后可以将此JSON对象写入文件或由更高组件组合。
• 使用Iterator trait进行部分扩展（更符合习惯）
• PruningDecorator的性能改进
• 添加Decorator trait和unwrap()的基本实现
• 改进LazyComputable的使用（特性？）

示例

为各种问题提供了一些示例。对于其中一些，DOGS实现是业界领先的。

• 顺序排序问题（SOP） git仓库，参考论文
• 排列作业车间（最小化最大完工时间和流动时间） git仓库，参考论文

一些有用的提示

安装rust

查看rust入门页面。

火焰图分析（Linux）

1. 安装需求 sudo apt install -y linux-tools-common linux-tools-generic
2. 通过 cargo 安装 flamegraph cargo install flamegraph
3. 禁用 perf 的 sudo 需求：echo -1 | sudo tee /proc/sys/kernel/perf_event_paranoid. 可能的话，sudo sh -c 'echo kernel.perf_event_paranoid=1 > /etc/sysctl.d/local.conf' 可能允许您在每个终端中不使用之前的命令。
4. 在 Cargo.toml 中添加以下内容

[profile.release]
debug = true

5. cargo flamegraph ARGUMENTS. 例如 (SOP): cargo flamegraph insts/R.700.1000.15.sop 30
6. 可视化 flamegraph（此处使用 Firefox）：firefox flamegraph.svg.

堆分析（Linux）

我们建议使用 heaptrack.

1. 调用 heaptrack PROG
2. 分析数据 heaptrack_gui DATA.gz

缓存性能

我们建议使用 Valgrind

1. valgrind--工具=callgrind--转储-指令=是--收集-跳转=是--模拟-缓存=是[程序] [参数]

遍历文件（Linux）

for f in `ls DIRNAME/*`; do COMMAND "${f}"; done

基准测试

本项目使用 cargo-criterion.

当 cargo-criterion 已安装时，您可以直接调用它： cargo criterion