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

5

ВВЕДЕНИЕ

Микроэлектроника является одним из наиболее быстро и эффективно развивающихся направлений науки и техники. Однако вместе с развитием схемотехники увеличивается и сложность разрабатываемых схем. Существуют элементы схемы, логической моделью которых является матрица, в частности, булева. Площадь микросхемы и ее быстродействие во многом зависят от параметров матрицы. Поэтому приоритетной задачей является уменьшение размеров элемента, например, путем нахождения кратчайшего покрытия булевых матриц. Целесообразность поиска кратчайших покрытий возникает и при минимизации ДНФ булевых функций, при синтезе логических схем некоторых типов, при решении систем логических уравнений, при поиске простейших диагностических тестов, а так же во многих других задачах, эффективность методов решения которых, оказывается, существенно зависящей от совершенства используемых алгоритмов поиска кратчайших покрытий.

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

1. ПОСТАНОВКА ЗАДАЧИ

Рассмотрим задачу о переводчиках [1]. Допустим, из некоторого числа переводчиков, каждый из которых владеет несколькими определенными языками, требуется скомплектовать минимальную по числу членов группу такую, чтобы она смогла обеспечить перевод с любого из интересующих нас языков.

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

Если обозначить множество переводчиков, из которого можно производить выбор, через A={a, б, в, г, д}, а множество интересующих нас языков через B={1,2,3,4,5,6}. То можно ввести булеву матрицу C отношения переводчиков к языкам.

1 2 3 4 5 6

.

Это означает, что переводчик а знает языки 1,3, переводчик б - языки 4,5 и т.д.

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

2. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Булевой матрицей называется матрица, элементы которой - либо 0, либо 1.

, {0, 1}.

Говорят, что i-я строка покрывает j-й столбец, если на их пересечении стоит единица, то есть =1. Причем каждая строка обязательно покрывает некоторое подмножество столбцов, а каждый столбец покрывается хотя бы одной строкой.

Подмножество строк матрицы B, в совокупности покрывающее все ее столбцы, образует строчное покрытие этой матрицы.

Подмножество столбцов матрицы B, в совокупности покрывающее все ее строки, образует столбцовое покрытие этой матрицы.

Покрытие, содержащее минимальное число строк (столбцов) матрицы B, называется кратчайшим покрытием матрицы B.

Пример1.

1 2 3 4 5 6 7 8 9 10

.

Множество строк матрицы B {а, в, г, е, ж} - одно из строчных покрытий этой матрицы. Множество же строк {д, е, з} - одно из кратчайших строчных покрытий матрицы B.

3. АЛГОРИТМЫ ПОИСКА КРАТЧАЙШИХ ПОКРЫТИЙ

Ниже приведены алгоритмы нахождения кратчайших покрытий методом Патрика [5] и методом Закревского [1].

3.1 Метод Патрика

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

Пример 2. Для матрицы

.

распишем, какие строчки покрывают определенный столбец в виде дизъюнкций.

Первый столбец могут покрыть а д, второй - в д, третий - а г д, четвертый - б в, пятый - б г д, и шестой - г. Теперь составим конъюнкцию данных дизъюнкций и раскроем скобки:

(а д)(в д)(а г д)(б в)(б г д)г = авг бгд вгд абвг бвгд абвгд.

Отсюда видно, что кратчайшее покрытие булевой матрицы С - либо {а, в, г}, либо {б, г, д}, либо {в, г, д}.

Это нахождение покрытий перебором на ЭВМ реализуется для исходной матрицы небольшого размера (до 7 х 7), чтобы реализовать метод Патрика для немногим больших матриц, рекомендуется оптимизировать матрицу.

3.2 Метод Закревского

Аркадий Дмитриевич Закревский предложил довольно эффективный и простой способ нахождения малой величины покрытия булевой матрицы (так называемое разложение по минимальному столбцу и минимальной строке).

Замечание: все случаи просчитывались как вручную, так и на ЭВМ при помощи разработанной программы.

3.2.1 Строчное покрытие

Алгоритм нахождения строчного покрытия методом Закревского:

1. Ищется столбец с минимальным числом единиц. Если таковых несколько, то выбирается любой (для определенности, допустим, самый левый).

2. Среди строк, покрывающих этот столбец, ищется строка с максимальным числом единиц и заносится в покрытие (следовательно, удаляется из матрицы); если же таких строк несколько, то выбирается любая из них (для определенности, допустим, самая верхняя).

