solverforge_solver/phase/
dynamic_vnd.rs

1use std::fmt::{self, Debug};
2use std::marker::PhantomData;
3
4use solverforge_core::domain::PlanningSolution;
5use solverforge_scoring::{Director, RecordingDirector};
6
7use crate::heuristic::r#move::{Move, MoveArena};
8use crate::heuristic::selector::MoveSelector;
9use crate::phase::control::{
10    append_interruptibly, settle_search_interrupt, should_interrupt_evaluation, StepInterrupt,
11};
12use crate::phase::Phase;
13use crate::scope::{PhaseScope, ProgressCallback, SolverScope, StepScope};
14
15pub struct DynamicVndPhase<S, M, MS> {
16    neighborhoods: Vec<MS>,
17    _phantom: PhantomData<(fn() -> S, fn() -> M)>,
18}
19
20impl<S, M, MS> DynamicVndPhase<S, M, MS> {
21    pub fn new(neighborhoods: Vec<MS>) -> Self {
22        Self {
23            neighborhoods,
24            _phantom: PhantomData,
25        }
26    }
27}
28
29impl<S, M, MS: Debug> Debug for DynamicVndPhase<S, M, MS> {
30    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
31        f.debug_struct("DynamicVndPhase")
32            .field("neighborhoods", &self.neighborhoods)
33            .finish()
34    }
35}
36
37impl<S, D, ProgressCb, M, MS> Phase<S, D, ProgressCb> for DynamicVndPhase<S, M, MS>
38where
39    S: PlanningSolution,
40    D: Director<S>,
41    ProgressCb: ProgressCallback<S>,
42    M: Move<S>,
43    MS: MoveSelector<S, M>,
44{
45    fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
46        let mut arena = MoveArena::<M>::new();
47        let mut phase_scope = PhaseScope::new(solver_scope, 0);
48        let mut current_score = phase_scope.calculate_score();
49        let mut k = 0usize;
50
51        while k < self.neighborhoods.len() {
52            let mut step_scope = StepScope::new(&mut phase_scope);
53            arena.reset();
54            let generation_interrupted = {
55                let iter = self.neighborhoods[k].iter_moves(step_scope.score_director());
56                append_interruptibly(&step_scope, &mut arena, iter)
57            };
58            if generation_interrupted {
59                match settle_search_interrupt(&mut step_scope) {
60                    StepInterrupt::Restart => continue,
61                    StepInterrupt::TerminatePhase => break,
62                }
63            }
64
65            match find_best_improving_move_index(&arena, &mut step_scope, &current_score) {
66                MoveSearchResult::Found(selected_index, selected_score) => {
67                    let selected_move = arena.take(selected_index);
68                    selected_move.do_move(step_scope.score_director_mut());
69                    step_scope.set_step_score(selected_score);
70                    current_score = selected_score;
71                    step_scope.phase_scope_mut().update_best_solution();
72                    step_scope.complete();
73                    k = 0;
74                }
75                MoveSearchResult::NotFound => {
76                    step_scope.complete();
77                    k += 1;
78                }
79                MoveSearchResult::Interrupted => match settle_search_interrupt(&mut step_scope) {
80                    StepInterrupt::Restart => continue,
81                    StepInterrupt::TerminatePhase => break,
82                },
83            }
84        }
85    }
86
87    fn phase_type_name(&self) -> &'static str {
88        "VariableNeighborhoodDescent"
89    }
90}
91
92enum MoveSearchResult<Sc> {
93    Found(usize, Sc),
94    NotFound,
95    Interrupted,
96}
97
98fn find_best_improving_move_index<S, D, ProgressCb, M>(
99    arena: &MoveArena<M>,
100    step_scope: &mut StepScope<'_, '_, '_, S, D, ProgressCb>,
101    current_score: &S::Score,
102) -> MoveSearchResult<S::Score>
103where
104    S: PlanningSolution,
105    D: Director<S>,
106    ProgressCb: ProgressCallback<S>,
107    M: Move<S>,
108{
109    let mut best: Option<(usize, S::Score)> = None;
110
111    for i in 0..arena.len() {
112        if should_interrupt_evaluation(step_scope, i) {
113            return MoveSearchResult::Interrupted;
114        }
115
116        let m = arena.get(i).unwrap();
117
118        if !m.is_doable(step_scope.score_director()) {
119            continue;
120        }
121
122        let mut recording = RecordingDirector::new(step_scope.score_director_mut());
123        m.do_move(&mut recording);
124        let move_score = recording.calculate_score();
125        recording.undo_changes();
126
127        if move_score > *current_score {
128            match &best {
129                Some((_, best_score)) if move_score > *best_score => {
130                    best = Some((i, move_score));
131                }
132                None => best = Some((i, move_score)),
133                _ => {}
134            }
135        }
136    }
137
138    match best {
139        Some((index, score)) => MoveSearchResult::Found(index, score),
140        None => MoveSearchResult::NotFound,
141    }
142}
solverforge_solver/phase/dynamic_vnd.rs

solverforge_solver/phase/
dynamic_vnd.rs
