Алгоритмы поиска кратчайших покрытий булевых матриц (стр. 2 из 3)
4 5 9
.Удаляем строки а, к (поглощаются строкой г). Получаем матрицу
( 2 х 3 ):4 5 9
.Из последней матрицы удаляем столбец 9 (равен столбцу 5) и получаем не упрощаемую матрицу
( 2 х 2 ):4 5
.Единственное покрытие последней матрицы – она сама. Итого, строки г и и составляют одно из кратчайших (даже единственное) покрытий матрицы A.
5. ПРОГРАММА
Написанная мной на ЭВМ программа «Нахождение кратчайшего покрытия булевых матриц» помогает вручную не искать покрытие заданной или генерируемой булевой матрицы до размера 99 х 99, а предоставить это компьютеру.
5.1 Описание программы
Средство программирования:
Интегрированная Среда Разработки BorlandC++ Builder 6.0.
Поддерживаемые операционные системы:
Windows 95/98/ME/NT/2000/XP.
Система для тестирования программы:
Pentium-4 ~2.3 Gh, 512 MbDDR, WindowsXPSP2.
5.2 Описание интерфейса
Pokrytie.exe – откомпилированная и отлаженная программа. При запуске отображается окно дополнительной информации:
При нажатии двойным щелчком на кнопку «Программа» в окне появляется основная форма — Меню программы (рис. 1).
Рис.1. Меню программы Рис.2. Задание вероятности единицы
Требуется ввести число строк и столбцов матрицы, а также выбрать тип создания требуемой матрицы: вручную или автоматически (с помощью компьютера). В первом случае возможны 2 способа создания пустого шаблона матрицы: все поля – либо нули, либо единицы (для реализации необходимо это просто отметить). Во втором же должна быть введена вероятность создания единицы в определенном месте матрицы (рис. 2).
По умолчанию все элементы матрицы – нули и программа допускает присутствие в матрице нулевых строк и столбцов. Если вы не ввели параметры матрицы до конца, то при нажатии кнопки «Сгенерировать» программа сообщит вам об этом:
При правильном вводе данных и нажатии кнопки генерации на экране появляется окно ввода матрицы:
При написании программы я применила графический способ ввода элементов матрицы: внутри прямоугольника, соответствующего размерам матрицы, чтобы изменить значение определенного элемента матрицы, необходимо нажать кнопку мыши при положении курсора внутри определенного квадрата, соответствующего этому элементу. Белый цвет соответствует нулю, а цвет выделяемого текста (по умолчанию – синий) соответствует единице. Для хранения данных в программе использованы динамические матрицы, что позволяет выделять память только по мере необходимости.
5.3 Результат работы программы
Рассмотрим несколько примеров, иллюстрирующих работу программы.
5.3.1 Пример 1. Пусть дана матрица С:
1 2 3 4 5 6
.Построим для этой матрицы кратчайшие покрытия методами Патрика и Закревского (строчное и столбцовое).
Матрица C в программе:
Покрытие методом Патрика:
Покрытия методом Закревского
Итого, покрытия, построенные программой, совпадают с покрытиями, построенными вручную.
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., которая является, на мой взгляд, наиболее подходящей для решения такого типа задач, поскольку позволяет создать наиболее удобный для пользователя интерфейс.
ЛИСТИНГ ПРОГРАММЫ
Unit1.cpp
#include <vcl.h>
#include <stdlib.h>
#pragma hdrstop
#include "Unit5.h"
#include "Unit4.h"
#include "Unit3.h"
#include "Unit2.h"
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
extern int a,b,c;
int **arr, *arra, *arrb,Flag = 0;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::RadioButton2Click(TObject *Sender)
{
Label3->Visible=true;
MaskEdit1->Visible=true;
Edit1->Visible=true;
CheckBox1->Visible=false;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::RadioButton1Click(TObject *Sender)
{
Label3->Visible=false;
MaskEdit1->Visible=false;
Edit1->Visible=false;
CheckBox1->Visible=true;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
a=StrToInt(MaskEdit2->EditText);
b=StrToInt(MaskEdit3->EditText);
if(a*b==0 || (RadioButton2->Checked==true && MaskEdit1->EditText=="0"))
{
Application->MessageBox("Введите данные до конца или проверьте данные", Внимание!");
Abort();
}
if(RadioButton2->Checked)
c=StrToInt(MaskEdit1->EditText);
else
c=0;
arr=new int*[b];
arra=new int[a];
arrb=new int[b];
for(int i=0;i<a;i++)
arra[i]=0;
for(int i=0;i<b;i++)
{
arrb[i]=0;
arr[i]=new int[a];
for(int j=0;j<a;j++)
{
if(c>0)
if(random(10)<=c)
{
arr[i][j]=1;
arrb[i]++;
arra[j]++;
}
else
arr[i][j]=0;
else
{
if(CheckBox1->Checked==false)
arr[i][j]=0;
else
{
arr[i][j]=1;
arrb[i]++;
arra[j]++;
} }} }
for(int i=0;i<b; i++)
{
for(int j=0;j<a;j++)
{
if((arrb[i]==0 || arra[j]==0) & RadioButton2->Checked==true)
{ Application->MessageBox("Попробуйте еще раз или введите другое значение вероятности", "Внимание!");
Abort();
}} }
Form1->Hide();
Form2->Show();
Form5->Visible=false;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormShow(TObject *Sender)
{
Form5->ShowModal();
}
//---------------------------------------------------------------------------
Unit2.cpp
#include <vcl.h>
#pragma hdrstop
#include "Unit5.h"
#include "Unit4.h"
#include "Unit3.h"
#include "Unit2.h"
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm2 *Form2;
int a, b, c, **pokr,**pokr2, q;
extern int **arr, *arra, *arrb,Flag;
//---------------------------------------------------------------------------
__fastcall TForm2::TForm2(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm2::FormClose(TObject *Sender, TCloseAction &Action)
{
Form1->Close();
}
//---------------------------------------------------------------------------
void __fastcall TForm2::FormShow(TObject *Sender)
{
Image1->Width=10*a;
Image1->Height=10*b;
for(int i=0; i<b; i++)
{
Image1->Canvas->MoveTo(0, i*Image1->Height/b);
Image1->Canvas->LineTo(Image1->Width, i*Image1->Height/b);
}
for(int j=0; j<a; j++)
{
Image1->Canvas->MoveTo(j*Image1->Width/a, 0);
Image1->Canvas->LineTo(j*Image1->Width/a, Image1->Height);
}
if(c>0 || c==0 && arr[0][0]==1)
{
Image1->Canvas->Brush->Color=clActiveCaption;
for(int i=0;i<b;i++)
{
for(int j=0;j<a;j++)
{
if(arr[i][j]==1)
Image1->Canvas->FillRect(Rect(10*j+1,10*i+1,10*j+10,10*i+10));
} } }}
//---------------------------------------------------------------------------