3. Удаляются все столбцы, которые покрывает полученная строка.

Действия продолжаем до тех пор, пока не удалится вся матрица.

Пример 3. Найдем кратчайшее строчное покрытие матрицы С:

1 2 3 4 5 6

.

1. Столбец 6 содержит минимальное число единиц - 1.

2. Строка г заносится в покрытие и удаляется из матрицы.

3. Удаляются столбцы 3, 5, 6.

Получаем матрицу

1 2 4

.

Далее проводим аналогичные действия с матрицей С:

1. Столбец 1 (самый левый) содержит только 2 единицы.

2. Строка д, покрывающая этот столбец, покрывает 2 столбца, заносится в покрытие и удаляется из матрицы.

3. Удаляются столбцы 1, 2.

Остался только один столбец матрицы - 4. Можно выбрать как строку б, так и строку в, в обоих случаях мы имеем покрытие матрицы, состоящее из 3 строчек.

Итого получаем покрытия {б, г, д} и {в, г, д } - как показал метод Патрика - кратчайшие покрытия.

Замечание: Не всегда метод Закревского дает кратчайшее покрытие, оно может состоять и из большего числа строк, но находится быстрее.

Столбцовое покрытие

Алгоритм нахождения столбцового покрытия методом Закревского:

1. Ищется строка с минимальным числом единиц. Если таковых несколько, то выбирается любая (для определенности, допустим, самая верхняя).

2. Среди столбцов, покрывающих эту строку, ищется столбец с максимальным числом единиц и заносится в покрытие (следовательно, удаляется из матрицы); если же таких столбцов несколько, то выбирается любой из них (для определенности, допустим, самый левый).

3. Удаляются все строки, которые покрывает полученный столбец.

Данные действия продолжаются до тех пор, пока не удалится вся матрица.

Итого получим покрытие {3,4}-столбцовое покрытие исследуемой матрицы.

4. Метод предварительного редуцирования булевой матрицы

При поиске кратчайшего покрытия целесообразно уменьшить матрицу, если такое возможно. Можно удалить как определенные строки, так и определенные столбцы. Отметим, что в практических задачах не требуется найти все кратчайшие покрытия, достаточно только одно или несколько. Это упрощает алгоритм упрощения (сокращения) матрицы.

1. Говорят, что i-я строка булевой матрицы поглощает j-ю строку этой матрицы (), если на позициях единиц j-й строки в i-й - тоже «единицы», причем число единиц в i-й строке больше числа единиц в j-й строке (если же число единиц одинаково, то данные строки называются равными).

Аналогичное утверждение можно сформировать и для столбцов.

2. Говорят, что i-й столбец булевой матрицы поглощает j-й столбец этой матрицы (), если на позициях единиц j-го столбца в i-м - тоже единицы, причем число единиц в i-м столбце больше числа единиц в j-м столбце (если же число единиц одинаково, то данные столбцы называются равными).

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

Замечание: при реализации данного алгоритма на ЭВМ программа не удаляет строки (столбцы), что приводит к требующему ресурсы процессора созданию новых массивов, а «зануляет» их, затем игнорируя.

При поиске кратчайших покрытий предварительно сокращенной матрицы некоторые кратчайшие покрытия теряются, но это не имеет практической ценности, но объем вычислений сокращается.

Пример 4. Пусть дана булева матрица A (10 х 10):

1 2 3 4 5 6 7 8 9 10

.

Удаляем строки б и е (поглощаются строкой к), строки в, д, ж (поглощаются строкой и) и строку з (поглощается строкой г). Получим матрицу , уже меньшую по размерам:

1 2 3 4 5 6 7 8 9 10

.

Удаляем столбец 1 (поглощает любой другой столбец), столбцы 2, 8 и 10 (поглощают столбец 4), столбцы 3 и 7 (равны столбцу 9) и столбец 6 (равен столбцу 4). В итоге получаем матрицу (4 х 3):

4 5 9

.

Удаляем строки а, к (поглощаются строкой г). Получаем матрицу ( 2 х 3 ):

4 5 9

.

Из последней матрицы удаляем столбец 9 (равен столбцу 5) и получаем не упрощаемую матрицу ( 2 х 2 ):

4 5

.

Единственное покрытие последней матрицы - она сама. Итого, строки г и и составляют одно из кратчайших (даже единственное) покрытий матрицы A.

5. ПРОГРАММА

