Function hercules::local_search_utils::one_step_local_search_improved

pub fn one_step_local_search_improved(
    qubo: &Qubo,
    x_0: &Array1<usize>,
    selected_vars: &Vec<usize>
) -> Array1<usize>

Performs a single step of local search, which is to say that it will flip a single bit and return the best solution out of all of the possible bit flips. This takes O(n|Q|) + O(n) time, where |Q| is the number of non-zero elements in the QUBO matrix.

Panics

Will panic is there are not any selected variables.

Example:

use hercules::qubo::Qubo;
use smolprng::{PRNG, JsfLarge};
use hercules::{initial_points, utils};
use hercules::local_search_utils;

// generate a random QUBO
let mut prng = PRNG {
   generator: JsfLarge::default(),
};
let p = Qubo::make_random_qubo(10, &mut prng, 0.5);

// generate a random point inside with x in {0, 1}^10 with
let x_0 = initial_points::generate_random_binary_point(p.num_x(), &mut prng, 0.5);

// perform a single step of local search
let x_1 = local_search_utils::one_step_local_search_improved(&p, &x_0, &vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);