Автор: Пользователь скрыл имя, 03 Марта 2013 в 03:36, курсовая работа
При конструкторском проектировании ЭВС решаются задачи, связанные с поиском наилучшего варианта конструкции, удовлетворяющего требованиям технического задания и максимально учитывающего возможности технологической базы производства. Тесная взаимосвязанность задач и большая размерность каждой из них обычно не позволяет предложить метод поиска конструктивного оптимального решения в едином цикле в связи с трудностями создания общей математической модели, комплексно учитывающей особенности конструкторско-технологической базы производства. Поэтому разработка и реализация алгоритмов и методов решения отдельных задач этапа конструкторского проектирования: компоновки, размещения и трассировки,- до сих пор остаются актуальными проблемами, решение которых неотъемлемо связано с развитием систем автоматизации проектирования.
Введение…………………………………………………………… 3
1. Теоретическая часть
1.1 Алгоритмы компоновки……….…………………………..….. 4
1.2 Последовательный алгоритм компоновки ………………….. 5
1.3 Алгоритм компоновки……………………..………………….. 6
2. Практическая часть
2.1 Анализ задания………………………………………………… 8
2.2 Инструкция пользователя…..…….………………………….. 10
3. Заключение…………………………………………….….……… 14
4. Список используемой литературы……………………….….… 15
5. Приложение
5.1 Листинг программы………………………………………….... 16
5.2 Ручной счет…………………………………………………….. 31
getch(); return 1; }
/*---------------------------*
tp.c=0;
tp.m=(int*)calloc(mr.c, sizeof(int));
if(tp.m == NULL)
{ printf("\nError: tp.m == NULL !");
getch(); return 1; }
/*---------------------------*
for(i=0; i < g.c; i++)
{
for(j=0; j < mr.c; j++)
{
if(mr.m[j][(g.m[i]-1)] > 0)
{
pr=0;
for(k=0; k < g.c; k++)
{
if((j+1) == g.m[k])
{
pr=1;
break;
}
}
if(pr == 0)
{
for(k=0; k < tp.c; k++)
{
if(tp.m[k] == (j+1))
{
pr=1;
break;
}
}
if(pr == 0)
{
for(r=0; r < q.c; r++)
{
if(q.m[r] == (j+1))
{
pr=1;
break;
}
}
if(pr == 0)
{
tp.m[tp.c]=(j+1);
tp.c++;
}
}
}
}
}
}
/*---------------------------*
if(tp.c == 0)
{
(*sm).m=NULL;
(*sm).c=0;
if(tp.m == NULL)
{ printf("\nError: tp.m == NULL !");
getch(); return 1; }
free(tp.m);
return 0;
}
else
{
(*sm).c=tp.c;
(*sm).m=(int*)calloc((*sm).c, sizeof(int));
if((*sm).m == NULL)
{ printf("\nError: (*sm).m == NULL !");
getch(); return 1; }
}
for(i=0; i < (*sm).c; i++)
{
(*sm).m[i]=tp.m[i];
}
/*---------------------------*
free(tp.m);
/*---------------------------*
return 0;
}
/*****************************
/* Функция добавления элемента в */
/* конец массива */
/*****************************
int add_ver(ms *g, int xi)
{
int *oldm;
int i,k;
/*----------------------------
/*printf("\nadd_ver!");*/
/*----------------------------
if((*g).m != NULL)
{
oldm=(int*)calloc((*g).c, sizeof(int));
if(oldm == NULL)
{ printf("Error: oldm == NULL !");
getch(); return 1; }
for(i=0; i < (*g).c; i++)
{
oldm[i] = (*g).m[i];
}
/*-------------------------*/
if((*g).m == NULL)
{ printf("\nError: (*g).m == NULL !");
getch(); return 1; }
free((*g).m);
k=(*g).c+1;
}
else
{
k=1;
}
(*g).m=(int*)calloc(k, sizeof(int));
if(k > 1)
{
for(i=0; i < (k-1); i++)
{
(*g).m[i]=oldm[i];
}
}
(*g).m[k-1]=xi;
(*g).c=k;
/*----------------------------
return 0;
}
/*****************************
/* Функция вывода массива */
/*****************************
int ms_pr(ms mass)
{
int i;
/*----------------------------
if(mass.m == NULL)
{
printf("\nError: mass.m == NULL !");
getch();
return 1;
}
/*----------------------------
if(mass.c == 0)
{
printf("\nError: mass.c == 0 !");
getch();
return 1;
}
/*----------------------------
for(i=0; i < mass.c; i++)
{
printf("%d ", mass.m[i]);
}
/*----------------------------
return 0;
}
1) Вычисляем матрицу смежности A=||aij||nxn.
|
|
x2 |
x4 |
x5 |
x6 |
x7 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
x15 |
x16 |
ρ | ||||
x1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 | |
x2 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 | |
x3 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 | |
x4 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 | |
x5 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 | |
x6 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
5 | |
x7 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
4 | |
= |
x8 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
2 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
7 |
x9 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
5 | |
X10 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
5 | |
X11 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
7 | |
X12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
5 | |
X13 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
5 | |
X14 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
4 | |
X15 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
4 | |
X16 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
3 |
2) Выделяем первую запрещенную вершину.
G1 ={X7}
3) Для вершины xi ϵ Г(xv) определяем относительные веса
δ (xv) = ρ(xi)-
где ρ(xi) – локальная степень вершины xi , ρ(xi) = ; – число ребер, соединяющих вершину xi с вершинами xj , вошедшими в G1;
m – число вершин G1 на текущем шаге работы алгоритма. Переход к п.4.
Г (X7) = {X7, X3, X6, X11}
4) Выбираем вершину Xs , для которой ). Если таких вершин несколько, то выбираем вершину с большой локальной степенью ρ(xi). Переход к п.5.
δ (X2) = 2 b27 = 1
δ (X3) = 0 min b37 = 1
δ (X6) = 4 b67 = 1
δ (X11) = 6 b117 = 1
5) Полученную вершину Xs помещаем в кусок G1: G1={ xv xs }. Переход к п.6.
Xs = X3
6) Подсчитываем число n1 вершин в куске G1. Если n1 < n, где n - заданное число вершин в каждом куске, то переход к п.8.
G1 = {X7, X3}, т.к. nt < n
8) Добавляем в список вершины, смежные вершинам, вошедшим в кусок G1.
Г (X7, X3) = {X2, X6, X11}
Переход к пункту № 3
3) Для вершины xi ϵ Г(xv) определяем относительные веса
δ (xv) = ρ(xi)-
где ρ(xi) – локальная степень вершины xi , ρ(xi) = ; – число ребер, соединяющих вершину xi с вершинами xj , вошедшими в G1;
m – число вершин G1 на текущем шаге работы алгоритма. Переход к п.4
Г (X7, X3) = {X2, X6, X11}
4) Выбираем вершину Xs, для которой ). Если таких вершин несколько, то выбираем вершину с большой локальной степенью ρ(xi). Переход к п.5.
δ (X2) = 2 min b273 = 1
δ (X6) = 4 b673 = 1
δ (X11) = 6 b1173 = 1
5) Полученную вершину Xs помещаем в кусок G1: G1={ xv xs }. Переход к п.6.
Xs = X2
6) Подсчитываем число n1 вершин в куске G1. Если n1 < n, где n - заданное число вершин в каждом куске, то переход к п.8.
G1 = {X7, X3, X2}, т.к. nt < n
8) Добавляем в список вершины, смежные вершинам, вошедшим в кусок G1.
Г (X7, X3, X2) = {X1, X6, X11}
Переход к пункту № 3
3) Для вершины xi ϵ Г(xv) определяем относительные веса
δ (xv) = ρ(xi)-
где ρ(xi) – локальная степень вершины xi , ρ(xi) = ; – число ребер, соединяющих вершину xi с вершинами xj , вошедшими в G1;
m – число вершин G1 на текущем шаге работы алгоритма. Переход к п.4
Г (X7, X3, X2) = {X1, X6, X11}
4) Выбираем вершину Xs , для которой ). Если таких вершин несколько, то выбираем вершину с большой локальной степенью ρ(xi). Переход к п.5.
δ (X1) = 1 min b1732 = 1
δ (X6) = 3 b6732 = 2
δ (X11) = 6 b11732 = 1
5) Полученную вершину Xs помещаем в кусок G1: G1={ xv xs }. Переход к п.6.
Xs = X1
6) Подсчитываем число n1 вершин в куске G1. Если n1 < n, где n - заданное число вершин в каждом куске, то переход к п.8.
G1 = {X7, X3, X2 X1}
7) Если n1 = n, кусок G1 сформирован, тогда переход к п.9.
n1 = n
9) Удаляем из матрицы
A строки и столбцы,
Удаляем из матрицы A {X7 X3, X2, X1}
x4 |
x5 |
X8 |
X9 |
X10 |
x12 |
x13 |
x15 |
ρ | |||||
x4 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
x5 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
x6 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
1 |
0 |
0 |
2 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
7 | |
X9 |
1 |
1 |
0 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
5 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
5 | |
x11 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
6 |
x12 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
5 |
x13 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
5 |
x14 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
4 | |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
3 |
=
2) Выделяем вторую запрещенную вершину.
G2 = (X14)
3) Для вершины xi ϵ Г(xv) определяем относительные веса
δ (xv) = ρ(xi)-
где ρ(xi) – локальная степень вершины xi , ρ(xi) = ; – число ребер, соединяющих вершину xi с вершинами xj , вошедшими в G2;
m – число вершин G2 на текущем шаге работы алгоритма. Переход к п.4.
Г (X14) = {X10, X11, X16}
4) Выбираем вершину Xs , для которой ). Если таких вершин несколько, то выбираем вершину с большой локальной степенью ρ(xi). Переход к п.5.
δ (X10) = 4 b1014 = 1
δ (X11) = 5 b1114 = 1
δ (X16) = 2 min b1614 = 1
5) Полученную вершину Xs помещаем в кусок G2: G2={ xv xs }. Переход к п.6.
Xs = X16
6) Подсчитываем число n2 вершин в куске G2. Если n2 < n, где n - заданное число вершин в каждом куске, то переход к п.8.
G2 = {X14, X16}, т.к. nt < n
8) Добавляем в список Г(xv) вершины, смежные вершинам, вошедшим в кусок G2. Переход к п.3.
Г (X14, X16) = { X10, X11, X13}
Переход к пункту № 3
3) Для вершины xi ϵ Г(xv) определяем относительные веса
δ (xv) = ρ(xi)-
где ρ(xi) – локальная степень вершины xi , ρ(xi) = ; – число ребер, соединяющих вершину xi с вершинами xj , вошедшими в G2;
m – число вершин G2 на текущем шаге работы алгоритма. Переход к п.4
Г (X14, X16) = { X10, X11, X13}
4) Выбираем вершину Xs , для которой ). Если таких вершин несколько, то выбираем вершину с большой локальной степенью ρ(xi). Переход к п.5.
δ (X10) = 4 min b101416 = 1
δ (X11) = 5 b111416 = 1
δ (X13) = 4 b131416 = 1
5) Полученную вершину Xs помещаем в кусок G2: G2={ xv xs }. Переход к п.6.
Xs = X16
6) Подсчитываем число n2 вершин в куске G2. Если n2 < n, где n - заданное число вершин в каждом куске, то переход к п.8.
G2 { X14, X16, X10}, т.к. nt < n
8) Добавляем в список Г(xv) вершины, смежные вершинам, вошедшим в кусок G2. Переход к п.3.
Г (X14, X16, X10) = { X6, X11, X12}
Переход к пункту № 3
3) Для вершины xi ϵ Г(xv) определяем относительные веса
δ (xv) = ρ(xi)-
где ρ(xi) – локальная степень вершины xi , ρ(xi) = ; – число ребер, соединяющих вершину xi с вершинами xj , вошедшими в G2;
m – число вершин G2 на текущем шаге работы алгоритма. Переход к п.4
Г (X14, X16, X10) = { X6, X11, X12}
4) Выбираем вершину Xs , для которой ). Если таких вершин несколько, то выбираем вершину с большой локальной степенью ρ(xi). Переход к п.5.
δ (X6) = 1 min b6141610 = 1
δ (X11) = 4 b11141610 = 1
δ (X12) = 4 b12141610 = 1
5) Полученную вершину Xs помещаем в кусок G2: G2={ xv xs }. Переход к п.6.
Xs = X6
6) Подсчитываем число n2 вершин в куске G2. Если n2 < n, где n - заданное число вершин в каждом куске, то переход к п.8.
G2 = { X14, X16, X10,X6}
7) Если n2 = n, кусок G1 сформирован, тогда переход к п.9.
n2 = n
Переход к пункту №9
9) Удаляем из матрицы
A строки и столбцы,
Удаляем из матрицы A { X14, X16, X10,X6}
x4 |
x5 |
x8 |
X9 |
X12 |
ρ | ||||
x4 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
3 |
x5 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
3 |
X8 |
1 |
1 |
2 |
1 |
1 |
1 |
0 |
0 |
7 |
X9 |
1 |
1 |
2 |
0 |
0 |
0 |
1 |
0 |
5 |
X11 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
3 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
4 | |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
4 | |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
Информация о работе Последовательный алгоритм компоновки с равными числу вершин в каждом куске