Программирование задач оптимизации на графах в среде MS Excel

Содержание
ВВЕДЕНИЕ……………………………………………………………………...3

ГЛАВА I. Основные понятия теории графов……………………………....6

1.1. Актуальность разработки библиотек для работы с графами
……………………………………………………………………………………6-7
1.2. Объектно-ориентированные библиотеки для работы с графами
…………………………………………………………………………………………………..7-8
1.3. Библиотека AGraph…………………………………………………….8-23

Глава II. Алгоритмы и программы решения задач оптимизации на графах ……………………………………………………………………………………24

2.1. Задачи оптимизации на графах………………………………………24-27

2.2. Максимальное покрывающее дерево графа и его графическое изображение…………………………………………………………….27-32

2.3. Задача о максимальном потоке в сети………………………………32-39

2.4. Создание пользовательской функции для вычисления двумерной экспоненциальной функции…………………………………………………40-43

2.4. Программа изображения структуры неориентированного графа…......................................................................................................43-52

Заключение……………………………………………………………………53-54

Литература
Приложение
ГЛАВА I Основные понятия теории графов
1.1. Актуальность разработки библиотек для работы с графами
К настоящему времени накоплен большой опыт решения теоретико-графовых задач на ЭВМ. Программы для решения многих задач можно найти в глобальной сети Интернет. В то же время, использование независимо разработанных программ сопряжено с большими трудностями. К их числу относятся как общие, не зависящие от предметной области, технические проблемы (различные языки программирования, несовместимость программных и аппаратных средств), так и проблемы, связанные со спецификой теоретико-графовых задач (использование различных внутренних представлений графов). В связи с этим актуальной задачей является разработка более или менее универсальных библиотек, которые, с одной стороны, предоставляли бы пользователю высокоуровневые средства для работы с графами, а с другой, избавляли его от необходимости ручного программирования рутинных операций ввода-вывода или преобразований между различными внутренними представлениями графов. Разработка универсальной библиотеки для работы с графами является сложной задачей. Одной из проблем является большое разнообразие задач теории графов. Поскольку теоретические исследования и разработка новых алгоритмов непрерывно продолжаются, очевидно, что никакая библиотека не сможет решать все существующие задачи. Другой проблемой является обеспечение эффективности. Нередко существует несколько алгоритмов для решения одной и той же задачи, причем не всегда можно указать алгоритм, оптимальный во всех случаях: для одних графов более эффективным может быть один алгоритм, для других - другой. Разработчик универсальной библиотеки обычно не может позволить себе реализацию нескольких алгоритмов для решения одной задачи, поэтому ему приходится идти на компромиссы между эффективностью и универсальностью. При разработке библиотек для работы с графами возникают также многочисленные технические трудности. Для приемлемой с точки зрения эффективности реализации многих алгоритмов программисту необходимо иметь в своем распоряжении такие структуры данных, как динамические массивы, списки, стеки, очереди, приоритетные очереди, деревья поиска. Реализация всех необходимых структур данных в рамках одной библиотеки вряд ли возможна и оправдана, поэтому универсальная библиотека для работы с графами требует серьезной программной "инфраструктуры" в виде других библиотек.
Перечисленные проблемы могут вызвать сомнения относительно целесообразности создания универсальных библиотек для работы с графами, однако существуют весомые аргументы в пользу их создания. Во-первых, реализованные в подобной библиотеке базовые алгоритмы могут служить хорошей основой для создания более специализированных алгоритмов и программ, направленных на решение конкретных прикладных задач. Во-вторых, соображения эффективности не всегда являются определяющими - постоянный рост производительности ЭВМ все чаще выводит на первый план технологичность и скорость разработки программного обеспечения (разумеется, это не означает, что программист не должен стремиться к эффективному использованию вычислительных ресурсов). Наряду с "промышленным" программирования, универсальные библиотеки для работы с графами могут применяться в учебных целях, а также для поддержки теоретических исследований, связанных с алгоритмами и программами решения задач теории графов. В обоих случаях универсальность проблемной ориентации библиотеки более важна, чем максимальная эффективность реализованных в ней алгоритмов.
1.2. Объектно-ориентированные библиотеки для работы с графами
1.2.1 Преимущества объектно-ориентированного программирования при создании библиотек для работы с графами
При создании "первого поколения" библиотек для работы с графами использовались языки программирования Fortran, Algol, PL\1, затем С. Для решения теоретико-графовых задач использовались и непроцедурные языки, такие, как язык функционального программирования LISP и логического программирования PROLOG, однако из-за недостаточной эффективности и технологических трудностей разработки больших программных систем на этих языках эти языки не подходят для создания универсальных библиотек. С развитием объектно-ориентированного программирования (ООП) началась разработка объектно-ориентированных библиотек для работы с графами. Использование средств ООП при решении теоретико-графовых задач дает существенные преимущества по сравнению с традиционным структурным подходом, поскольку сам граф, его вершины и ребра являются "готовыми" объектами, данными самой природой задачи. К достоинствам ООП, которые наиболее ярко проявляются при работе с графами, можно отнести следующее:
1. программный код становится более компактным, улучшается его читаемость;
2. при реализации алгоритмов появляется возможность абстрагироваться от деталей внутреннего представления графа;
3. внутреннее представление графа можно менять в широких пределах без влияния на "высокоуровневые" составляющие библиотеки;
4. легко решается проблема "привязки" данных к вершинам и ребрам графа.
1.2.2 Обзор существующих объектно-ориентированных библиотек для работы с графами
В настоящее время существует несколько объектно-ориентированных библиотек, предоставляющих средства для работы с графами. Среди них можно отметить:
• LEDA (Library of Efficient Data types and Algorithms);
• GTL (Graph Template Library, University of Passau);
• GTL (Graph Template Library, Евгений Цыпнятов, Нижний Новгород), далее - GTL (Н-Новгород).
Все эти библиотеки написаны на языке C++.
Библиотека LEDA (последняя версия - 3.8) разрабатывается с 1988г. в Институте Информатики Макса Планка (Сарабрюккен, ФРГ). Библиотека предлагает различные абстрактные типы данных (стеки, очереди, приоритетные очереди, отображения, списки, множества, разбиения, словари, интервальные множества и др.), специализированные числовые типы данных (рациональные числа, большие вещественные числа, алгебраические числа и др.), графы и вспомогательные структуры данных для работы с графами. В LEDA реализованы алгоритмы решения ряда комбинаторных, алгебраических, геометрических и теоретико-графовых задач, средства графического ввода и вывода. Институт Информатики Макса Планка бесплатно предоставляет библиотеку, включая исходные тексты, по лицензии, которая дает право использовать LEDA для академических исследований и/или обучения, но не допускает коммерческое использование.
Программный интерфейс приложений (API) для работы с графами, Библиотека GTL (Евгений Цыпнятов, последняя версия - 1.0R8) существенно отличается от других библиотек по своей идеологии. Во-первых, библиотека поддерживает несколько внутренних представлений для графов - в виде массивов вершин и ребер, списков смежности, матрицы смежности. Существует также представление, которое объединяет все три перечисленные выше структуры хранения графов и обеспечивает их автоматическую синхронизацию. Представления реализованы в виде шаблонных классов; выбор нужного представления осуществляется при создании графа. Во-вторых, библиотека использует оригинальный способ придания необходимых "свойств" вершинам и ребрам графа (фактически, "свойства" - это атрибуты вершин и ребер) - механизм классов-"привкусов" (Flavor). Этот способ основан на использовании множественного наследования и параметризуемых (шаблонных) классов графов. Механизм "привкусов" будет рассмотрен при сравнении с аналогичными средствами библиотек LEDA и AGraph. В настоящее время GTL доступна только на платформе Win32, т.к. она существенно зависит от библиотеки MFC (Microsoft Foundation Classes).

