On the application of some heuristics in the study of the state minimization problem for nondeterministic finite automata by the branch and bound method. Part 2
Abstract
We continue to study heuristics that can be applied to solve the problem of minimizing the states of nondeterministic finite automata by the branch and bound method, or rather, to the implementation of the most difficult stage of the solution associated with finding the minimum cover of an auxiliary logical matrix by special subsets of its elements with the value 1 (true). A new type of heuristic is described (the “big step” heuristic) and various combinations of this heuristic and the two types of previously described heuristics are considered. An auxiliary heuristic based on the use of additional information about the analyzed matrix is also described. This auxiliary heuristic allows to more accurately assess the effectiveness of various combinations of basic heuristics.
Along with new heuristics, one of the approaches to the analysis of the results of numerical experiments is described. It is based on constructing a reference set of the best quasi-optimal solutions and studying the distributions of the obtained solutions for different variants of the algorithm with respect to this set.
Full Text:
PDF (Russian)References
Abramyan M.E., Melnikov B.F. On the application of some heuristics in the study of the state minimization problem for nondeterministic finite automata by the branch and bound method. Part 1 // International Journal of Open Information Technologies. 2020. Vol. 8. No. 9. P. 1–7 (in Russian).
Abramyan M.E., Melnikov B.F. Investigation of the problem of state minimization of nondeterministic finite automata using the branch and bound method // Cloud of Science. 2020. Vol. 7, No. 2. P. 297–319 (in Russian).
Abramyan M.E. On one approach to the implementation of the branch and bound method for optimization problems // Information ap-proaches in modeling and control: approaches, methods, solutions. Collection of scientific papers of the II Russian scientific conference with international participation. Part 1. Togliatti, 2019. P. 56–64 (in Russian).
Abramyan M.E., Melnikov B.F. An approach to algorithmizing the problem of vertex minimization of nondeterministic automata. Part I. Problem statement and the brief description of the basis methods // IOP Conference Series: Materials Science and Engineering. 862 (2020) 052055. P. 1–6.
Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae. 2010. Vol. 104. No. 3. P. 267–283.
Melnikov B.F. Regular languages and nondeterministic finite automata: a monograph. – M. : RGSU Publ., 2018 (in Russian).
Melnikov B. The complete finite automaton // International Journal of Open Information Technologies. 2017. Vol. 5. No. 10. P. 9–17.
Melnikov B.F., Melnikova E.A. Clustering situations in real-time algorithms for discrete optimization problems // Control systems and information technologies. 2007. Vol. 28, No. 2. P. 16–20 (in Russian).
Melnikov B., Romanov N. Once again on heuristics for the traveling salesman problem // Theoretical problems of informatics and its applications. 2001. Vol. 4. P. 81 (in Russian).
Melnikov B., Tsyganov A. The state minimization problem for non-deterministic finite automata: the parallel implementation of the truncated branch and bound method // Proceedings – International Symposium on Parallel Architectures, Algorithms and Programming. 2012. P. 194–201.
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность IT Congress 2024
ISSN: 2307-8162