Задача Прима-Краскала

Программное обеспечение  вычислительной техники и автоматизированных систем

 

 

 

КУРСОВАЯ РАБОТА

Задача Прима-Краскала

 

 

Выполнил  студент:

 

 

Научный руководитель:

 

 

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

 

1)Введение 3

2)Теория 4

3)Алгоритм Прима-Краскала  4

4)Практика 6

5)Задача 1 6

6)Задача 2 9

7)Заключение 16

8) Список литтературы 17

 

 

 

 

 

 

 

 

 

 

 

Введение

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 Алгоритм Прима-Краскала

 

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

Алгоритм строит кратчайший остов:

Вход: граф G(V, Е) , заданный матрицей длин рёбер С.

Выход: кратчайший остов Т.

 Т:=V

while в Т больше одного элемента do

взять любое поддерево из Т

найти к нему ближайшее

соединить эти деревья в Т

end while

В частности, исследования алгоритма  Прима-Краскала привели в конечном счете к теории жадных алгоритмов. Следующий жадный алгоритм, известный как алгоритм Прима-Краскала, находит кратчайший остов в связном графе.

Алгоритм Прима-Краскала:

Вход: список Е рёбер графа G с длинами.

Выход: множество Т рёбер кратчайшего остова.

Т:=

Упорядочить Е в порядке возрастания длин

k:= 1 { номер рассматриваемого ребра }

for I from 1 to p – 1 do

while добавление ребра Е (k) образует цикл в Т do

k:=k+1 {пропустить ребро }

end while

Т:= Т Ụ { Е [k] } {добавить это ребро в SST }

end for

Пояснение SST-Shortest Sceleton Tree- стандартное обозначение для кратчайшего остова.

Заметим, что множество подмножеств  множества рёбер, не содержащих циклов, образует матроид. Действительно, если множество рёбер не содержит цикла, то любое подмножество также не содержит цикла. Пусть теперь Е^´ Е- произвольное множество рёбер, а G´- правильный подграф графа G, определяемый этими рёбрами. Очевидно, что любое максимальное не содержащее циклов подмножество множества Е´ является объединением остовов компонент связности G´и по теореме об основных свойствах деревьев содержит p(G´)- k(G´) элементов. Таким образом, по теореме множество ациклических подмножеств рёбер образует матроид. Далее, рассматриваемый алгоритм, как жадный алгоритм, находит кратчайшее ациклическое подмножество множества рёбер.

Граф — это схематическое  изображение объектов, связанных между собой отношениями. Такие объекты на графах называют вершинами, а отношения, которые их связывают, — ребрами. Граф в Turbo Pascal можно задать двумерным массивом d , где каждый элемент d (i, j) — отношение, которое связывает i -ю и j -ю вершины. Для решения поставленной задачи нужно пронумеровать города от 1 до N и занести в двумерный массив расстояния между городами (длины дорог). Для поиска наименьшей длины линий нужно использовать жадный алгоритм: каждый раз выбирать в цикле наименьшую длину дороги при условии, что эту дорогу еще не выбирали.

В файле data.in записано число N (количество городов в Хохляндии) и N строкрок по N чисел (расстояния между городами). Вывести в файл data.out

наименьшую длину линий  и последовательность пар городов, которые необходимо соединить оптоволоконными линиями. (N < 50)

Теория

Задача 1:

Задача (поставлена в общем  виде в 1961 году независимо друг от друга  Примом и Краскалом).

В стране Хохляндии нужно  соединить N городов оптоволоконными линиями для расширения Интернета. Все расстояния между городами известны. Найти наименьшую возможную длину линий.

 

 

 

 

 

 

 

Решение на Turbo Pascal:

Program prime_crascal;

var

d: array[1..50,1..50] of real;

f: text;

x, y: array[1..50] of real;

col: array[1..50] of integer;

res: array[1..50,1..2] of integer;

dmin, l: real;

n, k, m, i, j, i1,j1:integer;

begin

assign(f, ‘data.in’);

reset(f);

readln(fn);

for i:=l to n do

for j:=l to n do

read(f, d[i,j]);

close(f);

for i:=l to n do

col[i]:=i;

k:=0;

l:=0;

while k<n-l do

begin

dmin:=maxint;

for i1:=l to n-1 do

for j1:=i1+1 to n do

if (d[i1, j1]<dmin) and (col[i1]

ocol[j1]) then