1.3. Библиотека AGraph

1. Общая характеристика
При разработке библиотеки AGraph были поставлены следующие цели:
• охват широкого круга теоретико-графовых задач;
• простота использования;
• эффективность.
Библиотека AGraph написана на языке Object Pascal который используется в Delphi - среде быстрой разработки приложений (RAD) фирмы Inprise (бывшей Borland), и является, вероятно, единственной развитой библиотекой для работы с графами на Object Pascal. В то же время, используемый язык программирования - не главное отличие AGraph от других библиотек. При необходимости библиотека AGraph может быть переписана с использованием таких объектно-ориентированных языков программирования, как C++, Eiffel или Java. Перенос облегчается тем обстоятельством, что AGraph не использует стандартную библиотеки классов Delphi VCL (Visual Component Library), за исключением классов исключительных ситуаций (Exception).
В пользу выбора языка Object Pascal как средства создания библиотеки для работы с графами можно привести следующие соображения. К настоящему времени разработано немало объектно-ориентированных языков программирования (ООЯП): Smalltalk, C++, Java, Object Pascal, Eiffel, Oberon-2, Modula-3 и другие. Если исходить из достоинств и недостатков самих языков программирования, не принимая во внимание распространенность языка и качество его конкретных реализаций, то одним из лучших "кандидатов", на мой взгляд, является Eiffel. Однако, если учитывать конкретную платформу, которая имеется в распоряжении (персональный компьютер на процессоре семейства Intel 386, работающий под управлением операционных систем Windows или Linux), а также практически доступные системы программирования коммерческого качества, то выбор значительно сужается: остаются языки C++, Java и Object Pascal. Языки Smalltalk и Java не подходят по соображениям эффективности. Наиболее распространенный в настоящее ООЯП, C++, поддерживается на большинстве платформ и является мощным языком программирования. Важное значение имеет существование стандарта языка C++ (к сожалению, многие компиляторы C++ не вполне соответствуют этому стандарту). К недостаткам С++ можно отнести его значительно большую, по сравнению с Object Pascal, сложность. Учитывая цели, которые ставились при разработке библиотеки AGraph, в первую очередь - соображения простоты использования, выбор был сделан в пользу Object Pascal.
Язык Object Pascal в той его версии, которая реализована в Delphi, также является развитым объектно-ориентированным языком программирования. По сравнению с ранними версиями языка (Turbo Pascal и Borland Pascal), в Object Pascal некоторые изменения претерпела объектная модель, был реализован механизм свойств объектов (object property), добавлены средства обработки исключительных ситуаций (конструкции try...except и try...finally), появилась возможность передавать в процедуры и функции переменное количество параметров (open array параметры). В Delphi 4.0 появились динамические массивы, перегрузка (overloading) процедур и функций, а также возможность указывать для параметров процедур и функций значения, принимаемые по умолчанию. Среди важных языковых средств C++, которые не реализованы в Object Pascal, следует отметить множественное наследование и механизм шаблонов (templates). Последний недостаток удалось частично преодолеть с помощью "псевдошаблонов".
2. Внутреннее представление графов
Существуют различные способы внутреннего представления графов в оперативной памяти ЭВМ, в том числе в виде списков (массивов) вершин и ребер, списков (массивов) смежности, матриц смежности, а также в виде комбинаций этих структур хранения. Выбор внутреннего представления оказывает решающее влияние на эффективность выполнения различных операций над графами и во многом определяет "технологию" использования той или иной библиотеки в прикладных программах.
Ниже перечисленные структуры хранения графов будут рассмотрены более подробно, но перед этим необходимо сделать следующее замечание. В теории графов вершины и ребра графов, как правило, лишены индивидуальности: при таком подходе граф можно задать, например, булевской матрицей смежности, где логическая единица на пересечении i-ой строки и j-го столбца означает существование ребра (или дуги) между i-ой и j-ой вершинами графа. В то же время, во всех рассматриваемых библиотеках вершины и ребра графа считаются уникальными объектами (здесь термин "объект" употребляется в контексте объектно-ориентированного программирования), которые различаются, по крайней мере, тем, что каждый из них занимает отдельный участок в оперативной памяти ЭВМ. Объект-вершина может содержать или не содержать какие-либо данные; объект-ребро содержит, как минимум, указатели на инцидентные ему вершины. Если подходить с технологической точки зрения, то наличие уникальных объектов-вершин и объектов-ребер повышает удобство реализации и эффективность многих алгоритмов (хотя и неэкономично в смысле расхода оперативной памяти). Существует и более фундаментальная причина: при решении прикладных задач вершины графа, а иногда и его ребра, соответствуют реальным объектам предметной области. Таким образом, структуры хранения графов в объектно-ориентированной библиотеке для работы с графами обеспечивают хранение не только "математического" графа, но и объектов, представляющих вершины и ребра этого графа. Еще одно замечание необходимо сделать относительно использования списков и/или массивов: эти структуры данных будут считаться взаимозаменяемыми, пока изложение не коснется конкретных библиотек.
Списки вершин и ребер
Граф представляется в виде двух списков, один из которых содержит указатели на его вершины, второй - на ребра (как всегда, каждое ребро хранит в себе указатели на инцидентные ему вершины). Данная структура хранения обеспечивает эффективное добавление в граф вершин и ребер, а также итерацию по вершинам и ребрам. В то же время, это представления неудобно, когда необходимо определить ребра, инцидентные заданной вершине графа.
Списки смежности
Граф представляется списком входящих в него вершин. В свою очередь, каждая вершина содержит список инцидентных ей ребер (или списки входящих и исходящих дуг в случае орграфов). Данное представление обеспечивает эффективное добавление в граф вершин и ребер, итерацию по вершинам графа и доступ к ребрам, инцидентным заданной вершине, но не поддерживает итерацию по ребрам графа.
Матрицы смежности
Граф задается квадратной матрицей размерности NxN, где N - количество вершин в графе; на пересечении i-го столбца и j-ой строки матрицы находится либо указатель на ребро, соединяющее вершины i и j, если эти вершины инцидентны, либо nil, если они не инцидентны. Вершины могут либо храниться в отдельном списке, либо только в составе инцидентных им ребер (в случае связных графов). Это представление удобно для реализации некоторых алгоритмов, но не обеспечивает эффективное добавление и удаление вершин. Кроме того, оно является самым неэкономичным по расходу памяти (за исключением графов, в которых количество ребер значительно превышает количество вершин).
Из приведенного анализа видно, что каждая из трех рассмотренных структур хранения графов обладает своими достоинствами и недостатками. Внутреннее представление графов в универсальной библиотеке должно обеспечивать эффективную реализацию большого числа разнообразных алгоритмов, поэтому такие библиотеки используют комбинированные представления, либо, как это сделано в GTL, позволяют явно указать внутреннее представление при создании объекта-графа.
Распространенным вариантом комбинированного внутреннего представления является объединение представлений в виде списков вершин/ребер и списков смежности. Такая структура хранения обеспечивает эффективное добавление и удаление вершин и ребер, итерацию по вершинам и ребрам и, в то же время, позволяет легко определить ребра, инцидентные заданной вершине графа. Подобное представление используется в библиотеках LEDA и GTL. Библиотека AGraph также использует комбинированное представление, но вместо списков применяются динамические массивы указателей, реализованные в библиотеке Vectors (класс TPointerVector, он же TClassList). Сравнение списков и динамических массивов, реализованных в Vectors, с точки зрения эффктивности выполнения различных операций приведено в следующей таблице (n обозначает количество вершин в графе, m - количество ребер):
Операция Эффективность
Списки Массивы
Добавление вершины | ребра O(1) O(n) | O(m) в худшем случае,
O(1) в среднем
Удаление вершины |
ребра O(1) O(n) | O(m)
Доступ к вершине | ребру по индексу O(n) | O(m) O(1)
Списки позволяют эффективно добавлять и удалять вершины (ребра) графа, но не обеспечивают прямой доступ к ним по индексу (т.е. порядковому номеру) вершины (ребра) в соответствующем списке. Возможность получить ссылку на элемент графа по его индексу является весьма полезной при реализации многих алгоритмов, поэтому для решения данной проблемы приходится использовать дополнительные структуры данных.
Достоинством динамических массивов является быстрый доступ к элементам по индексу. Наиболее "дорогой" операцией при использовании динамических массивов является добавление элемента, поскольку в худшем случае для этого требуется выделить новый блок памяти увеличенного размера, скопировать содержимое старого блока памяти в новый и освободить старый блок, причем, по крайней мере, этап копирования имеет сложность O(n). В то же время, в среднем операция добавления вершин (ребер) в AGraph выполняется более эффективно. Это достигается за счет того, что при увеличении размера динамического массива (вектора) в библиотеке Vectors память выделяется сразу для нескольких элементов, поэтому в большинстве случаев операция добавления элемента не требует фактического изменения размера вектора.
Особенностью библиотеки AGraph является то, что каждая вершина (ребро) графа хранит собственный индекс в массиве вершин (ребер) графа. Наличие такой "обратной" ссылки во многих случаях значительно упрощает работу с графом. Поддержание этой ссылки не ухудшает асимптотическую сложность операций добавления и удаления вершин (ребер) графа.
3.Базовые средства
К базовым средствам библиотеки для работы с графами относятся средства, обеспечивающие выполнение наиболее общих операций над графом и его элементами, в том числе создание и уничтожение объектов-графов, добавление в граф вершин и ребер, удаление их из графа, итерацию по вершинам и ребрам и т.д. Базовые средства библиотеки AGraph в основном соответствуют аналогичным средствам других библиотек (см. пример 1). При создании программного интерфейса приложений (API) библиотеки AGraph первоочередное внимание уделялось обеспечению максимальных функциональных возможностей библиотеки при сохранении простоты ее использования. Имена классов библиотеки, их полей, методов и свойств (property) соответствуют распространенной англоязычной терминологии теории графов и общепринятым соглашениям языка Object Pascal.
// создание графа
G:=TGraph.Create;
// добавление вершин и ребер
V:=G.AddVertex;
G.AddVertices(5);
E:=G.AddEdge(G[0], G[1]); // ребро (v0, v1)
G.AddEdgeI(0, 3); // ребро (v0, v3)
G.AddEdges([1, 2, 2, 4]); // ребра (v1, v2) и (v2, v4)
// итерация по вершинам графа
for I:=0 to G.VertexCount - 1 do begin
V:=G.Vertices[I];
// итерация по ребрам, инцидентным заданной вершине графа
for J:=0 to V.Degree - 1 do
With V.IncidentEdge[J] do {...} ;
end;
// итерация по ребрам графа
for I:=0 to G.EdgeCount - 1 do
With G.Edges[I] do {...} ;
// удаление ребра (v0, v1)
E.Free;
// удаление ребра (v1, v2)
G.GetEdgeI(1, 2).Free;
// удаление вершины (с инцидентными ребрами)
G.Vertices[2].Free;
// уничтожение графа
G.Free;
Пример 1. Базовые операции над графами в библиотеке AGraph.
Если сравнивать библиотеки AGraph и LEDA, то можно отметить два существенных отличия. Первое из них связано с использованием динамических массивов для внутреннего представления графов в библиотеке AGraph. Массивы позволяют применять простой for-цикл для итерации по вершинам и ребрам графа. В библиотеке LEDA, использующей списки для хранения вершин и ребер, для той же цели необходимо использовать специальные макросы, а в библиотеке GTL (Passau), основанной на STL, - итераторы STL [библиотека LEDA также поддерживает "STL-style" итераторы (пока в качестве экспериментальной возможности)]. Второе отличие заключается в том, что в AGraph для удаления вершин и ребер из графа используется стандартный способ уничтожения объектов Object Pascal - вызов метода Free, в то время как в библиотеке LEDA для удаления вершин и ребер из графа приходится использовать специальные методы классов-графов. ....