АЛГОРИТМ ПОКРЫТИЯ РАЗРЕЖЕННЫХ БУЛЕВЫХ МАТРИЦ
Аннотация
Предлагается алгоритм решения задачи о наименьшем покрытии множества, известной в литературе как задача нахождения кратчайшего столбцового покрытия булевой матрицы. Сравнивается эффективность разработанного алгоритма, реализованного в программе Tie, c эффективностью алгоритма программы Espresso и алгоритма GANP. Приводятся результаты экспериментально-статистических испытаний алгоритма на стандартных примерах серий Benchmark, CLR и Stein, а также на псевдослучайных системах булевых функций.
Список литературы
1. Сапоженко, А.А. Минимизация булевых функций в классе дизъюнктивных нормальных форм / А.А. Сапоженко, И.П. Чухров // Итоги науки и техники. – М., 1987. – Т. 25. – С. 68–116.
2. Леончик, П.В. Минимизация систем булевых функций в классе дизъюнктивных нормальных форм / П.В. Леончик // Информатика. – 2006. – № 1(9). – C. 88–96.
3. Закревский, А.Д. Основы логического проектирования. Комбинаторные алгоритмы дискретной математики. Кн. 1 / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – Минск: ОИПИ НАН Беларуси, 2004.
4. Yang, S. Logic synthesis and optimization benchmarks user guide version 3.0. Technical Report / S. Yang. – Microelectronics Center of North Carolina, 1991.
5. Закревский, А.Д. Генераторы псевдослучайных логико-комбинаторных объектов / А.Д. Закревский, Н.Р. Торопов // Логическое проектирование: сб. науч. тр. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1999. – С. 49–63.
6. Beasley, J.E. OR-Library: Distributing test problems by electronic mail / J.E. Beasley // Journal of the Operational Research Society. – 1990. – Vol. 41, № 11. – P. 1069–1072.
7. Logic Minimization Algorithms for VLSI synthesis / R.K. Brayton [et al.]. – Boston: Kluwer Academic Publishers, 1984.
8. ESPRESSO-II: a New Logic Minimizer for PLA / R.K. Brayton [et al.] // IEEE Pros. Custom Integrated Circuits Conf. – Rochester, 1984.
9. Rudel, R. Multiple-Valued Minimization for PLA Optimization / R. Rudel, A. Sangiovanni Vincentelli // IEEE Trans. Computer-Aided Des. – 1987. – Vol. CAD-6, № 5. – Р. 727–751.
10. Еремеев, А.В. Генетический алгоритм для задачи о покрытии / А.В. Еремеев // Дискретный анализ и исследование операций. – 2000. – Сер. 2. – Т. 7, № 1. – С. 47–60.
Рецензия
Для цитирования:
Леончик П.В. АЛГОРИТМ ПОКРЫТИЯ РАЗРЕЖЕННЫХ БУЛЕВЫХ МАТРИЦ. Информатика. 2007;(2(14)):53-61.
Просмотров: 543
Послать статью по эл. почте 