Автор работы: Пользователь скрыл имя, 20 Мая 2013 в 14:54, курсовая работа
При конструкторском проектировании ЭВС решаются задачи, связанные с поиском наилучшего варианта конструкции, удовлетворяющего требованиям технического задания и максимально учитывающего возможности технологической базы производства. Тесная взаимосвязанность задач и большая размерность каждой из них обычно не позволяет предложить метод поиска конструктивного оптимального решения в едином цикле в связи с трудностями создания общей математической модели, комплексно учитывающей особенности конструкторско-технологической базы производства. Поэтому разработка и реализация алгоритмов и методов решения отдельных задач этапа конструкторского проектирования: компоновки, размещения и трассировки, до сих пор остаются актуальными проблемами, решение которых неотъемлемо связано с развитием систем автоматизации проектирования.
Введение…………………………………………………………………………...3
1.Теоретическая часть…………………………………………………………….4
1.1. Постановка задачи компоновки………………………………………4
1.2. Алгоритмы компоновки……………………………………………….4
1.3. Последовательный алгоритм разбиения графа G=(X,E) на кусков с числом вершин в каждом куске……………………………..7
2.Практическая часть……………………………………………………………..8
2.1. Решение задачи компоновки………………………………………….8
2.2.Инструкция пользователя……………………………………………10
3.Заключение……………………………………………………………………..12
4.Список использованной литературы…………………………………………13
Приложение. Листинг программы……………………………………………...14
п. 4. Формируем массив вершин смежных вершине x1.
Г(x1) = {x1 , x2 , x4 , x5, x6}
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x12 |
x13 |
x14 |
x15 |
x16 |
ρ | ||
x1 |
0 |
2 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
5 | |
x2 |
2 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
5 | |
x3 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
2 | |
x4 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
2 | |
x5 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 | |
А1 = |
x6 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
4 |
x12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 | |
x13 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
3 |
5 | |
x14 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
3 | |
x15 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2 | |
x16 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
3 |
0 |
1 |
0 |
5 |
п. 5. Количество элементов в массиве равно количеству элементов во втором куске разбиения, следовательно, кусок G2 сформирован G2 = {x1 , x2 , x4 , x5, x6}.
п. 8. Исключаем из G кусок G1 формируя матрицу А2.
x3 |
x12 |
x13 |
x14 |
x15 |
x16 |
ρ | ||
x3 |
0 |
0 |
0 |
0 |
0 |
1 |
1 | |
x12 |
0 |
0 |
1 |
0 |
0 |
0 |
1 | |
А2 = |
x13 |
0 |
1 |
0 |
1 |
0 |
3 |
5 |
x14 |
0 |
0 |
1 |
0 |
1 |
0 |
2 | |
x15 |
0 |
0 |
0 |
1 |
0 |
1 |
2 | |
x16 |
1 |
0 |
3 |
0 |
1 |
0 |
5 |
п.. Так как предпоследний кусок сформирован, то оставшиеся вершины составляют последний кусок, следовательно, кусок G3 сформирован G3 = {x3, x12 , x13, x14, x15, x16}.
п.10. Все куски сформированы, конец работы алгоритма.
1
2 2
Программа написана на языке Borland Delphi 7.0. Необходимая минимальная конфигурация компьютера для нормального функционирования программы: ОС Microsoft Windows 98/Me/2000/XP/Vista, процессор Pentium II 336 МГц, 64 МБ оперативной памяти, видеокарта 32 МБ.
Рис. 1
Для начала работы программы необходимо запустить файл «Project1.exe». В появившемся окне вводим общее количество элементов графа, в нашем случае 16, нажимаем на кнопку «Создать» (рис.2). Далее заполняем матрицу смежности. Это можно сделать вручную, определив количество вершин и нажав кнопку «создать» и заполнив матрицу смежности, либо загрузить заранее сохранённую структуру нажав на кнопку загрузить, в нужной папке выбрать файл «primer». После создания граф можно сохранить.
Затем вводим число кусков разбиения 3. Далее нажимаем кнопку «Задать» и вводим число элементов в каждом куске n1=5, n2=5, n3=6 соответственно.
После того как все данные введены можно запустить процедуру разбиения в пошаговом (кнопка пошагово) или не очень (кнопка разбить) режимах.
Рис. 2
В результат будут отображаться текущее состояние всех кусков разбиения, а в логе выводится все значимые шаги алгоритма (рис. 3).
Рис. 3
После завершения разбиения будет отображено окно с результатами (рис 4.): наборами вершин в группах и графическим представлением полученной компоновки - номера групп и количество связей между ними.
Рис. 4
В результате выполнения данной курсовой работы мною была:
1)Решена задача компоновки схемы на 3 куска, число элементов в каждом куске .
2)Написана программа «Project1», разрезающая произвольную схему соединений, представленную матрицей смежности, на 3 куска с заданным количеством элементов в каждом куске.
В результате была получена следующая компоновка, которая совпала с ручным счётом:
1
2 2
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ComCtrls, StdCtrls, Buttons, Grids, ExtCtrls, CLIPBRD, Menus;
type
Tgraph = class
public
versh, kuskov, step, currk, state:Integer;
vershVKuske, ls, alpha: array of Integer;
msmezh, itog:array of array of Integer;
indexs:array of Boolean;
teta:Boolean;
log:TStringList;
procedure razbit(turn:boolean);
procedure release;
procedure init;
end;
TForm1 = class(TForm)
pgc1: TPageControl;
ts5: TTabSheet;
strngrd1: TStringGrid;
grp4: TGroupBox;
grp3: TGroupBox;
btn5: TBitBtn;
strngrd2: TStringGrid;
grp2: TGroupBox;
edt2: TEdit;
btn1: TButton;
btn2: TButton;
lbl1: TLabel;
edt1: TEdit;
btn3: TButton;
grp1: TGroupBox;
grp5: TGroupBox;
dlgOpen1: TOpenDialog;
dlgSave1: TSaveDialog;
mmo1: TMemo;
lbl2: TLabel;
mmo2: TMemo;
btn4: TBitBtn;
btn6: TBitBtn;
btn7: TBitBtn;
pm1: TPopupMenu;
N1: TMenuItem;
procedure FormCreate(Sender: TObject);
procedure FormDestroy(Sender: TObject);
procedure btn3Click(Sender: TObject);
procedure stage1;
procedure stage2;
procedure stage3;
procedure stage4;
procedure stage5;
procedure btn4Click(Sender: TObject);
procedure btn5Click(Sender: TObject);
procedure btn6Click(Sender: TObject);
procedure strngrd1SetEditText(Sender: TObject; ACol, ARow: Integer;
const Value: String);
procedure btn7Click(Sender: TObject);
function start(turn:boolean):boolean;
procedure initmatrix();
procedure btn2Click(Sender: TObject);
procedure btn1Click(Sender: TObject);
procedure N1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
graph:TGraph;
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure SGCopyToCLP(SG: TStringGrid; CopySel: Boolean; CL: integer = -1;
RT: integer = -1; CR: integer = -1; RB: integer = -1);
var
i, j: Integer;
s: string;
begin
s := '';
with SG do
begin
if CopySel then
begin
CL := Selection.Left;
CR := Selection.Right;
RT := Selection.Top;
RB := Selection.Bottom;
end;
//при необходимости FixedRows и FixedCols можно заменить на 0
if (CL < FixedCols) or (CL > CR) or (CL >= ColCount) then
CL := FixedCols;
if (CR < FixedCols) or (CL > CR) or (CR >= ColCount) then
CR := ColCount - 1;
if (RT < FixedRows) or (RT > RB) or (RT >= RowCount) then
RT := FixedRows;
if (RB < FixedCols) or (RT > RB) or (RB >= RowCount) then
RB := RowCount - 1;
for i := RT to RB do
begin
for j := CL to CR do
begin
s := s + Cells[j, i];
if j < CR then
s := s + #9;
end;
s := s + #13#10;
end;
end;
Clipboard.AsText := s;
end;
function isUInt(str:string):Boolean;
var i:Integer;
begin
result:=True;
if Length(str)=0 then result:= False;
for i:=1 to Length(str) do
if Pos(str[i],'1234567890')=0 then begin
result:=False;
Break;
end;
end;
procedure TGraph.init;
begin
log := TStringList.Create;
end;
procedure TGraph.razbit(turn:boolean);
var
i0,i1,maxls,sum,minid:Integer;
fnd:Boolean;
tmpstr:string;
begin
repeat
teta:=False;
case state of
0: begin
i1:=0;
maxls:=-1;
//fnd max
for i0:= 0 to versh-1 do begin
if not indexs[i0] then Continue;
if ls[i0] > maxls then begin
maxls := ls[i0];
i1:=i0;
end;
end;
state := 1;
Inc(step);
itog[currk][0] := 1;
itog[currk][1] := i1;
log.Append('Шаг '+Inttostr(step)+ ': Выбран элемент с наибольшей локальной степенью х'
+inttostr(i1+1));
end;
1: begin
tmpstr:='x'+IntToStr(itog[
for i0:= 0 to versh-1 do begin
if not indexs[i0] then Continue;
if (i0<>itog[currk][1])and(
Inc(itog[currk][0]);
itog[currk][itog[currk][0]] := i0;
tmpstr:=tmpstr+'x'+IntToStr(
end;
end;
state := 2;
Inc(step);
log.Append('Шаг '+Inttostr(step)+ ': Сформирован массив смежных вершин состоящий из: '
+tmpstr);
end;
2: begin
if itog[currk][0] <> vershVKuske[currk] then begin
for i0:= 0 to versh-1 do begin
if not indexs[i0] then Continue;
sum:=0;
for i1 := 1 to itog[currk][0] do
if msmezh[i0][itog[currk][i1]] <> 0 then
//Inc(sum);
sum := sum + msmezh[i0][itog[currk][i1]];
alpha[i0] := sum;
end;
if itog[currk][0] < vershVKuske[currk] then begin//polu4ili men'she
minid:=-1;
for i0:= 0 to versh-1 do begin
if not indexs[i0] then Continue;
fnd := False;
for i1 := 1 to itog[currk][0] do
if (itog[currk][i1] = i0) then begin
fnd := True;
Break;
end;
if not fnd then begin
if (minid = -1) or ((ls[i0] - alpha[i0]) < (ls[minid] - alpha[minid]))
or (((ls[i0] - alpha[i0]) = (ls[minid] - alpha[minid]))
and (ls[i0] > ls[minid])) then
minid := i0;
end;
end;
Inc(itog[currk][0]);
itog[currk][itog[currk][0]] := minid;
log.Append('Шаг '+Inttostr(step+1)+ ': В массив смежных вершин добавлена вершина х'+
Inttostr(minid+1));
teta:=True;
end
else begin
minid:= itog[currk][2];
for i1 := 3 to itog[currk][0] do
if alpha[minid] > alpha[itog[currk][i1]] then
minid:=itog[currk][i1];
for i1 := 1 to itog[currk][0] do
if itog[currk][i1] = minid then begin
itog[currk][i1]:=itog[currk][
end;
Dec(itog[currk][0]);
log.Append('Шаг '+Inttostr(step+1)+ ': Из массива смежных вершин удалена вершина х'+
Inttostr(minid+1));
end;
end
else begin
log.Append('Шаг '+Inttostr(step+1)+ ': Очередной кусок сформирован');
state:=3;
end;
Inc(step);
end;
3: begin
i1 := 1;
tmpstr:='';
While i1 <= itog[currk][0] do begin
i0 := 0;
while i0 < versh do begin
if (itog[currk][i1] = i0) then begin
indexs[i0] := false;
tmpstr:=tmpstr+'x'+IntToStr(
Break;
end;
Inc(i0);
end;
Inc(i1);
end;
state:=0;
Inc(currk);
inc(step);
log.Append('Шаг '+Inttostr(step)+ ': Из матрицы смежности удалены вершины: '+tmpstr);
for i0 := 1 to versh do begin
if not indexs[i0-1] then Continue;
sum := 0;
for i1 := 1 to versh do begin
if not indexs[i1-1] then Continue;
if msmezh[i0-1,i1-1] <> 0 then
sum := sum + msmezh[i0-1,i1-1];
//Inc(sum);
end;
ls[i0-1]:=sum;
end;
if (currk = kuskov-1) then begin
state :=4;
end;
end;
4: begin
for i0:= 0 to versh-1 do begin
if not indexs[i0] then Continue;
Inc(itog[currk][0]);
itog[currk][itog[currk][0]] := i0;
end;
Inc(currk);
Inc(step);
log.Append('Шаг '+Inttostr(step)+ ': Оставшиеся вершины составляют последний кусок разбиения, конец работы алгоритма');
end;
end;
until ((turn) or (currk = (kuskov)));
if (currk = kuskov) then begin
step:=0;
currk:=0;
end;
end;
procedure TGraph.release;
var
i0:Integer;
begin
versh :=0;
kuskov := 0;
step := 0;
currk := 0;
SetLength(vershVKuske, 0);
SetLength(ls, 0);