|
Modelirovanie i Analiz Informatsionnykh Sistem, 2011, Volume 18, Number 4, Pages 168–180
(Mi mais207)
|
|
|
|
Verification of backtracking and branch and bound design templates
N. V. Shilovabc a Novosibirsk State University
b A. P. Ershov Institute of Informatics Systems Sib. Br. RAS
c Novosibirsk State Technical University
Abstract:
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.
Received: 11.10.2011
Citation:
N. V. Shilov, “Verification of backtracking and branch and bound design templates”, Model. Anal. Inform. Sist., 18:4 (2011), 168–180
Linking options:
https://www.mathnet.ru/eng/mais207 https://www.mathnet.ru/eng/mais/v18/i4/p168
|
Statistics & downloads: |
Abstract page: | 403 | Full-text PDF : | 182 | References: | 39 |
|