Задача Прима-Краскала о телефонной линии

Минимальная прокладка телефонная линия с 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с.