稀疏线性分配

用于二分图加权完美匹配问题的求解器（线性分配）。两个求解器都使用拍卖算法的变体，并用 Rust 实现。

• KhoslaSolver 适用于非对称 k-正则稀疏图。该算法在本论文中介绍。它会在有限次迭代中停止。
• ForwardAuctionSolver 对于对称分配问题效果更好。它使用 ε 缩放来加速拍卖算法。实现基于 sslap。当没有完美匹配时，它会进入无限循环并在 max_iterations 次迭代后停止。

使用方法

use sparse_linear_assignment::{AuctionSolver, KhoslaSolver};

fn main() -> Result<(), Box<dyn std::error::Error>> {
   // We have 2 people and 4 objects
   // weights between person i and objects j
   let weights = vec![
       // person 0 can connect with all objects
       vec![10, 6, 14, 1],
       // person 1 can connect with first 3 objects
       vec![17, 18, 16]
   ];
   let expected_cost = 1. + 16.;
   let expected_person_to_object = vec![3, 2];
   // u32::MAX value is used to indicate that the corresponding object is not assigned.
   // If there is no perfect matching unassigned people in `person_to_object` will be marked by
   // u32::MAX too
   let expected_object_to_person = vec![u32::MAX, u32::MAX, 1, 0];
   // Create `KhoslaSolver` and `AuctionSolution` instances with expected capacity of rows,
   // columns and arcs. We can reuse them in case there is a need to solve multiple assignment
   // problems.
   let max_rows_capacity = 10;
   let max_columns_capacity = 10;
   let max_arcs_capacity = 100;
   let (mut solver, mut solution) = KhoslaSolver::new(
       max_rows_capacity, max_columns_capacity, max_arcs_capacity);

   // init solver and CSR storage before populating weights for the next problem instance
   let num_rows = weights.len();
   let num_cols = weights[0].len();
   solver.init(num_rows as u32, num_cols as u32)?;
   // populate weights into CSR storage and init the solver
   // row indices are expected to be nondecreasing
   (0..weights.len() as u32)
       .zip(weights.iter())
       .for_each(|(i, row_ref)| {
           let j_indices = (0..row_ref.len() as u32).collect::<Vec<_>>();
           let values = row_ref.iter().map(|v| ((*v) as f64)).collect::<Vec<_>>();
           solver.extend_from_values(i, j_indices.as_slice(), values.as_slice()).unwrap();
   });
   // solve the problem instance. We want to minimize the cost of the assignment.
   let maximize = false;
   solver.solve(&mut solution, maximize, None)?;
   // We found perfect matching and all people are assigned
   assert_eq!(solution.num_unassigned, 0);
   assert_eq!(solver.get_objective(&solution), expected_cost);
   assert_eq!(solution.person_to_object, expected_person_to_object);
   assert_eq!(solution.object_to_person, expected_object_to_person);
   Ok(())
}

更多示例，请参阅 测试。