begin

dmin:=d[i1,jl];

i:=i1;

end;

k:=k+1;

l:=l+dmin;

res[k,1]:=i;

res[k.2]:=j;

j1:=col[j];

for m:=l to n do

if col[m]=j1 then col[m]:=col[i];

end;

assign(f, ‘data.out’);

rewrite(f);

writeln(f,l:4:2);

for i:=l to n-1 do

writeln(f,res[i,1],res[i,2]:5);

close(f)

end.

 

 

 

 

Результат:

 

 

 

 

 

 

 

 

 

 

 

Задача 2:

Дана плоская страна в  ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длинна телефонной линии была минимальной (рис.6).

 

Рисунок 6 − Карта плоской  страны

 

2.2 Ручной расчет задачи

 

Пусть

С_ij - это стоимость телефонной линии от i до j города.

Q_j – минимальная стоимость телефонной линии от 1 города до i, при поиске кротчайшего пути из 1 до 8 города.

Используем формулу Q_j = min(Q_j+ С_ij) для поиска стоимости прокладки телефонного кабеля.

Стоимость телефонной линии  от 1 города равна Q₁=0,

Q₂ = Q₁+ С₁₂ = 0+6 = 6

Q₇ = Q₂+ С₂₇ = 6+3 = 9

Q₈ = Q₇+ С₇₈ = 9+16 =25 нашли кратчайший путь, найдем кратчайший путь до оставшихся городов Q₃= Q₂+ С₂₃ = 6+9 =15, Q₄ = Q₃+ С₃₄ = 15+12= 27, Q₆ = Q₂+ С₂₆ = 6+5 =11, Q₅ = Q₁+ С₁₅ = 0+2=2.

Минимальная прокладка телефонная линия с 1 до 8 города составит 6+3+16=25 по пути (1-2-7-8). Полная стоимость всей телефонной линии 6+3+16+2+5+9+12=53.

 

Получили схему прокладки  телефонной линии (рис. 7).

 

Рисунок 7 – Схема прокладки  телефонной линии

 

Вывод: получили минимальную  стоимость прокладки телефонной линии с 1 до 8 город и составляет 6+3+16=25.

 

2.3 Машинная реализация  метода

 

Входные данные:

nU − число ребер в графе

X – список вершин графа

We – веса ребер согласно их сортировки

Выходные данные:

nU − число ребер в графе

nX − число вершин в графе

Х − список вершин графа

(u1,u2) − сортированный список ребер графа

We − веса ребер согласно их сортировки

(uo1,uo2) − ребра оставного дерева

Woe − веса ребер оставного дерева

Вес − сумма весов ребер  оставного дерева.

 

Решение:

Program Hungry_Ostov; {Оставное дерево.Жадный алгоритм.}

uses CRT,DOS;

Const

nVertex=50;{Максимальное количество вершин}

nRib=1000;{Максимальное количество ребер}

Type

TypeVertex=array[1..nVertex] of Integer;

TypeRib=array[1..nRib] of Integer;

Var f:Text;{Текстовый файл}

nX:Integer;{Количество вершин в графе}

nU:Integer;{Количество ребер в графе}

Mark:TypeVertex; {Метки принадлежности вершин}

x:TypeVertex;{Список вершин  графа}

U:TypeRib;{Реберный список  графа }

nUo:Integer;{Количество ребер в оставном дереве}

Uo:TypeRib;{Ребра оставного дерева}

We:TypeRib;{Веса ребер графа}

Wt:LongInt;{Вес минимального оставного дерева}

Procedure Init;{Переназначение меток вершин}

Var

i,j,m:Integer;

begin

for i:=1 to 2*nU do Uo[i]:=1;

for i:=1 to 2*nU do

for j:=i+1 to 2*nU do if Uo[j]=1 then

if U[j]=U[i] then Uo[j]:=0;

nX:=0;

for i:=1 to 2*nU do

if Uo[i]=1 then begin

nX:=nX+1;

X[nX]:=U[i];

end;

for i:=1 to 2*nU do {Новые метки}

for m:=1 to nX do

if U[i]=X[m] then begin U[i]:=m; break; end;

end;

Procedure Sort; {Сортировка списка ребер по их весам}

Var

i,j,k:Integer;

w:Integer;

begin

for i:=1 to nU do

for j:=1 to nU-i do

if We[j]>We[j+1] then begin

