Оптимізація жадібних алгоритмів пошуку для скомбінованих послідовностей даних

2016;
: с. 29 - 36
Автори:
1
Національний університет «Львівська політехніка», кафедра безпеки інформаційних технологій

Розглянуто питання оптимізації жадібних алгоритмів, які можуть бути застосовані для оптимізації розміщення/маршрутизації між компонентами в обчислювальних системах у випадку, коли послідовності даних було отримано за допомогою комбі- наційного розподілу. Проаналізовано недоліки використання звичайного жадібного алгоритму і запропоновано його оптимізований варіант на основі упорядкованого матричного запису розміщень, який дає змогу підвищити швидкодію алгоритму у 2.7 разу для 482 унікальних елементів.

  1. G. E. Moore, "No Exponential Is Forever: But 'Forever' Can Be Delayed!" Solid-State Circuits Conference, IEEE International Digest of Technical Papers, Vol. 1, 2003, pp. 20-23.
  2. Corman, T., Leiserson, C., Revelt, R., Stein, K. Chapter 16. Greedy Algorithms // Algorithms: Constructing and Analysis = Introduction to Algorithms, Ed. I. V. Krasikova. - 2nd ed. - M .: Williams, 2005 - 1296 pp. - ISBN 5-8459-0857-4.
  3. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms (MIT Press, 2000).
  4. Mazur, David R. (2010), Combinatorics: A Guided Tour, Mathematical Association of America, ISBN 978-0-88385-762-5.