Написанная мной на ЭВМ программа «Нахождение кратчайшего покрытия булевых матриц» помогает вручную не искать покрытие заданной или генерируемой булевой матрицы до размера 99 х 99, а предоставить это компьютеру.

5.1 Описание программы

Средство программирования:

Интегрированная Среда Разработки Borland C++ Builder 6.0.

Поддерживаемые операционные системы:

Windows 95/98/ME/NT/2000/XP.

Система для тестирования программы:

Pentium-4 ~2.3 Gh, 512 Mb DDR, Windows XP SP2.

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));

} } }}

//---------------------------------------------------------------------------

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;

delete []counter1;

delete []counter2;

pokr_d=new int[res];

for(int i=0; i<res; i++)

{

pokr_d[i]=0;

for(int j=0; j<b; j++)

if(pokr1[i][j]==1)

pokr_d[i]++;

}

min=pokr_d[0];

for(int i=1; i<res; i++)

if(pokr_d[i]<min && pokr_d[i]>0)

min=pokr_d[i];

q=res;

for(int i=0; i<res; i++)

{

if(pokr_d[i]>min)

{

q--;

for(int j=0; j<b; j++)

pokr1[i][j]=0;

pokr_d[i]=0;

}

}

for(int i=0; i<res; i++)

{

if(pokr_d[i]!=0)

{

for(int temp, j=i+1; j<res; j++)

{

temp=0;

for(int k=0; k<b; k++)

{

if(pokr1[i][k]==pokr1[j][k])

temp++;

}

if(temp==b)

{

q--;

pokr_d[j]=0;

for(int k=0; k<b; k++)

pokr1[j][k]=0;

} } } }

pokr=new int*[q];

for(int i=0; i<q; i++)

pokr[i]=new int[b];

for(int i=0, j=0; i<res; i++)