w:=We[j]; We[j]:=We[j+1]; We[j+1]:=w;

w:=U[2*j-1]; U[2*j-1]:=U[2*(j+1)-1];

U[2*(j+1)-1]:=w;

w:=U[2*j]; U[2*j]:=U[2*(j+1)]; U[2*(j+1)]:=w;

end;

end;

Procedure Ostov;{Строим минимальное оставное дерево}

Var

i,x,y,z:Integer;

sU:Integer;

begin

for i:=1 to nX do Mark[i]:=i;

Sort;{Сортировка ребер по весу}

nUo:=0;{Пустое множество Uo}

sU:=1;{Начальное ребро в сортированном U}

while nUo<nX-1 do begin

x:=U[2*sU];{Выбор нового ребра  из списка}

y:=U[2*sU-1];

if Mark[x]<>Mark[y] then begin

nUo:=nUo+1;

Uo[nUo]:=sU;{Добавить ребро в оставное дерево}

z:=Mark[y];{Слияние Ux и Uy}

for i:=1 to nX do if Mark[i]=z then

Mark[i]:=Mark[x];

end;

sU:=sU+1{Удалить ребра (x,y) из списка U }

end;

end;

Var{Main}

i,j:Integer;

Begin{Main}

Assign(f,'C:\hvvod.txt');

Reset(f);{Файл открыт для чтения}

Read(f,nU);{Количество ребер в реберном списке графа }

for i:=1 to nU do Read(f,U[2*i-1]);{Первые вершины ребер}

for i:=1 to nU do Read(f,U[2*i]);{Вторые вершины ребер}

for i:=1 to nU do Read(f,We[i]);{Вес ребер}

Close(f);

Assign(f,'C:\hvivod.txt');

Rewrite(f); {Файл открыт для чтения}

Init;

Sort;

WriteLn(f,'nU=',nU:3);

WriteLn(f,'nX=',nX:3);

Write(f,'X='); for i:=1 to nX do Write(f,X[i]:3);

WriteLn(f); Write(f,'u1=');

for i:=1 to nU do Write(f,X[U[2*i-1]]:3);

WriteLn(f); Write(f,'u2=');

for i:=1 to nU do Write(f,X[U[2*i]]:3);

WriteLn(f); Write (f,'We=');

for i:=1 to nU do Write(f,We[i]:3);WriteLn(f);

Ostov;

Write(f,'uo1=');

for i:=1 to nUo do Write(f,X[U[2*Uo[i]-1]]:3);

WriteLn(f);Write(f,'uo2=');

Write(f,'uo1=');

for i:=1 to nUo do Write(f,X[U[2*Uo[i]-1]]:3);

WriteLn(f);Write(f,'uo2=');

for i:=1 to nUo do Write(f,X[U[2*Uo[i]]]:3);

WriteLn(f); Write(f,'Woe=');

for i:=1 to nUo do Write(f,We[Uo[i]]:3);WriteLn(f);

Wt:=0;

for i:=1 to nUo do Wt:=Wt+We[Uo[i]];

Write(f,'Bec=',Wt:3);

Close(f);

end.{Main}

 

Результат:

 

 

 

 

 

 

Заключение

При выполнении курсовой работы по дисциплине «Математические методы», требуется применение знаний полученные при изучении таких дисциплин, как, «Математические методы», «Дискретная  математика», «Основы алгоритмизации и программирования».

В данной курсовой работе были рассмотрены понятия:

• алгоритм решения графов
• решение задачи ручным способом
• написание программы для решения задачи
• составление инструкций по использованию программы.

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литтературы

1. Вентцель Е.С. Исследование операций: задачи, принципы, методология. / Е.С. Вентцель. - М.: Высшая школа, 2001. – 487с.
2. Гончаров Г..А., Мочалин А.А. Элементы дискретной математики. /Г..А. Гончаров - М.: Форум – Инфра-М., 2004. – 128с.
3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы./ Б.Н. Иванов - М.: Лаборатория Базовых Знаний, 2002. – 128с.
4. Кремер Н.Ш. Исследование операций в экономике./Н.Ш.Кремер - М.: ЮНИТИ, 2004. – 407с.
5. Кузнецов А.В. и др. Руководство к решению задач по математическому программированию./ А.В. Кузнецов. - Минск: Высшая школа, 2001. – 448 с.
6. http://www.e-osnova.ru/PDF/osnova_2_0_54.pdf