分支与边界

此crate提供了一种通用的分支与边界算法模板。

基本构建块是BranchingOperator特性和BoundingOperator特性。为你的自定义结构实现这些特性，这些结构代表解决方案，并使用BranchAndBound结构来运行算法。

使用方法

将以下内容添加到你的Cargo.toml文件中

[dependencies]
bnb = "0.1.1"

要实现自己的BranchAndBound算法，导入BranchingOperator和BoundingOperator特性，并为你的自定义（解决方案）结构实现它们。请注意，对于BoundingOperator<V>特性，你可以使用任何实现了PartialOrd特性的类型或结构作为V。

use bnb::{BranchingOperator, BoundingOperator};

struct YourStruct { ... }

impl BranchingOperator for YourStruct {
    fn branch(&self) -> Vec<Self> {
        ...
    }
}

impl BoundingOperator<u32> for YourStruct {
    fn bound(&self) -> u32 {
        ...
    }

    fn solution(&self) -> Option<u32> {
        ...
    }
}

之后，使用YourStruct的初始状态版本导入并初始化BranchAndBound结构

use bnb::{BranchingOperator, BoundingOperator, BranchAndBound};

struct YourStruct { ... }

...

fn main() {
    let mut bnb = BranchAndBound::new(...) 
                    .minimize() // The problem is minimization problem
                    .use_dfs() // Use DFS to find the next node in the BnB-Tree
                    .with_start_solution(...); // Optional initialization with a starting solution 

    // Run the algorithm
    bnb.run_to_completion();

    // The solution should exist
    let sol = bnb.best_known_solution().unwrap();

    ...
}

或者，你可以简写为

use bnb::*;

以导入所有必需的特性。这仅导入不必要的seq-子模块。

请参阅文档，以查看背包问题的更详细的示例。