|
p align="left"> Покрытие методом Патрика Покрытия методом Закревского 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)); } } }} //--------------------------------------------------------------------------- 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<a;i++) arra_copy[i]=arra[i]; for(int i=0;i<b;i++) { arrb_copy[i]=arrb[i]; arr_copy[i]=new int[a]; for(int j=0; j<a; j++) arr_copy[i][j]=arr[i][j]; } for(int i=0;i<b; i++) { for(int j=0;j<a;j++) { if(arrb_copy[i]==0 || arra_copy[j]==0) { Application->MessageBox("Слишком маленькое значение вероятности", "Ошибка"); Abort(); } } } if(a*b>36) { for(int i=0; i<b; i++) { if(arrb_copy[i]>0) { for(int temp, j=i+1; j<b; j++) { if(arrb_copy[j]>0 && arrb_copy[i]>0) { int z; temp=0; for(int k=0; k<a; 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<a; k++) { if(arr_copy[z][k]==1) arra_copy[k]--; arr_copy[z][k]=0; } arrb_copy[z]=0; } } } } } for(int i=0; i<a; i++) { if(arra_copy[i]>0) { for(int temp, j=i+1; j<a; j++) { if(arra_copy[j]>0) { int z; temp=0; for(int k=0; k<b; 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<b; 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<a; 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<res; i++) { pokr1[i]=new int[b]; for(int j=0; j<b; j++) pokr1[i][j]=0; } for(;;) { for(int i=0; i<a; i++) { counter1[i]=counter2[i]; if(arra_copy[i]>0) { for(int j=0; j<b; 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;
Страницы: 1, 2, 3
| 
