Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

Введение

Персональные компьютеры сейчас в основном используются в четырёх областях:

• обработка текстов и компьютерная вёрстка;

• хранение баз данных с возможностью их быстрой обработки;

• управление производственными процессами;

• анализ сложных процессов;

Программа данной курсовой работы задача Прима-Краскала или жадный алгоритм,

то есть алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

В качестве примера я выбрал задачу о прокладке телефонного кабеля между городами. Потому что я считаю что это наиболее яркий и понятный пример раскрывающую задачу Прима-Краскала эта задача должна в конечном итоги показать наикротчайший путь и связь между городами.
Раздел 1. Теоретические аспекты

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

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

Всякую прикладную постановку задачи нелишне уточнить. Мы негласно подразумеваем, что города сравнительно со страной малы; поэтому мы пренебрежем величиной городов и будем изображать город (точнее: телефонную станцию, размещенную в городе) точкой. Введя походящую систему декартовых координат, мы запишем положение i-го города, i=1, …, n, парой координат (Xi,Yi). Условие, что страна плоская, означает, что dij –расстояние от i-го города, до j-го, j=1, …, n.

В задаче речь идет о телефонной связи, т.е. подразумевается транзитивность связи: ели i-й город связан с j-м, а j-й с k-м, то i-й связан с k-м. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов. Если бы в минимальном решении был цикл, скажем, (i,j,k,l,i), то можно было бы убрать одно звено цикла, скажем, (j,k), причем связь между j и k сохранилась бы по другой стороне цикла, по пути (j,i,l,k). Но убирая одно звено, мы бы уменьшили минимальный цикл, что невозможно. Уточненную задачу можно теперь переформулировать в терминах теории графов.

Для этого придется ввести много терминов, которые пригодятся и дальше. Как говорил Берж, “во многих случаях жизни старая привычка толкает нас рисовать на бумаге точки, изображающие людей, населенные пункты, физические вещества и т.д.”. Описанная картинка называется графом, точки (или маленькие кружки) - вершинами, линии – ребрами, стрелки – дугами. Если допустимо соединить две вершины кратными (т.е. несколькими) ребрами, то граф называется петлей. Граф кратных ребер и петель называется простым. Поскольку дальше мы будем изучать преимущественно простые графы, то эпитет “простой” будет подразумеваться по умолчанию. Цепью между вершинами v и u (если вершины - это города, а ребра – дороги между соседними городами, то цепь – это дорога, соединяющая – может быть, не смежные – города v и u.). Если граф ориентированный (орграф), в котором вместо ребер имеются дуги, то аналог цепи называется путем: в пути из v и u все дуги должны быть ориентированы “по ходу”. Связный граф – это граф, где существует цепь между любой парой вершин v,u, иногда такой граф называют односвязным; если граф не связный и распадается на k,k>1,

компонент связанности, то граф называется k-связным. Граф часто обозначают символом G(V,E), G от английского Graph, V от Vertices – вершины, Е от Edges – ребра. В приложениях часто рассматривают взвешенные графы, где каждому ребру приписывается вес (или длина). Взвешенные графы так же называют сетями, их часто обозначают N(V,E,W), где N- -от английского Network – сеть, а W – от Weight – вес. Иногда надо рассматривать не весь граф, а его часть (часть вершин и часть ребер). Часть вершин и все инцидентные им ребра называются подграфом; все вершины и часть инцидентных им ребер называются суграфом. Циклом называется цепь из V и V. Деревом называется граф без циклов. Остовным деревом называется связный суграф графа, не имеющий циклов. Полным графом называется граф, в котором проведены все возможные ребра (в полном графе с n вершинами имеется n(n-1)/2 ребер).

В терминах теории графов задача Прима-Краскала выглядит следующим образом:

Дан полный граф с n вершинами, длины ребер определяются по формуле, где Xi,Yj- координаты вершин. Найти остовное дерево минимальной длины.

В таком виде задача была поставлена и решена Примом(1961). Краскал, одновременно и независимо, поставил и решил задачу не для плоского случая, где расстояния определяются по формуле, а для произвольных положительных dij, I,j=1,…, n. При этом для некоторых пар индексов dij=∞, что означает отсутствие ребра, т.е. рассматривается любой граф, а не только полный. Итак, вышеприведенный вариант есть, строго говоря, задача Прима, а задача Краскала звучит так:

Дан граф с n вершинами; длины ребер заданы матрицей {dij}, i,j=1,…, n. Найти остовное дерево минимальной длины.

Обе перечисленные задачи решаются одним алгоритмом, причем алгоритмом самой примитивной разновидности.

Представим себе, что зимовщику оставлен некоторый запас продуктов, и его задачей является составление вкусного меню на всю зиму. Если зимовщик начнет с того, что сперва будет есть самую вкусную еду (например, шоколад), потом - вторую по вкусности (например, мясо), то он рискует оставить на последний месяц только соль и маргарин. Подобным образом, если оптимальный (для определенности, минимальный) объект строится как-то по шагам, то нельзя на первом шаге выбирать что-то самое малое, на втором шаге – оставшееся самое малое и т.д. За такую политику обычно приходится жестоко расплачиваться на последних шагах. Алгоритм который мы выше выругали, называется жадным.

Удивительно, но в задаче Прима-Краскала, которая не кажется особенно простой, жадный алгоритм дает точное оптимальное решение.

Как известно (это легко доказать, скажем по индукции), дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро надо выбирать жадно (лишь бы не возникали циклы).

Алгоритм Прима-Краскала получает в точности минимальное решение. Это нужно доказать.

Для доказательства нам потребуется очень простое утверждение:

Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро.

Действительно, пусть добавлено ребро (u,v) – «добавлено» означает, что ребро – новое, что раньше его в дереве не было. Поскольку дерево является связным графом, то существует цепь C(u,…,v) из нескольких ребер, соединяющая вершины u и v. Добавление ребра (u,v) замыкает цепь, превращая ее в цикл.

Теорема. Алгоритм Прима-Краскала получает минимальное остовное дерево.

Доказательство. Результатом работы алгоритма является набор из n-1 ребер. Они не образуют цикла, ибо на каждом из n-1 шагов соединялись вершины разного цвета, т.е. ранее не связанные. Это граф связный, потому что после проведения 1-го ребра осталось n-1 разных цветов, …, проведения (n-1)-го ребра остался один цвет, т.е. одна компонента связности. Итак, полученный набор ребер образует связный граф без циклов, содержащий n-1 ребер, т.е.n вершин. Следовательно, граф есть остовное дерево. Осталось доказать, что оно имеет минимальную длину.

Пусть {l1, l2, …, ln-1} ребра остовного дерева в том порядке, как их выбирал алгоритм, т.е.li<=li-1. Предположим для простоты доказательства, что все ребра сети имеют разную длину, т.е.

l1<l2<…<ln-1 (1)

Если полученное дерево не минимально, то существует другое дерево, задаваемое набором из n-1 ребер {d1,d2,…,dn-1}, такое что сумма длин di меньше суммы длин li. С точностью до обозначений

d1<d2<…<dn-1 (2)

Может быть l1=d1, l2=d2 и т.д., но так как деревья разные, то в последовательностях (1) и (2) найдется место, где ребра отличаются. Пусть самое левое такое место – k, так что lк!=dк (k может равняться единице, это не испортит доказательства). Поскольку lк

выбиралось по алгоритму самым малым из необразующих цикла с ребрами l1, l2, …, lк-1, то lк<dк. Теперь добавим к дереву (2) ребро lк; в нем появится цикл, содержащий ребро lк и, может быть, какие-то (или все) ребра из l1, l2, …, lк-1, но они сами не образуют цикла, поэтому в цикле будет обязательно ребро d из набора dк, …, dn-1, причем d>lк. Выбросим из полученного графа с одним циклом ребро d; мы снова получим дерево, но оно будет на d-lк короче минимального, что невозможно. Полученное противоречие доказывает теорему для сети со всеми разными ребрами.

Если не предполагать, что все ребра разные, то в доказательстве могло бы получиться, что lк=dк, и нам пришлось бы двигаться дальше по последовательностям (1) и (2), пока бы мы не нашли lк+m<dк+m. Это усложняет доказательство, но не меняет заключения.

1.2 Выбор языка программирования

Для программирования я выбрал язык Delphi.

Сравнивая Delphi с другими программами такими как С++,VBA, нужно сказать что он более прост в освоении. Delphi это – система программирования, базирующаяся на языке программирования (Object Pascal), имеющая свой редактор, компилятор и отладчик.

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

У Delphi есть еще одно приятное отличие. Многие системы разработки приложений для Windows либо вовсе не генерируют исполняемый код, либо генерируют, который не может быть выполнен процессором без дополнительной трансляции во время работы самой программы, что существенно снижает производительность компьютера.

Использование стопроцентной компиляции дает еще одно преимущество, заключающееся в создании библиотек динамической компоновки (DDL), которые могут содержать любые компоненты из библиотеки компонентов. Затем эти библиотеки можно использовать в собственных приложениях Delphi или распространять как независимые компоненты для других программ.

Нельзя обойти стороной и то, как в Delphi представлены средства создания и

управления базами данных. Статистика утверждает, что большинство приложений так или иначе связаны с базами данных. И это неудивительно, ведь где еще компьютеру показать себя во всей красе, как не в области сбора, обработки и представления данных. Если данных много (или очень много), разработчики используют для их хранения именно базы данных. Delphi предоставляет в распоряжение пользователя объекты и компоненты, которые значительно уменьшают трудовые затраты на создание такого рода приложений. Убедительным примером этого служит тот факт, что с помощью Delphi можно создать программу ведения баз данных, не написав ни строки программного кода.

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

1.2.1 Выбор инструментальных программных средств

В практической части данной курсовой работы используются следующие визуальные и не визуальные компоненты среды программирования Borland Delphi 7.0.

1.2.1.1 Компонент TMainMenu

TMainMenu позволяет поместить главное меню в программу. При помещении TMainMenu на форму это выглядит, как просто иконка. Иконки данного типа называют невидимым (невизуальным) компонентом, поскольку они невидимы во время выполнения программы. Создание меню включает три шага:

1) помещение TMainMenu на форму,

2) вызов Дизайнера Меню через свойство Items в Инспекторе Объектов,

3) определение пунктов меню в Дизайнере Меню.

Этот компонент доступен из модуля MENUS, и находится на странице Палитры компонентов Standard

Этот компонент представляет главное меню формы и наследует все методы и свойства TMenu. Особенность его в том, что в нем реализован сложный механизм объединения меню. Это необходимо по следующим причинам:

Если в приложении имеется несколько форм со своими меню, то для упрощения работы целесообразно соединить их в одно и управлять меню из главной формы.
Объединение меню нужно при работе с интерфейсом MDI и его подокнами.
Механизм объединения меню используется серверами OLE, запускаемыми по месту нахождения объекта OLE. Загружаясь, сервер дописывает осуществляемые им операции к меню другого приложения.

Для того чтобы реализовать объединение меню, у тех форм, меню которых будут присоединены к главному, необходимо установить в True свойство: (Рb) property AutoMerge: Boolean.

При этом у главного меню оно должно оставаться равным False, иначе главное меню будет вообще невидимым. Объединение будет происходить автоматически при активизации новых форм или серверов OLE. Кроме автоматического режима, объединение меню можно выполнить при вызове метода: procedure Merge(Menu: TMainMenu).

При установленном в True свойстве AutoMerge ссылка на присоединенное меню будет сохраняться в специальном поле компонента, и отсоединяться в нужных случаях автоматически (например, при закрытии формы, которой оно принадлежит).

Объединение меню происходит по специальным правилам, в основе которых лежит использование группового индекса (свойства Group Index) каждого объекта TMenuItem.

У пунктов меню одного уровня, в частности всех подменю верхнего уровня в главном меню, свойство GroupIndex является неубывающим, т. е. у последующего пункта групповой индекс больше либо равен индексу предыдущего. Это требование отслеживается как на этапе разработки, так и на этапе исполнения. Например, пусть пункты меню имеют индексы 0, 3, 4, 5, 6. Если включить пункт меню с индексом 5 между пунктами с индексами 0 и 3, то 3 и 4 будут изменены на 5. А вот изменить большее значение Х на меньшее Y, если впереди есть пункты с индексом, большим Y, невозможно. Если в этом примере попытаться изменить индекс 6 на 4, то это приведет к возникновению исключительной ситуации EMenuError.

Для обычных форм объединение происходит только на верхнем уровне в главном меню во время их активизации. В объединенном меню все подменю будут располагаться по возрастанию номера группового индекса, при этом:

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

К окнам интерфейса MDI все сказанное относится только при запуске приложения. Если в формах приложения со стилем fsMDIChild есть свои главные меню, то в этот момент они автоматически сольются с главным меню формы fsMDIForm независимо от состояния AutoMerge.

