Метод сокращения перебора в алгоритмах построения минимальных аддитивных цепочекетод сокращения перебора в алгоритмах построения минимальных аддитивных цепочек
Аннотация
Оптимизация алгоритмов вычислений значений многочленов, точнее мономов, эквивалентна задаче построения для заданного числа минимальной аддитивной цепочки. Для поиска таких цепочек не известно никаких алгоритмов, кроме перебора. Рост сложности перебора очень велик. Среди цепочек одинаковой длины очень много эквивалентных, то есть заканчивающихся одинаковым числом. В статье приведен достаточный признак эквивалентности цепочек и показано, как использование признака позволяет сократить процедуру формирования всех аддитивных цепочек фиксированной длины.
Литература
D. Knuth, Iskusstvo programmirovaniya [The Art of Computer Programming], K. I. Babenko and Yu. M. Bayakovskii, eds., vol. 1, Moscow: Iz-vo Mir, 1974 (in Russian).
N. Pippenger, “On the evaluation of powers and monomials,” SIAM J. Comput., vol. 9, no. 2, pp. 230–250, 1980; doi:10.1137/0209022
N. N. Vassiliev, “Evaluations of sparse polynomials and the synthesis of evaluating programs,” in Proc. Internat. Conf. on Comp. Algebra and Appl. Thtor. Phys., Dubna, 1984, pp. 154–159.
V. V. Kochergin, “Utochnenie otsenok slozhnosti vychisleniya odnochlenov i naborov stepenei v zadachakh Bellmana i Knuta” [Improvement of the estimates of the computational complexity for monomials and sets of powers in Bellman’s and Knuth’s problems], J. Appl. Industr. Math., vol. 9, no. 1, pp. 68–82, 2015 (in Russian); doi: 10.1134/S1990478915010081
A. M. Kotochigov, “Algoritmy fraktal’nogo analiza izobrazhenii” [Fractal Image Analysis Algorithms], Computer tools in education, no. 2, pp. 34–39, 2012 (in Russian).
Материал публикуется под лицензией:
