49728 (Алгоритмы поиска кратчайших покрытий булевых матриц), страница 2
Описание файла
Документ из архива "Алгоритмы поиска кратчайших покрытий булевых матриц", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "49728"
Текст 2 страницы из документа "49728"
Рис.1. Меню программы Рис.2. Задание вероятности единицы
Требуется ввести число строк и столбцов матрицы, а также выбрать тип создания требуемой матрицы: вручную или автоматически (с помощью компьютера). В первом случае возможны 2 способа создания пустого шаблона матрицы: все поля – либо нули, либо единицы (для реализации необходимо это просто отметить). Во втором же должна быть введена вероятность создания единицы в определенном месте матрицы (рис. 2).
По умолчанию все элементы матрицы – нули и программа допускает присутствие в матрице нулевых строк и столбцов. Если вы не ввели параметры матрицы до конца, то при нажатии кнопки «Сгенерировать» программа сообщит вам об этом:
При правильном вводе данных и нажатии кнопки генерации на экране появляется окно ввода матрицы:
При написании программы я применила графический способ ввода элементов матрицы: внутри прямоугольника, соответствующего размерам матрицы, чтобы изменить значение определенного элемента матрицы, необходимо нажать кнопку мыши при положении курсора внутри определенного квадрата, соответствующего этому элементу. Белый цвет соответствует нулю, а цвет выделяемого текста (по умолчанию – синий) соответствует единице. Для хранения данных в программе использованы динамические матрицы, что позволяет выделять память только по мере необходимости.
-
Результат работы программы
Рассмотрим несколько примеров, иллюстрирующих работу программы.
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
#include
#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 arra[i]=0; for(int i=0;i { arrb[i]=0; arr[i]=new int[a]; for(int j=0;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 { for(int j=0;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 #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 { Image1->Canvas->MoveTo(0, i*Image1->Height/b); Image1->Canvas->LineTo(Image1->Width, i*Image1->Height/b); } for(int j=0; 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 { for(int j=0;j { if(arr[i][j]==1) Image1->Canvas->FillRect(Rect(10*j+1,10*i+1,10*j+10,10*i+10)); } } }} //--------------------------------------------------------------------------- void __fastcall TForm2::N1Click(TObject *Sender) { int *arra_copy, *arrb_copy, **arr_copy; int min, *pokr_d, *counter1, *counter2, **pokr1, t=0, res=1; arr_copy=new int*[b]; arra_copy=new int[a]; arrb_copy=new int[b]; for(int i=0;i arra_copy[i]=arra[i]; for(int i=0;i { arrb_copy[i]=arrb[i]; arr_copy[i]=new int[a]; for(int j=0; j arr_copy[i][j]=arr[i][j]; } for(int i=0;i { for(int j=0;j { if(arrb_copy[i]==0 || arra_copy[j]==0) { Application->MessageBox("Слишком маленькое значение вероятности", "Ошибка"); Abort(); } } } if(a*b>36) { for(int i=0; i { if(arrb_copy[i]>0) { for(int temp, j=i+1; j { if(arrb_copy[j]>0 && arrb_copy[i]>0) { int z; temp=0; for(int k=0; k if(arr_copy[i][k]==1 & arr_copy[j][k]==1) temp++; if(arrb_copy[i]>=arrb_copy[j]) z=j; else z=i; if(temp==arrb_copy[z]) { for(int k=0; k { if(arr_copy[z][k]==1) arra_copy[k]--; arr_copy[z][k]=0; } arrb_copy[z]=0; } } } } } for(int i=0; i { if(arra_copy[i]>0) { for(int temp, j=i+1; j { if(arra_copy[j]>0) { int z; temp=0; for(int k=0; k if(arr_copy[k][i]==1 & arr_copy[k][j]==1) temp++; if(arra_copy[i]>=arra_copy[j]) z=i; else z=j; if(temp==arra_copy[z]) { for(int k=0; k { if(arr_copy[k][z]==1) arrb_copy[k]--; arr_copy[k][z]=0; } arra_copy[z]=0; } } } } } } counter1=new int[a]; counter2=new int[a]; for(int i=0; i { if(arra_copy[i]>0) { res*=arra_copy[i]; if(arra_copy>0) counter2[i]=1; else counter2[i]=0; } } pokr1=new int*[res]; for(int i=0; i { pokr1[i]=new int[b]; for(int j=0; j pokr1[i][j]=0; } for(;;) { for(int i=0; i { counter1[i]=counter2[i]; if(arra_copy[i]>0) { for(int j=0; j { if(arr_copy[j][i]==1) { if(counter1[i]>1) { counter1[i]--; continue; } pokr1[t][j]=1; break; } } } } counter2[0]++; for(int i=0; i<(a-1); i++) { if(counter2[i]>arra_copy[i] && counter2[a-1]<=arra_copy[a-1]) { counter2[i]=0; counter2[i+1]++; } } if(counter2[a-1]>arra_copy[a-1]) break; t++; if(t==res) break; } delete []arr_copy; delete []arra_copy; delete []arrb_copy; delete []counter1; delete []counter2; pokr_d=new int[res]; for(int i=0; i { pokr_d[i]=0; for(int j=0; j if(pokr1[i][j]==1) pokr_d[i]++; } min=pokr_d[0]; for(int i=1; i if(pokr_d[i]0) min=pokr_d[i]; q=res; for(int i=0; i { if(pokr_d[i]>min) { q--; for(int j=0; j pokr1[i][j]=0; pokr_d[i]=0; } } for(int i=0; i { if(pokr_d[i]!=0) { for(int temp, j=i+1; j { temp=0; for(int k=0; k { if(pokr1[i][k]==pokr1[j][k]) temp++; } if(temp==b) { q--; pokr_d[j]=0; for(int k=0; k pokr1[j][k]=0; } } } } pokr=new int*[q]; for(int i=0; i pokr[i]=new int[b]; for(int i=0, j=0; i { if(pokr_d[i]>0) { for(int k=0; k pokr[j][k]=pokr1[i][k]; j++; } } delete []pokr1; Flag = 0; Form3->Caption = "Метод Патрика"; Form3->Show(); } //--------------------------------------------------------------------------- void __fastcall TForm2::N3Click(TObject *Sender) //Строчный { for(int i=0;i { for(int j=0;j { if(arrb[i]==0 || arra[j]==0) { Application->MessageBox("Неправильно ввели матрицу! \n Пожалуйста, проверьте начальные данные ", "Внимание!"); Abort(); } } } int x, y, res, *str, *stb, str_max, stb_min; res=1; q=1; pokr=new int*[res]; pokr[0]=new int[b]; str=new int[b]; stb=new int[a]; for(int i=0;i { pokr[0][i]=0; str[i]=arrb[i]; } for(int i=0; i { stb[i]=arra[i]; } for(;;) { for(int i=0; i { if(stb[i]>0) { stb_min=stb[i]; break; } } for(int i=0; i if(stb[i] stb_min=stb[i]; for(int i=0; i { if(stb[i]==stb_min) { x=i; break; } } for(int i=0, j=0; i { if(arr[i][x]==1) { if(j==0) { str_max=str[i]; j++; } if(str[i]>str_max) str_max=str[i]; } } for(int i=0; i { if(str[i]==str_max && arr[i][x]==1) { y=i; pokr[0][y]=1; str[y]=0; for(int j=0; j { if(arr[y][j]==1) { stb[j]=0; for(int k=0; k if(arr[k][j]==1 && k!=y) str[k]--; } } break; } } int z=0; for(int i=0; i z+=stb[i]; if(z==0) break; } delete []str; delete []stb; int x1, y1, res1, *str1, *stb1, str_min1, stb_max1; //Столбцовый res1=1; q=1; pokr2=new int*[res1]; pokr2[0]=new int[b]; str1=new int[a]; stb1=new int[b]; for(int i=0;i { pokr2[0][i]=0; str1[i]=arra[i]; } for(int i=0; i { stb1[i]=arrb[i]; } for(;;) { for(int i=0; i { if(stb1[i]>0) { str_min1=stb1[i]; break; } } for(int i=0; i if(stb1[i] str_min1=stb1[i]; for(int i=0; i { if(stb1[i]==str_min1) { x=i; break; } } for(int i=0, j=0; i { if(arr[x][i]==1) { if(j==0) { stb_max1=str1[i]; j++; } if(str1[i]>stb_max1) stb_max1=str1[i]; } } for(int i=0; i { if(str1[i]==stb_max1 && arr[x][i]==1) { y=i; pokr2[0][y]=1; str1[y]=0; for(int j=0; j { if(arr[j][y]==1) { stb1[j]=0; for(int k=0; k if(arr[j][k]==1 && k!=y) str1[k]--; } } break; } } int z=0; for(int i=0; i z+=stb1[i]; if(z==0) break; } Flag = 1; Form3->Caption = "Метод Закревского"; Form3->Show(); } //--------------------------------------------------------------------------- void __fastcall TForm2::Image1MouseDown(TObject *Sender, TMouseButton Button, TShiftState Shift, int X, int Y) { if(c==0) { X=X/10*10; Y=Y/10*10; if(Image1->Canvas->Pixels[X+5][Y+5]==clWhite) { arr[Y/10][X/10]=1; arra[X/10]++; arrb[Y/10]++; Image1->Canvas->Brush->Color=clActiveCaption; } else { arr[Y/10][X/10]=0; arra[X/10]--; arrb[Y/10]--; Image1->Canvas->Brush->Color=clWhite; } Image1->Canvas->FillRect(Rect(X+1,Y+1,X+10,Y+10)); }} //--------------------------------------------------------------------------- void __fastcall TForm2::N5Click(TObject *Sender) { Form1->Close(); } //--------------------------------------------------------------------------- void __fastcall TForm2::N4Click(TObject *Sender) { Form1->Visible=true; // Form5->Visible=true; Form2->Visible=false; } //--------------------------------------------------------------------------- void __fastcall TForm2::N6Click(TObject *Sender) { for(int i=0;i { for(int j=0;j { if(arrb[i]==0 || arra[j]==0) { Application->MessageBox("Неправильно ввели матрицу! \n Пожалуйста, проверьте начальные данные", "Ошибка!"); Abort(); } } } int x, y, res, *str, *stb, str_max, stb_min; res=1; q=1; pokr=new int*[res]; pokr[0]=new int[b]; str=new int[b]; stb=new int[a]; for(int i=0;i { pokr[0][i]=0; str[i]=arrb[i]; } for(int i=0; i { stb[i]=arra[i]; } for(;;) { for(int i=0; i { if(stb[i]>0) { stb_min=stb[i]; break; } } for(int i=0; i if(stb[i] stb_min=stb[i]; for(int i=0; i { if(stb[i]==stb_min) { x=i; break; } } for(int i=0, j=0; i { if(arr[i][x]==1) { if(j==0) { str_max=str[i]; j++; } if(str[i]>str_max) str_max=str[i]; } } for(int i=0; i { if(str[i]==str_max && arr[i][x]==1) { y=i; pokr[0][y]=1; str[y]=0; for(int j=0; j { if(arr[y][j]==1) { stb[j]=0; for(int k=0; k if(arr[k][j]==1 && k!=y) str[k]--; } } break; } } int z=0; for(int i=0; i z+=stb[i]; if(z==0) break; } delete []str; delete []stb; int x1, y1, res1, *str1, *stb1, str_min1, stb_max1; q=1; pokr2=new int*[res1]; pokr2[0]=new int[b]; str1=new int[a]; stb1=new int[b]; for(int i=0;i { pokr2[0][i]=0; str1[i]=arra[i]; } for(int i=0; i { stb1[i]=arrb[i]; } for(;;) { for(int i=0; i { if(stb1[i]>0) { str_min1=stb1[i]; break; } } for(int i=0; i if(stb1[i] str_min1=stb1[i]; for(int i=0; i { if(stb1[i]==str_min1) { x=i; break; } } for(int i=0, j=0; i { if(arr[x][i]==1) { if(j==0) { stb_max1=str1[i]; j++; } if(str1[i]>stb_max1) stb_max1=str1[i]; } } for(int i=0; i { if(str1[i]==stb_max1 && arr[x][i]==1) { y=i; pokr2[0][y]=1; str1[y]=0; for(int j=0; j { if(arr[j][y]==1) { stb1[j]=0; for(int k=0; k if(arr[j][k]==1 && k!=y) str1[k]--; } } break; } } int z=0; for(int i=0; i z+=stb1[i]; if(z==0) break; } Flag = 1; Form3->Caption = "Метод предварительного редуцирования"; Form3->Show(); } //--------------------------------------------------------------------------- Unit3.cpp //--------------------------------------------------------------------------- #include #pragma hdrstop #include "Unit5.h" #include "Unit4.h" #include "Unit3.h" #include "Unit2.h" #include "Unit1.h" //--------------------------------------------------------------------------- #pragma package(smart_init) #pragma resource "*.dfm" TForm3 *Form3; extern int b, a, q, **pokr,**pokr2 ,**arr,Flag; int wert = 0,wert2 = 0; //--------------------------------------------------------------------------- __fastcall TForm3::TForm3(TComponent* Owner) : TForm(Owner) { } //--------------------------------------------------------------------------- void __fastcall TForm3::FormShow(TObject *Sender) { Image1->Hide(); q = 1; Image1->Width=10*q; Image1->Height=10*b; for(int i=0; i { Image1->Canvas->MoveTo(0, i*Image1->Height/b); Image1->Canvas->LineTo(Image1->Width, i*Image1->Height/b); } for(int j=0; j { Image1->Canvas->MoveTo(j*Image1->Width/q, 0); Image1->Canvas->LineTo(j*Image1->Width/q, Image1->Height); } //Image1->Canvas->Brush->Color=clActiveCaption; for(int i=0;i { for(int j=0;j { if(pokr[i][j]==1) { Image1->Canvas->Brush->Color=clActiveCaption; wert++; } else Image1->Canvas->Brush->Color=clWhite; Image1->Canvas->FillRect(Rect(10*i+1,10*j+1,10*i+10,10*j+10)); } } Image2->Hide(); Label4->Caption=IntToStr(wert); Label6->Caption=IntToStr(wert2) ; Image1->Show(); wert = 0; wert2 = 0; if (Flag == 1) { Image2->Show(); Image2->Width=10*a; Image2->Height=10*q; for(int i=0; i { Image2->Canvas->MoveTo(0, i*Image2->Height/q); Image2->Canvas->LineTo(Image2->Width, i*Image2->Height/q); }