На уровне работы с серверами OLE предусмотрены дополнительные возможности по объединению меню. Если в компонент TOLEContainer загружен объект OLE, то в конец подменю Edit обычно добавляется подменю, из которого можно вызвать функции открытия и редактирования этого объекта. После активизации сервера он может не только вставлять свои подменю в главное, но и добавлять новые пункты к уже существующим подменю.

1.2.1.2 Компонент TLabel

TLabel служит для отображения текста на экране. Можно изменить шрифт и цвет метки, если дважды щелкнуть на свойство Font в Инспекторе Объектов. Видно, что это легко сделать и во время выполнения программы, написав всего одну строчку кода.

Этот компонент доступен из модуля STDCTRLS, и находится на странице Палитры компонентов Standard.

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

Компонент TEdit

TEdit служит для ввода данных с клавиатуры. С помощью него можно ввести необходимые данные, с которыми в последствии можно будет работать.

Раздел 2. Программная реализация

2.1 Описание программы

Главная форма программы выглядит следующим образом:

На ней расположены 3 кнопки, поле куда надо ввести размер матрицы, и таблица куда будем вводить уже сами значения для вычисления.

Так же на форме присутствует пункт меню. Структура которого такова:

Файл

- Открыть

- Сохранить

- Выход

2. Пример

3. О программе

Для того чтобы начать работать необходимо ввести размер матрицы в соответствующее поле. После того, как мы это сделали, нажимаем кнопку «Заполнить». Должно получиться следующее:

Затем заполняем таблицу, и нажимаем «Вычислить». Внизу формы выводится наикратчайший путь и минимальные расходы.

По кнопке “Открыть” открывается стандартное диалоговое окно Windows открытия файла, где вы можете открыть ранее сохраненный проект.

Кнопкой “Сохранить” вы можете сохранить введенные вами данные, для последующего удобного открытия. Это позволяет ускорить процесс ввода данных в программу, особенно если вам приходится вводить большие объемы информации.

Ну и по последней кнопке в этой вкладке “Выход” приложение закрывается.

Если Вас интересует автор программы, или для чего предназначена программа, просто нажмите на кнопку “О программе”.

Чтобы очистить все введенные данные, просто нужно нажать кнопку «Очистить».

При нажатии кнопки “Пример” программа автоматически заполнит все нужные поля и выдаст результат.

2.2 Тестирование программы

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

A B C D

A 0 10 11 12

B 10 0 13 14

C 11 13 0 15

D 12 14 15 0

Из пункта А минимальное расстояние в данном примере до пункта B. Из пункта В минимальное расстояние до пункта С. И из пункта С соответственно до пункта D. Просуммировав данные результаты, мы получим: 10+13+15=38.

Кратчайший путь соответственно будет A-B-C-D.

Программа выдала следующие результаты:

Как видно по результатам теста, ответ найденный вручную и с помощью программы совпадает, а значит, доказывает правильность и корректность работы программы.

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

unit proga;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, Menus;

type

TForm1 = class(TForm)

StringGrid1: TStringGrid;

Edit1: TEdit;

Button1: TButton;

Button2: TButton;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Button3: TButton;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

SaveDialog1: TSaveDialog;

OpenDialog1: TOpenDialog;

N5: TMenuItem;

N6: TMenuItem;

Label5: TLabel;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure StringGrid1KeyPress(Sender: TObject; var Key: Char);

procedure N3Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure N5Click(Sender: TObject);

