В таблице 3 приведён протокол тестирования правильности работы программы по алгоритму Крускала. В входных данных вводится матрица смежности, в выходных данных ожидается получить минимальное остовное дерево.

Таблица 3 протокол тестирования правильности

№ п/п	Входные данные	Выходные данные		Тест
		Ожидаемый результат	Действительный результат
	Cost[4][4]	МОД	МОД
1	0 5 9 12 11 0 4 0 1 0 0 11 14 9 0 0	Ребро 1 –> 2 Ребро2–> 3 Ребро 3–> 4	Ребро 1 –> 2 Ребро2–> 3 Ребро 3–> 4	+
2	0 14 12 12 6 0 2 12 10 11 0 8 12 1 5 0	Ребро 1 –> 3 Ребро3–> 4 Ребро 4–> 2	Ребро 1 –> 3 Ребро3–> 4 Ребро 4–> 2	+

4.2 Анализ по времени

Анализ по времени проводится функцией clock() из стандартной библиотеки <time.h>. Длины ребер задаем с помощью функции rand() из той же библиотеки <time.h>, длины этих ребер будут варьироваться от 0 до 15. Ниже на рисунке 7 представлена диаграмма роста функции f(t)=N, где t – время работы программы, а N – количество вершин. Жирным выделен график роста функции алгоритма Прима, а тонким выделен график роста функции алгоритма Крускала.

Рисунок 6 – Диаграмма роста функции

---

Заключение

В ходе реализации алгоритма, были применены теоретические и практические знания полученные за период обучения.

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

---

Список используемых источников.

1. ГОСТ 7.32–2001. Отчёт о научно-исследовательской работе. Структура и правила оформления [Текст]. – Взамен ГОСТ 7.32–91 ;введ. 2001–07–01. – Минск :Межгос. совет по стандартизации, метрологии и сертификации ; М. : Изд-во стандартов, 2001. – 16 с. – (Система стандартов по информации, библиотечному и издательскому делу).

2. ГОСТ 7.1–2003. Библиографическая запись. Библиографическое описание. Общие требования и правила составления [Текст]. – Взамен ГОСТ 7.1–84, ГОСТ 7.16–79, ГОСТ 7.18–79, ГОСТ 7.34–81, ГОСТ 7.40–82 ;введ. 2004–07–01. – М. : Изд-во стандартов, 2004. – 116 с. – (Система стандартов по информации, библиотечному и издательскому делу).

3. Кормен Т. Х. / Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2007. — 1296 с.

4. Роберт Серджвик. Фундаментальные алгоритмы на С++. [Текст]: в 5 ч. / Роберт Серджвик. – СПб, ООО «ДиаСлфтЮП», 2002.

Ч. 5: Алгоритмы на графах: Перевод с англ. – 2002 – 486с. ISBN 5-93772-054-7.

5. Степанов, В.Н. Дискретная математика: графы и алгоритмы на графах: учеб.пособие / В.Н. Степанов. – Омск, Изд-во ОмГТУ, 2010 – 120с. ISBN 978-5-8149-0913-8

6. Форум программистов и сисадминов CyberForum.ru [Электронный ресурс]. –Форум начинающих и профессиональных программистов, системных администраторов, администраторов баз данных, компьютерный форум. – Режим доступа: . http://www.cyberforum.ru/ –Загл. с экрана.

7. Википедия – свободная энциклопедия [Электронный ресурс]. – Википедия – свободная энциклопедия, которую может редактировать каждый. Режим доступа: . http://ru.wikipedia.org –Загл. с экрана.

---

Приложение А.

(Обязательное)

Текст основной программы.

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<conio.h>

#include<time.h>

using namespace std;

int a,b,u,v,n,i,j,N=1;

int visited[101]={0},_min,_mincost=0,cost[101][101];

void main()

{

setlocale(LC_ALL, "Russian");

srand(time(NULL));

printf("\n Введите кол-во вершин :");

scanf("%d",&n);

printf("\n Элементы матрицы %i*%i:\n",n,n);

float t=clock()/100;

for(i=1;i<=n;i++)

{

for(j=1;j<=n;j++)

{

//scanf("%d",&cost[i][j]);

if (i==j) cost[i][j]=0; else cost[i][j]=0+rand()%15;

cout<<cost[i][j]<<"\t";

if(cost[i][j]==0)

cost[i][j]=999;

}

printf("\n");

}

visited[1]=1;

printf("\n");

while(N<n) // N - номер вершины

{

for(i=1,_min=999;i<=n;i++)

for(j=1;j<=n;j++)

if(cost[i][j]<_min)

if(visited[i]!=0)

{

_min=cost[i][j];

a=u=i;

b=v=j;

}

if(visited[u]==0 || visited[v]==0)

{

printf("\n Ребро %d:(%d %d) вес:%d",N++,a,b,_min);

_mincost+=_min;

visited[b]=1;

}

cost[a][b]=cost[b][a]=999;

}

float tt=clock()/100-t;

printf("\n Время выполнения алгоритма: %f",tt);

printf("\n Вес минимального остовного дерева=%d",_mincost);

getch();

}

---

Смотрите также файлы

• Методы оптимизации Курсовой проект О распределении.docx

• Методы оптимизации Зыкина.docx

• РЕФЕРАТ_ФИЗКУЛЬТУРА.docx

• физра реферат.doc

• конкуренты.docx