{

if(pokr_d[i]>0)

{

for(int k=0; k<b; 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<b; i++)

{

for(int j=0;j<a;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<b;i++)

{

pokr[0][i]=0;

str[i]=arrb[i];

}

for(int i=0; i<a; i++)

{

stb[i]=arra[i];

}

for(;;)

{

for(int i=0; i<a; i++)

{

if(stb[i]>0)

{

stb_min=stb[i];

break;

} }

for(int i=0; i<a; i++)

if(stb[i]<stb_min && stb[i]!=0)

stb_min=stb[i];

for(int i=0; i<a; i++)

{

if(stb[i]==stb_min)

{

x=i;

break;

} }

for(int i=0, j=0; i<b; 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<b; i++)

{

if(str[i]==str_max && arr[i][x]==1)

{

y=i;

pokr[0][y]=1;

str[y]=0;

for(int j=0; j<a; j++)

{

if(arr[y][j]==1)

{

stb[j]=0;

for(int k=0; k<b; k++)

if(arr[k][j]==1 && k!=y)

str[k]--;

} }

break;

} }

int z=0;

for(int i=0; i<a; 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<a;i++)

{

pokr2[0][i]=0;

str1[i]=arra[i];

}

for(int i=0; i<b; i++)

{

stb1[i]=arrb[i];

}

for(;;)

{

for(int i=0; i<b; i++)

{

if(stb1[i]>0)

{

str_min1=stb1[i];

break;

} }

for(int i=0; i<b; i++)

if(stb1[i]<str_min1 && stb1[i]!=0)

str_min1=stb1[i];

for(int i=0; i<b; i++)

{

if(stb1[i]==str_min1)

{

x=i;

break;

} }

for(int i=0, j=0; i<a; 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<a; i++)

{

if(str1[i]==stb_max1 && arr[x][i]==1)

{

y=i;

pokr2[0][y]=1;

str1[y]=0;

for(int j=0; j<b; j++)

{

if(arr[j][y]==1)

{

stb1[j]=0;

for(int k=0; k<a; k++)

if(arr[j][k]==1 && k!=y)

str1[k]--;

} }

break;

} }

int z=0;

for(int i=0; i<b; 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<b; i++)

{

for(int j=0;j<a;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<b;i++)

{

pokr[0][i]=0;

str[i]=arrb[i];

}

for(int i=0; i<a; i++)

{

stb[i]=arra[i];

}

for(;;)

{

for(int i=0; i<a; i++)

{

if(stb[i]>0)

{

stb_min=stb[i];

break;

} }

for(int i=0; i<a; i++)

if(stb[i]<stb_min && stb[i]!=0)

stb_min=stb[i];

for(int i=0; i<a; i++)

{

if(stb[i]==stb_min)

{

x=i;

break;

} }

for(int i=0, j=0; i<b; 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<b; i++)

{

if(str[i]==str_max && arr[i][x]==1)

{

y=i;

pokr[0][y]=1;

str[y]=0;

for(int j=0; j<a; j++)

{

if(arr[y][j]==1)

{

stb[j]=0;

for(int k=0; k<b; k++)

if(arr[k][j]==1 && k!=y)

str[k]--;

}

}

break;

} }

int z=0;

for(int i=0; i<a; 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<a;i++)

{

pokr2[0][i]=0;

str1[i]=arra[i];

}

for(int i=0; i<b; i++)

{

stb1[i]=arrb[i];

}

for(;;)

{

for(int i=0; i<b; i++)

{

if(stb1[i]>0)

{

str_min1=stb1[i];

break;

} }

for(int i=0; i<b; i++)

if(stb1[i]<str_min1 && stb1[i]!=0)

str_min1=stb1[i];

for(int i=0; i<b; i++)

{

if(stb1[i]==str_min1)

{

x=i;

break;

} }

for(int i=0, j=0; i<a; 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<a; i++)

{

if(str1[i]==stb_max1 && arr[x][i]==1)

{

y=i;

pokr2[0][y]=1;

str1[y]=0;

for(int j=0; j<b; j++)

{

if(arr[j][y]==1)

{

stb1[j]=0;

for(int k=0; k<a; k++)

if(arr[j][k]==1 && k!=y)

str1[k]--;

} }

break;

} }

int z=0;

for(int i=0; i<b; i++)

z+=stb1[i];

if(z==0)

break;

}

Flag = 1;

Form3->Caption = "Метод предварительного редуцирования";

Form3->Show();

}

//---------------------------------------------------------------------------

Unit3.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"

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<b; i++)

{

Image1->Canvas->MoveTo(0, i*Image1->Height/b);

Image1->Canvas->LineTo(Image1->Width, i*Image1->Height/b);

}

for(int j=0; j<q; 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<q;i++)

{

for(int j=0;j<b;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<b; i++)

{

Image2->Canvas->MoveTo(0, i*Image2->Height/q);

Image2->Canvas->LineTo(Image2->Width, i*Image2->Height/q);

}

for(int j=0; j<a; j++)

{

Image2->Canvas->MoveTo(j*Image2->Width/a, 0);

Image2->Canvas->LineTo(j*Image2->Width/a, Image2->Height);

}

//Image2->Canvas->Brush->Color=clActiveCaption;

for(int i=0;i<q;i++)

{

for(int j=0;j<a;j++)

{

if(pokr2[i][j]==1)

{

Image2->Canvas->Brush->Color=clActiveCaption;

wert2++;

}

else

Image2->Canvas->Brush->Color=clWhite;

Image2->Canvas->FillRect(Rect(10*j+1,10*i+1,10*j+10,10*i+10));

}

}

Label6->Caption=IntToStr(wert2) ;

wert2 = 0;

}

delete []pokr;

delete []pokr2;

}

//---------------------------------------------------------------------------

void __fastcall TForm3::N3Click(TObject *Sender)

{

Form2->Visible=false;

Form3->Visible=false;

Form1->Visible=false;

}

//---------------------------------------------------------------------------

void __fastcall TForm3::N2Click(TObject *Sender)

{

Form3->Visible=false;

}

//---------------------------------------------------------------------------

void __fastcall TForm3::N1Click(TObject *Sender)

{

Form1->Show();

}

//---------------------------------------------------------------------------

Unit4.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"

TForm4 *Form4;

extern int b, a, q, **pokr,**pokr2 ,**arr,Flag;

//---------------------------------------------------------------------------

__fastcall TForm4::TForm4(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

void __fastcall TForm4::FormShow(TObject *Sender)

{

Image1->Width=10*q;

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<q; 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<q;i++)

{

for(int j=0;j<b;j++)

{

if(pokr[i][j]==1)

Image1->Canvas->FillRect(Rect(10*i+1,10*j+1,10*i+10,10*j+10));

} }

delete []pokr;

}

Unit5.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"

TForm5 *Form5;

//---------------------------------------------------------------------------

__fastcall TForm5::TForm5(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

void __fastcall TForm5::Button1Click(TObject *Sender)

{

Form1->Show();

Form5->Close();

}