Курсовая работа: Алгоритмы поиска кратчайших покрытий булевых матриц
💣 👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Микроэлектроника является одним из наиболее быстро и эффективно развивающихся направлений науки и техники. Однако вместе с развитием схемотехники увеличивается и сложность разрабатываемых схем. Существуют элементы схемы, логической моделью которых является матрица, в частности, булева. Площадь микросхемы и ее быстродействие во многом зависят от параметров матрицы. Поэтому приоритетной задачей является уменьшение размеров элемента, например, путем нахождения кратчайшего покрытия булевых матриц. Целесообразность поиска кратчайших покрытий возникает и при минимизации ДНФ булевых функций, при синтезе логических схем некоторых типов, при решении систем логических уравнений, при поиске простейших диагностических тестов, а так же во многих других задачах, эффективность методов решения которых, оказывается, существенно зависящей от совершенства используемых алгоритмов поиска кратчайших покрытий.
Алгоритмы нахождения кратчайших покрытий – занятие трудоемкое для человека, особенно при сравнительно большой размерности матрицы, поэтому разработанная мною программа значительно упрощает выполнение этой работы.
Рассмотрим задачу о переводчиках [1]. Допустим, из некоторого числа переводчиков, каждый из которых владеет несколькими определенными языками, требуется скомплектовать минимальную по числу членов группу такую, чтобы она смогла обеспечить перевод с любого из интересующих нас языков.
Решение данной задачи легко находиться с помощью нахождения кратчайшего покрытия булевой матрицы, составленной по условию.
Если обозначить множество переводчиков, из которого можно производить выбор, через A={a, б, в, г, д}, а множество интересующих нас языков через B={1,2,3,4,5,6}. То можно ввести булеву матрицу C отношения переводчиков к языкам.
Это означает, что переводчик а знает языки 1,3, переводчик б – языки 4,5 и т.д.
Таким образом, данная задача сводится к задаче нахождения кратчайшего покрытия булевой матрицы С, то есть нахождения такой минимальной совокупности строк матрицы, которая содержала бы не менее одной единицы в каждом столбце матрицы.
Булевой матрицей называется матрица, элементы которой – либо 0, либо 1.
Говорят, что i-я строка покрывает j-й столбец, если на их пересечении стоит единица, то есть =1. Причем каждая строка обязательно покрывает некоторое подмножество столбцов, а каждый столбец покрывается хотя бы одной строкой.
Подмножество строк матрицы B, в совокупности покрывающее все ее столбцы, образует строчное покрытие этой матрицы.
Подмножество столбцов матрицы B, в совокупности покрывающее все ее строки, образует столбцовое покрытие этой матрицы.
Покрытие, содержащее минимальное число строк (столбцов) матрицы B, называется кратчайшим покрытием матрицы B.
Множество строк матрицы B {а, в, г, е, ж} – одно из строчных покрытий этой матрицы. Множество же строк {д, е, з} – одно из кратчайших строчных покрытий матрицы B.
3. АЛГОРИТМЫ ПОИСКА КРАТЧАЙШИХ ПОКРЫТИЙ
Ниже приведены алгоритмы нахождения кратчайших покрытий методом Патрика [5] и методом Закревского [1].
Если требуется найти все кратчайшие покрытия булевой матрицы, можно найти все ее покрытия и выделить из них кратчайшие. Это реализуется на следующем примере.
распишем, какие строчки покрывают определенный столбец в виде дизъюнкций.
Первый столбец могут покрыть а Ú д, второй – в Ú д, третий – а Ú г Ú д, четвертый – б Ú в, пятый – б Ú г Ú д, и шестой – г. Теперь составим конъюнкцию данных дизъюнкций и раскроем скобки:
(а Ú д)(в Ú д)(а Ú г Ú д)(б Ú в)(б Ú г Ú д)г = авг Ú бгд Ú вгд Ú абвг Ú бвгд Ú абвгд.
Отсюда видно, что кратчайшее покрытие булевой матрицы С – либо {а, в, г}, либо {б, г, д}, либо {в, г, д}.
Это нахождение покрытий перебором на ЭВМ реализуется для исходной матрицы небольшого размера (до 7 х 7), чтобы реализовать метод Патрика для немногим больших матриц, рекомендуется оптимизировать матрицу.
Аркадий Дмитриевич Закревский предложил довольно эффективный и простой способ нахождения малой величины покрытия булевой матрицы (так называемое разложение по минимальному столбцу и минимальной строке).
Замечание: все случаи просчитывались как вручную, так и на ЭВМ при помощи разработанной программы.
Алгоритм нахождения строчного покрытия методом Закревского:
1. Ищется столбец с минимальным числом единиц. Если таковых несколько, то выбирается любой (для определенности, допустим, самый левый).
2. Среди строк, покрывающих этот столбец, ищется строка с максимальным числом единиц и заносится в покрытие (следовательно, удаляется из матрицы); если же таких строк несколько, то выбирается любая из них (для определенности, допустим, самая верхняя).
3. Удаляются все столбцы, которые покрывает полученная строка.
Действия продолжаем до тех пор, пока не удалится вся матрица.
Пример 3. Найдем кратчайшее строчное покрытие матрицы С:
1. Столбец 6 содержит минимальное число единиц – 1.
2. Строка г заносится в покрытие и удаляется из матрицы.
Далее проводим аналогичные действия с матрицей С:
1. Столбец 1 (самый левый) содержит только 2 единицы.
2. Строка д, покрывающая этот столбец, покрывает 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, 8 и 10 (поглощают столбец 4), столбцы 3 и 7 (равны столбцу 9) и столбец 6 (равен столбцу 4). В итоге получаем матрицу (4 х 3):
Удаляем строки а, к (поглощаются строкой г). Получаем матрицу ( 2 х 3 ):
Из последней матрицы удаляем столбец 9 (равен столбцу 5) и получаем не упрощаемую матрицу ( 2 х 2 ):
Единственное покрытие последней матрицы – она сама. Итого, строки г и и составляют одно из кратчайших (даже единственное) покрытий матрицы A.
Написанная мной на ЭВМ программа «Нахождение кратчайшего покрытия булевых матриц» помогает вручную не искать покрытие заданной или генерируемой булевой матрицы до размера 99 х 99, а предоставить это компьютеру.
Интегрированная Среда Разработки BorlandC++ Builder 6.0.
Поддерживаемые операционные системы:
Система для тестирования программы:
Pentium-4 ~2.3 Gh, 512 MbDDR, WindowsXPSP2.
Pokrytie.exe – откомпилированная и отлаженная программа. При запуске отображается окно дополнительной информации:
При нажатии двойным щелчком на кнопку «Программа» в окне появляется основная форма — Меню программы (рис. 1).
Рис.1. Меню программы Рис.2. Задание вероятности единицы
Требуется ввести число строк и столбцов матрицы, а также выбрать тип создания требуемой матрицы: вручную или автоматически (с помощью компьютера). В первом случае возможны 2 способа создания пустого шаблона матрицы: все поля – либо нули, либо единицы (для реализации необходимо это просто отметить). Во втором же должна быть введена вероятность создания единицы в определенном месте матрицы (рис. 2).
По умолчанию все элементы матрицы – нули и программа допускает присутствие в матрице нулевых строк и столбцов. Если вы не ввели параметры матрицы до конца, то при нажатии кнопки «Сгенерировать» программа сообщит вам об этом:
При правильном вводе данных и нажатии кнопки генерации на экране появляется окно ввода матрицы:
При написании программы я применила графический способ ввода элементов матрицы: внутри прямоугольника, соответствующего размерам матрицы, чтобы изменить значение определенного элемента матрицы, необходимо нажать кнопку мыши при положении курсора внутри определенного квадрата, соответствующего этому элементу. Белый цвет соответствует нулю, а цвет выделяемого текста (по умолчанию – синий) соответствует единице. Для хранения данных в программе использованы динамические матрицы, что позволяет выделять память только по мере необходимости.
Рассмотрим несколько примеров, иллюстрирующих работу программы.
5.3.1 Пример 1. Пусть дана матрица С:
Построим для этой матрицы кратчайшие покрытия методами Патрика и Закревского (строчное и столбцовое).
Итого, покрытия, построенные программой, совпадают с покрытиями, построенными вручную.
5.3.2 Пример 2. Построим кратчайшее покрытие для произвольной матрицы размером 7×7 с плотностью единицы 0,2 методом Патрика и методом Закревского:
Матрица, сгенерированная программой:
5.3.3 Пример 3.Построим кратчайшее покрытие для произвольной матрицы размером 30×30 с плотностью единицы 0,3 методом Закревского
Матрица, сгенерированная программой
Длина покрытия булевой матрицы – это число строк (столбцов), образующих покрытие этой матрицы.
С помощью созданной программы можно проследить зависимость длины покрытия матрицы (L) от плотности единицы (P) в ней.
Построим график зависимости для матриц размерности 7×7, для этого сделаем 10 попыток на каждую вероятность. По оси абсцисс отложим плотность единицы в матрице, а по другой оси среднее значение длины покрытия при заданной плотности.
Видно, что при достаточно малых размерностях матрицы, всего 7×7, средняя длина покрытия почти совпадает.
Построим график для метода Закревского для матриц 10×10, для этого сделаем 20 попыток на каждое значение вероятности:
В результате выполнения курсовой работы мною была разработана и отлажена программа, позволяющая находить кратчайшие покрытия булевых матриц размером до 100×100 методом Патрика (см. раздел 3.1) и методом Закревского (столбцовое и строчное покрытие) (см. раздел 3.2), а так же рассмотрен способ оптимизации (сокращения) булевых матриц (см. раздел 3.3).
Алгоритмы нахождения кратчайших покрытий – занятие трудоемкое для человека, особенно при сравнительно большой размерности матрицы, поэтому разработанная мною программа значительно упрощает выполнение этой работы.
Данные алгоритмы реализованы в интегрированной среде C++Builder6.0., которая является, на мой взгляд, наиболее подходящей для решения такого типа задач, поскольку позволяет создать наиболее удобный для пользователя интерфейс.
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
//---------------------------------------------------------------------------
void __fastcall TForm1::RadioButton2Click(TObject *Sender)
//---------------------------------------------------------------------------
void __fastcall TForm1::RadioButton1Click(TObject *Sender)
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
if(a*b==0 || (RadioButton2->Checked==true && MaskEdit1->EditText=="0"))
Application->MessageBox("Введите данные до конца или проверьте данные", Внимание!");
if((arrb[i]==0 || arra[j]==0) & RadioButton2->Checked==true)
{ Application->MessageBox("Попробуйте еще раз или введите другое значение вероятности", "Внимание!");
//---------------------------------------------------------------------------
void __fastcall TForm1::FormShow(TObject *Sender)
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
extern int **arr, *arra, *arrb,Flag;
//---------------------------------------------------------------------------
__fastcall TForm2::TForm2(TComponent* Owner)
//---------------------------------------------------------------------------
void __fastcall TForm2::FormClose(TObject *Sender, TCloseAction &Action)
//---------------------------------------------------------------------------
void __fastcall TForm2::FormShow(TObject *Sender)
Image1->Canvas->MoveTo(0, i*Image1->Height/b);
Image1->Canvas->LineTo(Image1->Width, i*Image1->Height/b);
Image1->Canvas->MoveTo(j*Image1->Width/a, 0);
Image1->Canvas->LineTo(j*Image1->Width/a, Image1->Height);
Image1->Canvas->Brush->Color=clActiveCaption;
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;
if(arrb_copy[i]==0 || arra_copy[j]==0)
Application->MessageBox("Слишком маленькое значение вероятности", "Ошибка");
if(arrb_copy[j]>0 && arrb_copy[i]>0)
if(arr_copy[i][k]==1 & arr_copy[j][k]==1)
if(arr_copy[k][i]==1 & arr_copy[k][j]==1)
if(counter2[i]>arra_copy[i] && counter2[a-1]<=arra_copy[a-1])
//---------------------------------------------------------------------------
void __fastcall TForm2::N3Click(TObject *Sender) //Строчный
{ Application->MessageBox("Неправильно ввели матрицу! \n Пожалуйста, проверьте начальные данные ", "Внимание!");
int x, y, res, *str, *stb, str_max, stb_min;
if(str[i]==str_max && arr[i][x]==1)
int x1, y1, res1, *str1, *stb1, str_min1, stb_max1; //Столбцовый
if(str1[i]==stb_max1 && arr[x][i]==1)
Form3->Caption = "МетодЗакревского";
//---------------------------------------------------------------------------
void __fastcall TForm2::Image1MouseDown(TObject *Sender,
TMouseButton Button, TShiftState Shift, int X, int Y)
if(Image1->Canvas->Pixels[X+5][Y+5]==clWhite)
Image1->Canvas->Brush->Color=clActiveCaption;
Image1->Canvas->Brush->Color=clWhite;
Image1->Canvas->FillRect(Rect(X+1,Y+1,X+10,Y+10));
//---------------------------------------------------------------------------
void __fastcall TForm2::N5Click(TObject *Sender)
//---------------------------------------------------------------------------
void __fastcall TForm2::N4Click(TObject *Sender)
//---------------------------------------------------------------------------
void __fastcall TForm2::N6Click(TObject *Sender)
{ Application->MessageBox("Неправильно ввели матрицу! \n Пожалуйста, проверьте начальные данные", "Ошибка!");
int x, y, res, *str, *stb, str_max, stb_min;
if(str[i]==str_max && arr[i][x]==1)
int x1, y1, res1, *str1, *stb1, str_min1, stb_max1;
if(str1[i]==stb_max1 && arr[x][i]==1)
Form3->Caption = "Метод предварительного редуцирования";
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
extern int b, a, q, **pokr,**pokr2 ,**arr,Flag;
//---------------------------------------------------------------------------
__fastcall TForm3::TForm3(TComponent* Owner)
//---------------------------------------------------------------------------
void __fastcall TForm3::FormShow(TObject *Sender)
Image1->Canvas->MoveTo(0, i*Image1->Height/b);
Image1->Canvas->LineTo(Image1->Width, i*Image1->Height/b);
Image1->Canvas->MoveTo(j*Image1->Width/q, 0);
Image1->Canvas->LineTo(j*Image1->Width/q, Image1->Height);
//Image1->Canvas->Brush->Color=clActiveCaption;
Image1->Canvas->Brush->Color=clActiveCaption;
Image1->Canvas->Brush->Color=clWhite;
Image1->Canvas->FillRect(Rect(10*i+1,10*j+1,10*i+10,10*j+10));
Image2->Canvas->MoveTo(0, i*Image2->Height/q);
Image2->Canvas->LineTo(Image2->Width, i*Image2->Height/q);
Image2->Canvas->MoveTo(j*Image2->Width/a, 0);
Image2->Canvas->LineTo(j*Image2->Width/a, Image2->Height);
//Image2->Canvas->Brush->Color=clActiveCaption;
Image2->Canvas->Brush->Color=clActiveCaption;
Image2->Canvas->Brush->Color=clWhite;
Image2->Canvas->FillRect(Rect(10*j+1,10*i+1,10*j+10,10*i+10));
//---------------------------------------------------------------------------
void __fastcall TForm3::N3Click(TObject *Sender)
//---------------------------------------------------------------------------
void __fastcall TForm3::N2Click(TObject *Sender)
//---------------------------------------------------------------------------
void __fastcall TForm3::N1Click(TObject *Sender)
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
extern int b, a, q, **pokr,**pokr2 ,**arr,Flag;
//---------------------------------------------------------------------------
__fastcall TForm4::TForm4(TComponent* Owner)
//---------------------------------------------------------------------------
void __fastcall TForm4::FormShow(TObject *Sender)
Image1->Canvas->MoveTo(0, i*Image1->Height/b);
Image1->Canvas->LineTo(Image1->Width, i*Image1->Height/b);
Image1->Canvas->MoveTo(j*Image1->Width/q, 0);
Image1->Canvas->LineTo(j*Image1->Width/q, Image1->Height);
Image1->Canvas->Brush->Color=clActiveCaption;
Image1->Canvas->FillRect(Rect(10*i+1,10*j+1,10*i+10,10*j+10));
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
__fastcall TForm5::TForm5(TComponent* Owner)
//---------------------------------------------------------------------------
void __fastcall TForm5::Button1Click(TObject *Sender)
Название: Алгоритмы поиска кратчайших покрытий булевых матриц
Раздел: Рефераты по информатике
Тип: курсовая работа
Добавлен 23:48:31 06 декабря 2010 Похожие работы
Просмотров: 370
Комментариев: 13
Оценило: 3 человек
Средний балл: 4.7
Оценка: неизвестно Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Ребятки, кто на FAST-REFERAT.RU будет заказывать работу до 26го мая - вводите промокод iphone, и тогда будете учавствовать в розыгрыше iphone xs)) сам только что узнал, что у них такие акции бывают (п.с. кстати не удивляйтесь что вас перекидывает на сайт с другим названием, так и должно быть)
Мне с моими работами постоянно помогают на FAST-REFERAT.RU - можете просто зайти узнать стоимость, никто вас ни к чему не обязывает, там впринципе всё могут сделать, вне зависимости от уровня сложности) у меня просто парень электронщик там какой то, тоже там бывает заказывает))
Спасибо, Оксаночка, за совет))) Заказал курсач, отчет по практике, 2 реферата и дипломную на REFERAT.GQ , все сдал на отлично, и нервы не пришлось тратить)
Я обычно любые готовые работы покупаю на сайте shop-referat.tk , и свои все там же на продажу выставляю, неплохой доп.заработок. А если там не нахожу то уже на referat.gq заказываю и мне быстро делают.
Да, но только в случае крайней необходимости.
Курсовая работа: Алгоритмы поиска кратчайших покрытий булевых матриц
Курсовая работа по теме Планування і контроль загальновиробничих витрат підприємства
Дипломная работа по теме Обработка результатов двух групп многократных измерений
Методичка На Тему Кручение
Курсовая работа по теме Анализ возможности применения методов многомерного анализа для классификации и оценки конкурентоспособности регионов
Реферат по теме Референдум-форма осуществления власти народом России
Курсовая работа: Стафилококки — возбудители пищевых токсикозов
Как Красиво Оформить Сказку Собственного Сочинения
Сочинение Литература 21 Века
Синтез броматов редкоземельных элементов
Контрольные Работы По Геометрии Параллельность Плоскостей
Геометрия 9 Контрольная Работа Векторы
Курсовая работа по теме Гепатит собак
Контрольная Работа На Тему Характеристика Металлического Состояния. Общая Характеристика Свойств Металлов
Пример Отзыва Научного Руководителя На Диссертацию
Лабораторная работа: Сущность, цели и задачи менеджмента
Реферат: Видавнича діяльність українських вчительських товариств
Курсовая работа по теме Лидерство как феномен группового развития
Реферат: Breaking The Chains Of Violence Essay Research
Реферат На Тему Отец Медицины, Философ - Гиппократ
Дипломная работа: Технологічна обробка дверних полотен
Курсовая работа: Расчет и конструирование газоразрядной индикаторной панели переменного тока
Реферат: Средства физической культуры, комплексы физических упражнений и восстановительные мероприятия в системе профилактики профессиональных заболеваний
Курсовая работа: Нові тенденції і прикладні аспекти інженерії знань