Разработка и описание графа
Представление входного файла выглядит следующим образом:
<Количество вершин>
<Матрица смежности с весами ребер >
Матрица состоит из n-го количества строк и в каждой строке находятся n-ое количество весов, разделенных «пробелом».
Пример входного файла:
0 2 3 9 3 1
2 0 7 2 4 2
3 7 0 3 5 3
9 1 3 0 8 4
3 4 5 8 0 5
6 7 8 9 1 0
Рассмотрим описание каждого массива в программе и занесем в табл. 4.
Таблица 4. Обозначения и описание массивов.
| № | Имя массива | Размерность массива | Описание массива |
| a | n*n, n-количество вершин | матрица смежности | |
| q | k, k-количество вершин в подграфе | массив с вершинами подграфа | |
| q1 | k, k-количество вершин в подграфе | массив с вершинами подграфа, необходимый для подбора вершин | |
| p1 | k+1, k-количество вершин в подграфе | массив для подсчета вероятности | |
| p2 | k, k-количество вершин в подграфе | массив для подсчета вероятности | |
| b | n*n, n-количество вершин | матрица с феромонами | |
| x | n, n-количество вершин | массив с вершинами, для выбора не пройденных вершин |
В табл. 5 рассмотрены описания всех переменных в программе.
Таблица 5. Обозначения и описание переменных.
| № | Имя переменной | Тип переменной | Минимальное и максимальное значения переменной | Описание переменной |
| Q | int | 0…65535 | константа равная 5 | |
| i1 | int | 0…65535 | рабочий индекс | |
| i2 | int | 0…65535 | рабочий индекс | |
| f1 | int | 0…65535 | заменяет переменную k при подсчете не пройденных вершин и вероятности | |
| p | int | 0…65535 | рабочий индекс | |
| l | int | 0…65535 | начальная вершина при разбиении | |
| m | int | 0…65535 | количество выбранных вершин | |
| n | int | 0…65535 | количество вершин | |
| k | int | 0…65535 | количество вершин в подграфе | |
| f | int | 0…65535 | рабочий индекс | |
| c | int | 0…65535 | конечная вершина при разбиении | |
| t | int | 0…65535 | количество не пройденных вершин | |
| y | int | 0…65535 | рабочий индекс | |
| i | int | 0…65535 | рабочий индекс | |
| j | int | 0…65535 | рабочий индекс | |
| v | double | степень феромона | ||
| sum | float | 1.17549e-38… 3.40282e+38 | сумма между выбранными и оставшимися вершинами | |
| min | float | 1.17549e-38… 3.40282e+38 | минимальная сумма между выбранными и оставшимися вершинами | |
| sum1 | double | 2.22507e-308… 1.79769e+308 | сумма для подсчета вероятности | |
| g1 | double | 2.22507e-308… 1.79769e+308 | случайное числа для подсчета вероятности | |
| g | double | 2.22507e-308… 1.79769e+308 | случайное числа для подсчета вероятности между 0 и 1 | |
| sum2 | double | 2.22507e-308… 1.79769e+308 | сумма для подсчета вероятности | |
| min1 | float | 1.17549e-38… 3.40282e+38 | минимальная сумма между выбранными и оставшимися вершинами |
Программная реализация алгоритма
Решения задачи и ее описание
В программной реализации алгоритма на Microsoft Visual Studio 2010 требуется включить следующие библиотеки:
#include "stdafx.h" – заголовок со стандартным именем
#include <stdio.h> - стандартный заголовочный файл ввода/вывода
#include <conio.h> - заголовочный файл, используемый в старых компиляторах, работающих в операционных системах MS-DOS, для создания текстового интерфейса пользователя
#include <locale> - заголовочный файл для включения кириллицы в программе
#include <iostream> - заголовочный файл с классами, функциями и переменными для организации ввода-вывода
using namespace std - использовать пространство имен std
#include "fun1.h" – файл содержащий функцию, которая используется для считывания данных с файла
#include "fun2.h"" – файл содержащий функцию, которая используется для разбиения графа на подграфы
#include "fun3.h"" – файл содержащий функцию, которая используется для записи данных в файл
В реализации программы также потребуются перечисленные ниже функции и методы:
fscanf – функция считывания с файла
fprintf – функцию записи в файл
random - функция генерирующая случайные числа
Разработка системы тестов и отладка программы
Тесты черного ящика
Для проектирования тестов программы методами черного ящика с помощью эквивалентного разбиения входных/выходных данных на области (классы) эквивалентности составлен список ситуаций, каждая из которых должна создаваться хотя бы одним тестом. Тестовые ситуации приведены в табл. 6, в скобках указаны их номера.
Таблица 6. Области входных/выходных данных тестов программы.
| Входные и выходные параметры | Допустимые значения | Недопустимые значения |
| Количество вершин, n | 2..NMAX (1) | <2 (2), >NMAX (3) |
| Количество ребер | 1…n*(n-1) (4) | < 1 (5), > n*(n-1) (6) |
| Наличие петель | Нет (7) | Есть (8) |
| Вес ребра | >=0 (9) | <0(10) |
| Входной файл существует | Да(11) | Нет(12) |
| Выходной файл существует | Да(13) | Нет(14) |
Для создания перечисленных тестовых ситуаций разработаны тесты, представленные в табл. 7. Входные и выходные данные тестов по возможности выбирались ближе к границам классов эквивалентности.
Таблица 7. Тесты черного ящика для отладки программы.
| № теста | Входные данные | Выходные данные | № ситуаций |
| 0 2 3 9 5 2 0 7 1 6 3 7 0 3 7 9 1 3 0 9 5 6 7 9 0 | G1 (4,1) G2 (0,2,3) | 1, 4, 7, 9, 11, 13 | |
| Сообщение «Количество вершин меньше или равно 0» | 2, 1, 7, 9, 11, 13 | ||
| 0 2 3 9 5 2 0 7 1 6 3 7 0 3 7 9 1 3 0 9 5 6 7 9 5 | Сообщение «Присутствуют петли» | 1, 4, 8, 10, 11, 13 | |
| Сообщение «Ошибка открытия файла для чтения» | 12, 13 | ||
| 0 2 3 9 5 2 0 7 1 6 3 7 0 3 7 9 1 3 0 9 5 6 7 9 0 | Сообщение «Ошибка открытия файла для записи» | 1, 4, 7, 9, 11, 14 | |
| 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | Сообщение «Матрица смежности состоит из нулей» | 1, 5, 7, 9, 11, 13 | |
| 0 1 2 3 4 5 1 0 6 7 8 9 2 6 0 8 7 6 3 7 8 0 5 4 4 8 7 5 0 3 5 9 6 4 3 0 | G1 (2,3,4) G2 (0,1,5) | 1, 4, 7, 9, 11, 13 | |
| 1 1 2 3 4 5 1 0 6 7 8 9 2 6 0 8 7 6 3 7 8 0 5 4 4 8 7 5 0 3 5 9 6 4 3 0 | Сообщение «Присутствуют петли» | 1, 4, 8, 9, 11, 13 | |
| 0 1 -2 3 4 5 1 0 6 7 8 9 -2 6 0 8 7 6 3 7 8 0 5 4 4 8 7 5 0 -3 5 9 6 4 -3 0 | Сообщение «Вес ребра меньше 0» | 1, 4, 7, 10, 11, 13 | |
| 0 2 3 9 5 7 3 4 2 0 7 2 6 8 0 7 3 7 0 3 7 3 8 0 9 2 3 0 9 5 9 4 5 6 7 9 0 6 7 8 7 8 3 5 6 0 3 1 3 0 8 9 7 3 0 4 4 7 0 4 8 1 4 0 | G1 (3,6,2,4) G2 (0,1,5,7) | 1, 4, 7, 9, 11, 13 | |
| 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | Сообщение «Матрица смежности состоит из нулей» | 1, 5, 7, 9, 11, 13 |
Тесты белого ящика
Разработанные тесты проверены методом белого ящика по критериям охвата основных путей выполнения алгоритма подпрограмм. В программе имеются составные условия. Поэтому использован критерий комбинаторного покрытия условий (см. табл. 8).
Таблица 8. Комбинаторное покрытие условий тестами черного ящика.
| Модуль | Элементарные условия | Истина | Ложь |
| main | n>0 | 1,5,7,10 | 2,3,4,6,8,9 |
| fun1 | inp == NULL | Остальные | |
| fun1 | n<=0 | Остальные | |
| fun1 | a[i][j]<0 | 3,9 | Остальные |
| fun1 | i==j | Остальные | |
| fun1 | a[i][j]!=0 | Остальные | |
| fun2 | m<k | Остальные | 6,11 |
| fun2 | m>1 | Остальные | 6,11 |
| fun2 | a[i][j]>0 | Остальные | 6,11 |
| fun2 | j!=x[i1] | Остальные | 6,11 |
| fun2 | f==m | Остальные | 6,11 |
| fun2 | i1<f1 | Остальные | 6,11 |
| fun2 | i1<=f1 | Остальные | 6,11 |
| fun2 | g1>=p1[i2] | Остальные | 6,11 |
| fun2 | g1<=p1[i1] | Остальные | 6,11 |
| fun2 | y!=x[i] | Остальные | 6,11 |
| fun2 | f==k | Остальные | 6,11 |
| fun2 | min>sum | Остальные | 6,11 |
| fun2 | i=0;i<n;i++ | Остальные | 6,11 |
| fun2 | j=0;j<n;j++ | Остальные | 6,11 |
| fun2 | i1=0;i1<m;i1++ | Остальные | 6,11 |
| fun2 | i1=0;i1<f1;i1++ | Остальные | 6,11 |
| fun2 | int e=0;e<k;e++ | Остальные | 6,11 |
| fun2 | y=0;y<n;y++ | Остальные | 6,11 |
| fun2 | i=0;i<k;i++ | Остальные | 6,11 |
| fun2 | y=0;y<k;y++ | Остальные | 6,11 |
| fun3 | q[0]==q[1] | 6,11 | Остальные |
| fun3 | fp == NULL | Остальные | |
| fun3 | y=0;y<k;y++ | 6,11,5 | Остальные |
| fun3 | y=0;y<n;y++ | 6,11,5 | Остальные |
| fun3 | i=0;i<k;i++ | 6,11,5 | Остальные |
Из табл. 8 видно, что тесты черного ящика обеспечивают полное комбинаторное покрытие все х ситуаций, поэтому нет необходимости в тестах белого ящика.
ЗАКЛЮЧЕНИЕ
Проблема разбиения графов является актуальной при решении многих научных задач. В наше время существует много разновидностей алгоритмов. В данной работе рассмотрен так называемый муравьиный алгоритм разбиения графов.
Ниже следуют пункты, рассмотренные в курсовой работе.
1) Оформлялась содержательная часть задачи разбиения графов.
2) Разрабатывался алгоритм решения задачи.
3) Разрабатывались структуры программы и алгоритмы программных модулей.
4) Решили задачу на контрольном примере.
5) Разрабатывался и описывался граф.
6) Исходя из разработанного алгоритма, реализовывалась программа.
7) Разрабатывались системы тестов в виде черных и белых ящиков.
Алгоритм разбиения был реализован на языке высокого уровня С++. Отлаживалась программа в среде разработки MS Visual studio 2010.
Курсовая работа выполнена в соответствии с требованиями в полном объеме.
СПИСОК ЛИТЕРАТУРЫ
1. Хохлов Д.Г. Основы технологии модульного программирования. Учебное пособие – Казань: КГТУ (КАИ), 2003.
2. Ладыженский Ю.П., Родригес Р.А. Муравьиный алгоритм для разбиения графов. Учебное пособие – Донецк: ДНТУ, 2007.
3. Лебедев О.Б. Гибридный алгоритм разбиения на основе метода муравьиной колонии и коллективной адаптации.М.: Физматлит, 2010.
4. Методы и алгоритмы компоновки, размещения и трассировки печатных плат
5. Родригес Р.А. Методы решения задач разбиения графов с использованием компьютерной кластерной сети. Учебное пособие – Донецк: ДНТУ, 2003.
6. Деньдобренько Б.Н. Автоматизация конструирования РЭА. Москва: Высшая школа, 1980.
7. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. Москва: Радио
и связь, 1990.
8. Хортон А. Visual C++: полный курс. М.:ООО «Дифлектика», 2011.
9. Введение в теорию графов [Электронный ресурс] / Под ред. В.С. Князьков, Т.В. Волченская — Электрон. дан. — М.: Интернет университет информационных технологий, 2005. — Режим доступа: ссылка свободная. — Загл. с экрана.
10. Струструп Б. Дизайн и эволюция С++. М.:ДМК Пресс, 2006.
ПРИЛОЖЕНИЯ. Листинг программы
//…………Основной модуль main
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <locale>
#include <iostream>
#include "fun1.h"
#include "fun2.h"
#include "fun3.h"
using namespace std;
int main ()
{setlocale (LC_ALL, "rus");
int n;
int a[100][100];
int *q;
n=fun1(a);
if (n>0)
{q=fun2(n,a);
fun3(n,q);
}
getch();
return 0;
//……………….Модуль fun1.h
#include <iostream>
using namespace std;
int fun1 (int a[100][100]) //функция считывания мартицы с файла
{int i,j,n;
FILE *inp=fopen("C:\\2.txt","r");
if (inp == NULL)
{cout << "Ошибка открытия файла для чтения"; return -1; }
else
{fscanf(inp,"%d",&n);
if(n<=0) {cout<<"Количество вершин меньше или равно 0"; return -1; }
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{fscanf(inp,"%d",&a[i][j]);
{if (a[i][j]<0)
{cout<<"Вес ребра меньше 0"; return -1;}
if(i==j)
if(a[i][j]!=0)
{cout<<"Присутствуют петли"; return -1;}}
}}
fclose(inp);
return n;
}
//………………Модуль fun2.h
#include <iostream>
using namespace std;
int *fun2 (int n,int a[100][100]) //функция обработки графа
{int Q=5,i1,i2,f1,p;
double v,sum1,g1,g,sum2;
int q1[100],q2[100];
double p1[100],p2[100];
int l,m;
double b[100][100];
int x[100];
float min1=65000,min=65000;
float sum;
int f,c,t;
int *q,k=n/2,y;
int i,j,l1,h1;
q=new int[k];
for (i=0;i<n;i++) //матрица с феромонами
for (j=0;j<n;j++)
{if (i==j) b[i][j]=0;
else b[i][j]=1;}
l=0;
while (l<n)
{l1=0; h1=l;
while (l1<n)
{m=1; i=h1; c=i; t=0; x[t]=h1;
while (m<k)
{y=0; f1=-1;
for (j=0;j<n;j++)
{if (m>1&&(a[i][j]>0)) // выбираем не пройденные вершины
{f=0;
for (i1=0;i1<m;i1++)
{if (j!=x[i1]) f++;}
if (f==m)
{f1++; q1[f1]=j;}
}
else
{if (a[i][j]>0) {f1++; q1[f1]=j;}
}
}
sum1=0; //находим сумму для нахождения вероятности
for (i1=0;i1<f1;i1++)
{sum1=a[i][q1[i1]]*b[i][q1[i1]]+sum1;}
for (i1=0;i1<f1;i1++) //находим вероятность и делим 1 на эту вероятность
{sum2=a[i][q1[i1]]/sum1; p2[i1]=b[i][q1[i1]]*1/sum2;}
sum1=0;
for (i1=0;i1<f1;i1++)
{sum1=p2[i1]+sum1; }
sum1=1/sum1; //находим среднюю вероятность
p1[0]=0; i2=0; i1=0;
while (i1<f1) // распологаем вероятности между 0 и 1
{i1++; p1[i1]=p2[i2]*sum1+p1[i2]; i2++;}
g=rand () % 100;
g1=g/100; //случайное число между 0 и 1
f=0;i2=0;i1=0;
while (i1<=f1) //ищем в какую из областей вероятности она входит и выбираем эту вершину
{i1++;
if (g1>p1[i2]&&g1<=p1[i1])
{f++; i2++; c=q1[i1];}
else i2++;}
m++; t++; x[t]=c; i=c;
}
for(int e=0;e<k;e++)
t=0;
for (y=0;y<n;y++) //не пройденные вершины
{f=0;
for (i=0;i<k;i++)
{if (y!=x[i]) f++;}
if (f==k) {q1[t]=y; t++;}
}
sum=0;
for (y=0;y<k;y++) //суммируем связь между выбранными и не пройденными вершинами
for (p=0;p<t;p++)
{sum=a[x[y]][q1[p]]+sum;}
if (sum<min1) //выбор минимальной суммы и присвоение вершин
{min1=sum;
for (y=0;y<k;y++)
{q2[y]=x[y];}}
l1++; h1=c;
}
for(int e=0;e<k;e++)
t=0;
for (y=0;y<n;y++) //не пройденные вершины
{f=0;
for (i=0;i<k;i++)
{if (y!=x[i]) f++;}
if (f==k) {q1[t]=y; t++;}
}
sum=0;
for (y=0;y<k;y++) //суммируем связь между выбранными и не пройденными вершинами
for (p=0;p<t;p++)
{sum=a[x[y]][q1[p]]+sum;}
if (sum<min) //выбор минимальной суммы и присвоение вершин
{min=sum;
for (y=0;y<k;y++)
{q[y]=q2[y];}}
v=Q/sum; // степень феромона
i2=1;
for (i1=0;i1<k-1;i1++) //увеличиваем степень феромона
{b[x[i1]][x[i2]]=b[x[i1]][x[i2]]+v;
b[x[i2]][x[i1]]=b[x[i2]][x[i1]]+v; i2++;}
l++;
}
if (q[0]!=q[1]) cout<<"сумма смежных ребер между выбранными подграфами равна "<<min;
return q;
}
//……………….Модуль fun3.h
#include <iostream>
using namespace std;
int fun3 (int n, int *q) //функция вывода полученных после разбияния графов
{int i,j;
int k=n/2,y,f;
FILE *fp = fopen("C:\\3.txt","w");
if (fp == NULL)
{cout << "Ошибка открытия файла для записи";}
else
if (q[0]==q[1])
{cout<<"Матрица смежности состоит из нулей"; return-1; }
{fprintf(fp,"%s","G1 (");
for (y=0;y<k;y++)
{fprintf(fp,"%d",q[y]); fprintf(fp,"%s",",");}
fprintf(fp,"%s",")");
fprintf(fp,"\n");
fprintf(fp,"%s","G2 (");
for (y=0;y<n;y++)
{f=0;
for (i=0;i<k;i++)
{if (y!=q[i]) f++;}
if (f==k) {fprintf(fp,"%d",y); fprintf(fp,"%s",",");}}
fprintf(fp,"%s",")");
}
fclose(fp);
cout<<"Программа успешно выполнена";
return 0;}