×

zbMATH — the first resource for mathematics

Object-oriented backtracking. (English) Zbl 1425.68057
Summary: Several versions of the backtracking are known. In this paper, those versions are in focus which solve the problems whose problem space can be described with a special directed tree. The traversal strategies of this tree will be analyzed and they will be implemented in object-oriented style. In this way, the traversal is made by an enumerator object which iterates over all the paths (partial solutions) of the tree. Two different “backtracking enumerators” are going to be presented and the backtracking algorithm will be a linear search over one of these enumerators. Since these algorithms consist of independent objects (the enumerator, the linear search and the task which must be solved), it is very easy to exchange one component in order to solve another problem. Even the linear search could be substituted with another algorithm pattern, for example, with a counting or a maximum selection if the task had to be solved with a backtracking counting or a backtracking maximum selection.
MSC:
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] K.A. Berman, J. L. Paul, Fundamentals of Sequential Algorithms, PWS Publishing, 1996. ⇒146
[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (3rd edition), The MIT Press, 2009. ⇒148 · Zbl 1187.68679
[3] T. Gregorics, Programozáas 1.kötet Tervezées, ELTE, Eötvös Kiadó, 2013. (in Hungarian) ⇒145, 153, 155, 158
[4] T. Gregorics, Programming theorems on enumerator, Teaching Mathematics and Computer Science, 8, 1 (2010) 89-108. ⇒145, 153, 155, 158
[5] I. Fekete, T. Gregorics, S. Nagy, Bevezetés a mesterséges intelligenciába, LSI, 1990. (in Hungarian) ⇒145
[6] Á. Fóthi, Bevezetés a programozásba, ELTE, Eötvös Kiadó, 2005. (in Hungarian) ⇒146, 151
[7] I. Futó (ed), Mesterséges intelligencia, Aula, 1999. (in Hungarian) ⇒145
[8] D. E. Knuth, Estimating the efficiency of backtrack programs, Mathematics of Computation 29 (1975) 121-136. ⇒146 · Zbl 0297.68037
[9] K. I. Lörentey, Fekete, Á. Fóthi, T. Gregorics, On the wide variety of backtracking algorithms, ICAI’05 Eger, Hungary, January 28-February 3. 2005, pp. 165-174. ⇒145, 146, 151
[10] N. J. Nilsson, Principles of Artificial Intelligence, Springer-Verlag, Berlin, 1982. ⇒145, 148 · Zbl 0474.68094
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.