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

Вход: граф 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ґ) элементов. Таким образом, по теореме множество ациклических подмножеств рёбер образует матроид. Далее, рассматриваемый алгоритм, как жадный алгоритм, находит кратчайшее ациклическое подмножество множества рёбер. По построению оно содержит p-1 элемент, а значит, является искомым остовом.

2 ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Решение задачи-теста

2.1.1 Постановка задачи

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

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

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

Пусть

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

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

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

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

Q2 = Q1+ С12 = 0+6 = 6

Q7 = Q2+ С27 = 6+3 = 9

Q8 = Q7+ С78 = 9+16 =25 нашли кратчайший путь, найдем кратчайший путь до оставшихся городов Q3= Q2+ С23 = 6+9 =15, Q4 = Q3+ С34 = 15+12= 27, Q6 = Q2+ С26 = 6+5 =11, Q5 = Q1+ С15 = 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 ? веса ребер оставного дерева

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

2.4 Блок-схема

Рисунок 7 - Блок-схема алгоритма решения задачи

2.5 Обоснование выбора языка программирования

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

Паскаль ? замечательный язык программирования, который относительно прост в изучении, довольно ясен и логичен и, будучи первым изучаемым языком программирования, приучает к хорошему стилю. Паскаль воспитывает дисциплину структурного рограммирования и программирования вообще лучше, чем другие языки программирования.

2.6 Листинг программы

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}

2.7 Анализ полученных результатов

После запуска программы на экране пользователя получили результаты программных расчетов (рис.8).

ЗАКЛЮЧЕНИЕ

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

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

· алгоритм решения графов

· решение задачи ручным способом

· написание программы для решения задачи

· составление инструкций по использованию программы.

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

СПИСОК ЛИТЕРАТУРЫ

1. Вентцель Е.С. Исследование операций: задачи, принципы, методоло-гия. / Е.С. Вентцель. - М.: Высшая школа, 2001. - 487с.

2. Гончаров Г..А., Мочалин А.А. Элементы дискретной математики. /Г..А. Гончаров - М.: Форум - Инфра-М., 2004. - 128с.

3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы./ Б.Н. Иванов - М.: Лаборатория Базовых Знаний, 2002. - 128с.

4. Кремер Н.Ш. Исследование операций в экономике./Н.Ш.Кремер - М.: ЮНИТИ, 2004. - 407с.

5. Кузнецов А.В. и др. Руководство к решению задач по математическому программированию./ А.В. Кузнецов. - Минск: Высшая школа, 2001. - 448 с.

6. Математическое программирование. Сборник задач и упражнений по высшей математике. / Под ред. Кузнецова А.В., Рутковского Р.А. - Минск: Высшая школа, 2002. - 447с.

7. Морозов И.Н., Сухарев Л.Г., Федоров В.В. Исследование операций в задачах и упражнениях. /И.Н Морозов. - М.: Высшая школа, 1986.-504с.

8. Новиков Ф.А. Дискретная математика для программистов. / Ф.А. Новиков. - С.-Петербург: Питер, 2001. - 304с.

9. Партыка Т.Л. Математические методы./ Т.Л.Партыка, И.И. Попов. - М.: ФОРУМ-ИНФРА-М, 2005. - 464с.

10. Советов Б.Я., Яковлев С.А. Моделирование систем. / Б.Я. Советов. - М.: Высшая школа, 2001. - 343с.

11. Чернов В.П., Ивановский В.Б. Теория массового обслуживания./ В.П. Чернов. - М.: Инфра-М, 2000. - 205с.

Страницы: 1, 2