Geodesic
Verification of backtracking and branch and bound design templates
Modelirovanie i analiz informacionnyh sistem, Tome 18 (2011) no. 4, pp. 168-180

Voir la notice de l'article provenant de la source Math-Net.Ru

The Design and Analysis of Computer Algorithms is a must of Computer Curricula. It covers many topics that group around several core themes. These themes range from data structures to the complexity theory, but one very special theme is algorithmic design patterns, including greedy method, divide-and-conquer, dynamic programming, backtracking and branch-and-bound. Naturally, all the listed design patterns are taught, learned and comprehended by examples. But they can be semi-formalized as design templates, semi-specified by correctness conditions, and semi-formally verified by means of Floyd method. Moreover, this approach can lead to new insights and better comprehension of the design patterns, specification and verification methods. In this paper we demonstrate an utility of the approach by study of backtracking and branch-and-bound design patterns. In particular, we prove correctness of the suggested templates when the boundary condition is monotone, but the decision condition is anti-monotone on sets of “visited” vertices.
Keywords: backtracking, branch-and-bound, abstract data type, partial correctness, total correctness, Floyd proof method, $n$-queen puzzle, knapsack problem. 
@article{MAIS_2011_18_4_a14,
     author = {N. V. Shilov},
     title = {Verification of backtracking and branch and bound design templates},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {168--180},
     publisher = {mathdoc},
     volume = {18},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2011_18_4_a14/}
}
TY  - JOUR
AU  - N. V. Shilov
TI  - Verification of backtracking and branch and bound design templates
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2011
SP  - 168
EP  - 180
VL  - 18
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2011_18_4_a14/
LA  - ru
ID  - MAIS_2011_18_4_a14
ER  - 
%0 Journal Article
%A N. V. Shilov
%T Verification of backtracking and branch and bound design templates
%J Modelirovanie i analiz informacionnyh sistem
%D 2011
%P 168-180
%V 18
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2011_18_4_a14/
%G ru
%F MAIS_2011_18_4_a14
N. V. Shilov. Verification of backtracking and branch and bound design templates. Modelirovanie i analiz informacionnyh sistem, Tome 18 (2011) no. 4, pp. 168-180. http://geodesic.mathdoc.fr/item/MAIS_2011_18_4_a14/