Курсовая работа: Алгоритмы поиска кратчайших покрытий булевых матриц

Покрытия методом Закревского

Итого, покрытия, построенные программой, совпадают с покрытиями, построенными вручную.

5.3.2 Пример 2. Построим кратчайшее покрытие для произвольной матрицы размером 7×7 с плотностью единицы 0,2 методом Патрика и методом Закревского:

Матрица, сгенерированная программой:

Покрытие методом Патрика

Покрытия методом Закревского

5.3.3 Пример 3.Построим кратчайшее покрытие для произвольной матрицы размером 30×30 с плотностью единицы 0,3 методом Закревского

Матрица, сгенерированная программой

Покрытия, построенные программой:

6. Длина покрытия

Длина покрытия булевой матрицы – это число строк (столбцов), образующих покрытие этой матрицы.

С помощью созданной программы можно проследить зависимость длины покрытия матрицы (L) от плотности единицы (P) в ней.

Построим график зависимости для матриц размерности 7×7, для этого сделаем 10 попыток на каждую вероятность. По оси абсцисс отложим плотность единицы в матрице, а по другой оси среднее значение длины покрытия при заданной плотности.

Видно, что при достаточно малых размерностях матрицы, всего 7×7, средняя длина покрытия почти совпадает.

Построим график для метода Закревского для матриц 10×10, для этого сделаем 20 попыток на каждое значение вероятности:

ЗАКЛЮЧЕНИЕ

В результате выполнения курсовой работы мною была разработана и отлажена программа, позволяющая находить кратчайшие покрытия булевых матриц размером до 100×100 методом Патрика (см. раздел 3.1) и методом Закревского (столбцовое и строчное покрытие) (см. раздел 3.2), а так же рассмотрен способ оптимизации (сокращения) булевых матриц (см. раздел 3.3).

Алгоритмы нахождения кратчайших покрытий – занятие трудоемкое для человека, особенно при сравнительно большой размерности матрицы, поэтому разработанная мною программа значительно упрощает выполнение этой работы.

Данные алгоритмы реализованы в интегрированной среде C++Builder6.0., которая является, на мой взгляд, наиболее подходящей для решения такого типа задач, поскольку позволяет создать наиболее удобный для пользователя интерфейс.

ЛИСТИНГ ПРОГРАММЫ