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

Введение

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

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

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

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

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

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

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

В качестве примера я выбрал задачу о прокладке телефонного кабеля между городами. Потому что  я  считаю что это наиболее яркий  и понятный пример раскрывающую задачу Прима-Краскала  эта задача должна в конечном итоги показать наикротчайший путь и связь между городами. 
Раздел 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. Особенность его в том, что в нем реализован сложный механизм объединения меню. Это необходимо по следующим причинам:

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

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

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