procedure N4Click(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure Edit1KeyPress(Sender: TObject; var Key: Char);

procedure N6Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

f: text;

i,j,N:integer;

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

implementation

uses Unit1;

{$R *.dfm}

// Кнопка «Заполнить»

procedure TForm1.Button1Click(Sender: TObject);

begin

StringGrid1.ColCount:=strtoint(edit1.Text)+1;

StringGrid1.RowCount:=strtoint(edit1.Text)+1;

N:=strtoint(edit1.Text)+1;

for i:=0 to n-2 do begin

stringgrid1.Cells[0,i+1]:=Chr(Byte('A')+i); буквы по алфавиту

stringgrid1.Cells[i+1,0]:=Chr(Byte('A')+i);

end;

for i:=1 to n-1 do

stringgrid1.Cells[i,i]:='0';

end;

// Кнопка «Вычислить»

procedure TForm1.Button2Click(Sender: TObject);

Var

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

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

k,m,i1,j1,q,z:integer;

min,L:real;

flag:boolean;

begin

label4.Caption:='A';

for i:=1 to N-1 do

for j:=1 to N-1 do

a[i,j]:=strtoint(stringgrid1.Cells[j,i]); запись чисел из таблицы в массив

k:=1;

L:=0;

q:=1;

while K<N-1 do begin

label4.Caption:=label4.Caption+'-';

i:=q;

z:=1;

j:=1;

flag:=false;

while flag=false do begin

if a[i,j]=0 then

j:=j+1

else begin

min:=a[i,j];

i1:=i;

j1:=j;

flag:=true; Нахождение минимального элемента

end; в каждой строке

end;

for j:=1 to N-1 do

if (a[i,j]<>0) and (a[i,j]<min) then begin

min:=a[i,j];

i1:=i;

j1:=j;

end;

L:=L+min;

label4.Caption:=label4.Caption+stringgrid1.Cells[0,j1];

for z:=1 to n do begin

a[i1,z]:=0;

a[z,i1]:=0;

end;

q:=j1;

K:=k+1;

end;

Label3.Caption:=floattostr(L); Вывод результатов

end;

procedure TForm1.StringGrid1KeyPress(Sender: TObject; var Key: Char);

begin

case key of

#15,'0'..'9': begin

j:=stringgrid1.col;

i:=stringgrid1.row; Ограничение ввода в StringGrid

stringgrid1.cells[i,j]:=stringgrid1.cells[i,j]+key;

end;

#13: if (stringgrid1.Col<stringgrid1.colcount-1) then

stringgrid1.Col:=stringgrid1.Col+1;

else

key:=chr(0);

end;

// Кнопка «Сохранить»

procedure TForm1.N3Click(Sender: TObject);

var i,l: integer;

begin

if savedialog1.Execute then begin

assignfile(f,savedialog1.FileName);

rewrite(f);

writeln(f,edit1.text);

for i:=0 to N-1 do

for j:=0 to N-1 do

writeln(f,stringgrid1.cells[j,i]); запись из таблицы в файл

closefile(f);

end;

// Кнопка «Очистить»

procedure TForm1.Button3Click(Sender: TObject);

begin

for i:=0 to 99 do

for j:=0 to 99 do

stringgrid1.Cells[j,i]:='';

label3.Caption:='';

label4.Caption:='';

edit1.Text:='';

stringgrid1.ColCount:=2;

stringgrid1.RowCount:=2;

stringgrid1.FixedCols:=1;

stringgrid1.FixedRows:=1;

end;

// Кнопка «Пример»

procedure TForm1.N5Click(Sender: TObject);

Var

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

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

k,m,i1,j1,q,z:integer;

min,L:real;

flag:boolean;

begin

N:=5;

edit1.Text:=inttostr(n-1);

StringGrid1.ColCount:=strtoint(edit1.Text)+1;

StringGrid1.RowCount:=strtoint(edit1.Text)+1;

for i:=0 to n-2 do begin

stringgrid1.Cells[0,i+1]:=Chr(Byte('A')+i);

stringgrid1.Cells[i+1,0]:=Chr(Byte('A')+i);

end;

stringgrid1.Cells[1,1]:='0';

stringgrid1.Cells[2,1]:='10';

stringgrid1.Cells[3,1]:='11';

stringgrid1.Cells[4,1]:='12';

stringgrid1.Cells[1,2]:='10';

stringgrid1.Cells[2,2]:='0';

stringgrid1.Cells[3,2]:='13';

stringgrid1.Cells[4,2]:='14';

stringgrid1.Cells[1,3]:='11';

stringgrid1.Cells[2,3]:='13';

stringgrid1.Cells[3,3]:='0';

stringgrid1.Cells[4,3]:='15';

stringgrid1.Cells[1,4]:='12';

stringgrid1.Cells[2,4]:='14';

stringgrid1.Cells[3,4]:='15';

stringgrid1.Cells[4,4]:='0';

label4.Caption:='A';

for i:=1 to N-1 do

for j:=1 to N-1 do

a[i,j]:=strtoint(stringgrid1.Cells[j,i]);

k:=1;

L:=0;

q:=1;

while K<N-1 do begin

label4.Caption:=label4.Caption+'-';

i:=q;

z:=1;

j:=1;

flag:=false;

while flag=false do begin

if a[i,j]=0 then

j:=j+1

else begin

min:=a[i,j];

i1:=i;

j1:=j;

flag:=true;

end;

for j:=1 to N-1 do

Задача Прима - Краскала 📙 Курсовая → 🆔 79653