close

Вход

Забыли?

вход по аккаунту

Донцова Юлия Андреевна. Разработка программного обеспечения для моделирования на графах комбинаторных задач

код для вставки
Powered by TCPDF (www.tcpdf.org)
Powered by TCPDF (www.tcpdf.org)
3
1.1.
Постановка задачи разработки программного обеспечения для
моделирования на графах
1.2.
Основные теоретические сведения, необходимые для решения
транспортных задач
1.3.Постановка задачи о нахождении максимального потока в сети
1.4. Применение алгоритма Форда–Фалкерсона к решению задачи
нахождения максимального потока
1.5. Применение алгоритма Дейкстры к решению задачи о нахождении
кратчайшего пути
1.6. Постановка задачи о назначениях
1.7. Применение Венгерского алгоритма для решения задачи о назначениях
Глава II. РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
2.1. Программная реализация алгоритма Форда – Фалкерсона
2.1.1. Описание программного обеспечения, реализованного с помощью
языка Python. Содержимое исполняемого файла «maxflow.py»
2.1.2. Описание программного обеспечения, реализующего интерфейс для
пользователя. Содержимое исполняемого файла «window.py»
2.2. Программная реализация алгоритма Дейкстры
2.2.1. Описание программного обеспечения, реализованного с помощью
языка Python. Содержимое исполняемого файла «deikstra.py»
2.2.2. Описание программного обеспечения, реализующего интерфейс для
пользователя. Файл «window_deikstra.py»
2.2.3. Описание процесса разработки откна для вывода результатов. Файл
window_result_deikstra.py
2.3. Программная реализация решения задачи о назначениях с помощью
Венгерского алгоритма
2.3.1. Описание программного обеспечения, реализованного с помощью
языка Python. Содержимое исполняемых файлов «n_min.py» и «n_max.py»
2.3.2. Описание программного обеспечения, реализующего интерфейс для
пользователя. Файл «window_ naz.py»
4
2.3.3. Описание процесса разработки откна для вывода результатов. Файлы
«window_result_naz_max.py» и «window_result_naz_min.py»
2.4. Разработка дополнительных скриптов
2.4.1. Разработка стартового окна приложения
2.4.2. Описание программного обеспечения, реализующего генерацию
случайных входных данных. Содержимое исполняемого файла «randomgraph.py»
Глава III Исследование задач
3.1. Исследование задач на нахождение максимального потока в сети с
помощью алгоритма Форда-Фалкерсона
3.1.1. Пошаговый пример применения алгоритма Форда-Фалкерсона для
решения задачи о нахождении максимального потока в сети
3.1.2. Примеры решения более сложных задач и моделирование их путем
использования разработанного программного обеспечения
3.1.3. Решение прикладной задачи на нахождение максимального потока
3.2. Исследование задач на нахождение минимального потока в сети с
помощь алгоритма Дейкстры
3.2.1. Пошаговый пример применения алгоритма Дейкстры для решения
задачи о нахождении минимального потока в сети
3.2.2. Исследование более сложных задач на нахождение минимального
потока в сети
3.2.3. Решение прикладной задачи на нахождение минимального потока
3.3. Исследование задач о назначениях
3.3.1. Пошаговые примеры решения задач о назначении с помощью
Венгерского алгоритма
3.3.2. Анализ эффективности разработанного программного обеспечения
при решении задач различных размерностей
3.3.3. Решение прикладной задачи о назначениях
Заключение
Список источников
Powered by TCPDF (www.tcpdf.org)
Powered by TCPDF (www.tcpdf.org)
7
Аннотация
Магистерская диссертация на тему «Разработка программного обеспечения
для моделирования на графах комбинаторных задач» содержит 126 страниц
текста, рисунков – 52, таблиц – 14, формул – 19, использованных источников – 32,
приложений - 12.
В настоящий момент подобные задачи востребованы в связи с их широким
применением в различных отраслях. С их решением сталкиваются, например, при
оптимизации
транспортных
путей,
сетей
трубопроводов,
моделировании
различных процессов физики и химии, составлении расписания авиарейсов и
перевозки грузов, обработке цифровых изображений и для решения родственных
задач теории графов.
Ключевые
слова:
комбинаторные
задачи,
максимальный
поток,
минимальный поток, задача о назначениях, алгоритм Форда-Фалкерсона,
алгоритм Дейкстры, Венгерский алгоритм
Предмет исследования. Содержание программного обеспечения для
моделирования различных комбинаторных задач на графах.
Объект исследования. Моделирование различных комбинаторных задач на
графах.
Цель работы. Разработка программного обеспечения для моделирования
комбинаторных задач на графах.
Метод исследования. Для исследования применяется метод анализа и
моделирования.
Результаты
работы.
В
магистерской
диссертации
разработано
программное обеспечение на языке Python, позволяющая решать и моделировать
комбинаторные задачи на графах при различных входных параметрах. Так же
8
выполнена апробация программного обеспечения на тестовых и прикладных
задачах.
Работа имеет теоретическое и практическое значение, т.к. разработанный
комплекс программ может применяться для дальнейших исследований при
разнообразных входных параметрах и решении задач прикладного характера,
связанных с различными отраслями человеческой жизнедеятельности.
Abstract
The master's thesis on "Software development for modeling on graphs of
combinatorial problems" contains 119 pages of text, drawings - 52 tables - 14 formulas 19 used sources - 32 applications – 12
At the moment, such tasks are in demand in connection with their wide
application in various industries. They are faced with their solution, for example, when
optimizing transport routes, pipeline networks, modeling various physics and chemistry
processes, scheduling flights and cargo transportation, processing digital images and
solving related graph theory problems.
Keywords: combinatorial problems, maximum flow, minimum flow, assignment
problem, Ford-Falkerson algorithm, Dijkstra`s algorithm, Hungarian algorithm.
The subject of the study. The contents of the software for modeling various
combinatorial problems on graphs.
The object of study. Modeling of various combinatorial problems on graphs.
The purpose of the work. Development of software for modeling combinatorial
problems on graphs.
Method of the study. The method of analysis and modeling is used for the study.
9
The results of the work. In the master's thesis, software is developed in Python,
which allows solving and modeling combinatorial problems on graphs with different
input parameters. Also, the testing of software on test and applied tasks was carried out.
The work has theoretical and practical importance, because the developed set of
programs can be used for further research with a variety of input parameters and solving
applied problems related to various branches of human life.
10
СОДЕРЖАНИЕ
ВВЕДЕНИЕ .................................................................................................................... 12
ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ.......................................................................... 19
1.1. Постановка задачи разработки программного обеспечения для
моделирования на графах ............................................. Error! Bookmark not defined.
1.2. Основные теоретические сведения, необходимые для решения транспортных
задач ……………………………………………………………………………………20
1.3. Постановка задачи о нахождении максимального потока в сети ................... 22
1.4. Применение алгоритма Форда–Фалкерсона к решению задачи нахождения
максимального потока .................................................................................................. 24
1.5. Применение алгоритма Дейкстры к решению задачи о нахождении
кратчайшего пути .......................................................................................................... 27
1.6. Постановка задачи о назначениях ...................................................................... 30
1.7. Применение Венгерского алгоритма для решения задачи о назначениях .... 33
ГЛАВА 2. РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ............................ 35
2.1. Программная реализация алгоритма Форда – Фалкерсона ............................. 35
2.1.1. Описание программного обеспечения, реализованного с помощью языка
Python. Содержимое исполняемого файла «maxflow.py» ......................................... 36
2.1.2. Описание программного обеспечения, реализующего интерфейс для
пользователя. Содержимое исполняемого файла «window.py» ............................... 46
2.2. Программная реализация алгоритма Дейкстры ............................................... 65
2.2.1. Описание программного обеспечения, реализованного с помощью
языка Python. Содержимое исполняемого файла «deikstra.py» ................................ 66
2.2.2. Описание программного обеспечения, реализующего интерфейс для
пользователя. Файл «window_deikstra.py».................................................................. 70
2.2.3 Описание процесса разработки откна для вывода результатов. Файл
«window_result_deikstra.py» ......................................................................................... 72
2.3. Программная реализация решения задачи о назначениях с помощью
Венгерского алгоритма ................................................................................................. 74
2.3.1. Описание программного обеспечения, реализованного с помощью
языка Python. Содержимое исполняемых файлов «n_min.py» и «n_max.py» ......... 75
2.3.2. Описание программного обеспечения, реализующего интерфейс для
пользователя. Файл «window_ naz.py» ........................................................................ 80
11
2.3.3. Описание процесса разработки откна для вывода результатов. Файлы
«window_result_naz_max.py» и «window_result_naz_min.py» ................................... 83
2.4. Разработка дополнительных скриптов .............................................................. 85
2.4.1. Разработка стартового окна приложения ....................................................... 85
2.4.2. Описание программного обеспечения, реализующего генерацию
случайных входных данных. Содержимое исполняемого файла «randomgraph.py»
………………………………………………………………………………….87
ГЛАВА 3. ИССЛЕДОВАНИЕ ЗАДАЧ ....................................................................... 91
3.1. Исследование задач на нахождение максимального потока в сети с помощью
алгоритма Форда-Фалкерсона...................................................................................... 91
3.1.1. Пошаговый пример применения алгоритма Форда-Фалкерсона для решения
задачи о нахождении максимального потока в сети ................................................. 91
3.1.2. Примеры решения более сложных задач и моделирование их путем
использования разработанного программного обеспечения .................................... 99
3.1.3. Решение прикладной задачи на нахождение максимального потока ......... 105
3.2. Исследование задач на нахождение минимального потока в сети с помощь
алгоритма Дейкстры.................................................................................................... 109
3.2.1. Пошаговый пример применения алгоритма Дейкстры для решения задачи о
нахождении минимального потока в сети ................................................................ 110
3.2.2. Исследование более сложных задач на нахождение минимального потока в
сети................................................................................................................................ 115
3.2.3. Решение прикладной задачи на нахождение минимального потока .......... 116
3.3. Исследование задач о назначениях .................................................................... 118
3.3.1. Пошаговые примеры решения задач о назначении с помощью Венгерского
алгоритма ..................................................................................................................... 118
3.3.2. Анализ эффективности разработанного программного обеспечения при
решении задач различных размерностей .................................................................. 121
3.3.3. Решение прикладной задачи о назначениях ................................................... 123
ЗАКЛЮЧЕНИЕ ........................................................................................................... 125
СПИСОК ИСТОЧНИКОВ .......................................................................................... 128
ПРИЛОЖЕНИЕ ........................................................................................................... 130
12
ВВЕДЕНИЕ
Обоснование выбора темы и ее актуальность
В 40-х годах XX века впервые появилась такая дисциплина, как линейное
программирование. Ее рождение было обусловлено ростом экономики и
необходимостью в разработке методов, позволяющих с большой точностью
рассчитать наиболее выгодную прибыль. Линейное программирование является
одним из разделов математики, ориентированным на нахождение экстремума
(максимума или минимума) в задачах, которые описываются линейными
уравнениями [1].
Примерно в то же время прогрессивность компьютерных технологий и
необходимость создания средств обработки и передачи информации, определили
бурное развитие дискретной математики. Эта область математики отвечает за
изучение дискретных структур, возникающих как в пределах математики, так и в
ее приложениях. В основном это различные конечные структуры (конечные
группы, конечные автоматы, машины Тьюринга), алгебраические системы,
вычислительные схемы, клеточные автоматы и т.д.
Две эти дисциплины имеют очень тесные связи между собой. Многие
задачи линейного программирования являются линеаризацией комбинаторных
задач из дискретной математики.
Одними из самых актуальных задач линейного программирования и
дискретной математики на сегодняшнее время являются задачи транспортного
типа. Их применение достаточно широко. Наиболее часто они используются в
транспортных копаниях, аэропортах, системе трубопроводов, а также на
различных производствах [2].
Проблема программной реализации становится весомой не только из-за
сложности алгоритмов, направленных на решение данных задач. Если говорить о
таких больших моделях, как аэропорт, то следует помнить о масштабах
13
используемых данных. Достаточно сложно вручную просчитать расписание
авиарейсов различных компаний и исключить возможные ошибки. Отсюда
исходит необходимость в создании такого ПО, которое сможет не только оказать
помощь в решении тех или иных задач, но также будет оперировать достаточно
большим объемом данных.
Для данной работы были выбраны задачи, рением которых занимается и
линейное программирование и дискретная математика:
•
Задача о нахождении максимального потока в сети
•
Задача о нахождении минимального пути
•
Задача о назначениях
Эти задачи интересны как с точки зрения оптимизации в линейном
программировании, так и со стороны применения алгоритмов теории графов.
Степень разработанности проблемы
Задача о максимальном потоке в сети изучается уже более 60 лет. В 1956
г. Лестер Форд (1927-2017) и Делберт Фалкресон (1924-1976) предложили
рассматривать для решения этой задачи ориентированную сеть и искать решение
с помощью итерационного алгоритма. До этого времени задача решалась simplexметодом линейного программирования, что было крайне не эффективно. Новый
алгоритм получил название алгоритм Форда-Фалкерсона. В дальнейшем
алгоритм неоднократно модифицировали и улучшали, однако основная его идея
осталось неизменной и алгоритм Форда-Фалкерсона до сих остается базисом для
всех передовых достижений в исследовании задачи о нахождении максимального
потока [3].
Одной из рассматриваемых в теории графов задач является задача о
нахождении минимального пути. Голландский ученый Эдсгер Вайб Дейкстра
(1930-2002) внес большой вклад в развитие динамического программирования и
теорию графов. Одно из наиболее известных его достижение – создание
14
алгоритма Дейкстры, разработанный в 1959 г. и предназначенный специально
для поиска кратчайшего расстояния между вершинами [4].
Задача о назначениях является частным случаем транспортной задачи и
может быть решена с использованием методов линейного программирования или
алгоритма решения транспортной задачи. Однако в виду ее особой структуры в
1955 г. для нее был разработан специальный Венгерский алгоритм. Создателем
алгоритма является Гарольд Кун (1925-2014) , в своих работах он опирался на
ранние работы двух венгерских математиков Денеша Кенига и Эйтена
Эгервари, в честь которых алгоритм и получил название [5].
Помимо выбора алгоритма для решения задач необходимо уделить
внимание выбору современного языка программирования, способного в процессе
счета обеспечить высокую скорость и точность решения при работе с большим
объемом информации. Так
как при решении данных
задач
возникает
необходимость использования матриц больших размерностей, на практике часто
приходится сталкиваться с большим временем исполнения программы, либо
вообще с невозможностью получить ответ. Для реализации алгоритмов был
выбран высокоуровневый язык программирования общего назначения – Python
[6]. Он располагает большим количеством встроенных и подключаемых модулей
и библиотек. В частности NumPy - расширение, добавляющее поддержку
больших многомерных массивов и матриц, вместе с большой библиотекой
высокоуровневых математических функций для операций с этими массивами [7].
Кроме
того
была
использована
подключаемая
библиотека
Graphviz,
Содержание программного обеспечения для моделирования
различных
предназначенная для визуализации графов [8].
Предмет исследования.
комбинаторных задач на графах.
15
Объект исследования.
Моделирование различных комбинаторных задач на графах.
Цель работы.
Разработка программного обеспечения для моделирования комбинаторных
задач на графах.
Основные задачи исследования:
1.
Исследование задачи на актуальность, анализ источников,
соответствующих тематике работы;
2.
Расширение
и
систематизация
теоретических
знаний,
касающихся математического аппарата теории графов;
3.
Реализация
программного
кода,
посредством
языка
программирования Python, для решения задач о нахождении максимального
потока, минимального потока и задачи о назначениях;
4.
Разработка дружественного интерфейса для взаимодействия
пользователя и программного обеспечения;
5.
Исследование
и
анализ
эффективности
разработанного
программного обеспечения.
Метод исследования.
Для исследования применяется метод анализа и моделирования.
Теоретическое и практическое значение работы
Работа имеет теоретическое и практическое значение, так как теоретические
данные, изложенные в работе, могут применяться для дальнейшего исследования
более сложных алгоритмов теории графов, а разработанный комплекс программ
может использоваться для моделирования разнообразных процессов при
различных входных данных. Например, при оптимизации транспортных путей,
16
сетей трубопроводов, составлении расписания авиарейсов или грузоперевозок,
моделирования экономических задач о наилучший инвестициях и для решения
родственных задач теории графов.
Структура работы
Работа состоит из введения, трех глав, заключения списка источников и
приложений.
Во введении рассматривается актуальность работы, ставится цель и
обозначаются задачи, необходимые для достижения поставленной цели.
Первая часть представляет собой совокупность теоретических данных об
изучаемых задачах. В ней описаны математические постановки задач и
алгоритмы, используемые для их решения.
Во второй главе описывается программная реализация поставленной задачи:
взаимодействие всех компонентов программного обеспечения на языке Python со
вспомогательными библиотеками.
В третьей главе проводится апробация разработанного программного
обеспечения.
В заключении делаются выводы по проделанной работе и рассматриваются
дальнейшие
перспективы
применения
разработанного
программного
обеспечения.
Приводится список использованных источников.
В приложениях приведен полный исходный код
программного обеспечения.
разработанного
17
Апробация работы
Промежуточные
результаты
исследования
были
опубликованы
в
следующих научных работах:
1. Разработка программного обеспечения для реализации алгоритма ФордаФалкерсона нахождения максимального потока в сети // Вестник
студенческих работ Орловского государственного университета (в
рамках «Недели науки-2015»). – Орел: ФГБОУ ВПО «ОГУ», 2015. вып.7 – с. 20-22.
2. Разработка программного обеспечения посредством языка Python для
исследования максимального потока в сети // Молодежный научный
форум: Технические и математические науки. Электронный сборник
статей по материалам ХХХ студенческой международной заочной
научно-практической конференции. – Москва: Изд. «МЦНО». – 2016. –
№ 1 (30) – с. 22-26.
3. О решении прикладных задач путем моделирования на графах //
Современные проблемы физико-математических наук. Материалы II
международной научно-практической конференции, 24-27 ноября 2016 г.
/ под общ. ред. Т.Н. Можаровой. — Орел: ОГУ, 2016. – с. 170-172.
4. Функционал
программного
обеспечения,
реализующего
алгоритм
нахождения максимального потока в различных сетях // Научнопрактический электронный журнал «Аллея науки» \ Отв. ред. Шелистов
Д.А. – Томск. – 2016. – выпуск №4 (4) – с. 761-765.
5. Функционал программного обеспечения, реализующего нахождение
кратчайшего пути в различных сетях с помощью алгоритма Дейкстры //
Научно-практический электронный журнал «Аллея науки» \ Отв. ред.
Шелистов Д.А. – Томск. – 2017. – выпуск №12 (2) – с. 395-398.
6. О разработке программного обеспечения для реализации алгоритмов
оптимизации на сетях и графах // Международный научный электронный
18
журнал «Синергия наук» \ Отв. ред. Сиденко В.П. – Санкт-Петербург: −
2017.− № 15 (сентябрь).− с. 582-587.
7. Аспекты разработки программного обеспечения для решения задачи о
назначениях с помощью Венгерского алгоритма // Наука среди нас:
сетевое научно-практическое издание №1 (5) / под ред. В.И. Вахрушева.
– Магнитогорск : ИП Вахрушев В.И., 26.01.2018. – 76-81.
8. Разработка программного обеспечения для реализации Венгерского
алгоритма для решения задачи о назначениях // Молодежный научный
форум: Технические и математические науки. Электронный сборник
статей по материалам LIII студенческой международной научнопрактической конференции. – Москва: Изд. «МЦНО». – 2018. – № 1 (53)
– с. 78-82.
9. Решение прикладных задач о назначении с помощью программного
обеспечения, реализующего Венгерский алгоритм // Международный
научный электронный журнал «Синергия наук» \ Отв. ред. Сиденко В.П.
– Санкт-Петербург: − 2018.− № 19 (январь).− с. 1560-1566.
19
ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ
1.1.
Постановка задачи разработки программного обеспечения для
моделирования на графах
Ежедневно,
во
всех
областях
своей
жизнедеятельности
человек
сталкивается с проблемой: как получить наибольшую выгоду, потратив
наименьшее количество ресурсов? Эта проблема относится к выбору маршрутов
при планировании отдыха или командировки, к приобретению продуктов
потребления, к сфере услуг, а так же ко многим рабочим моментам. При решении
этих
задач
возникает
необходимость
просчитывать большое количество
различных вероятностных событий и комбинаций этих событий.
Эти задачи относятся к такой дисциплине как теория графов, которая
является областью дискретной математики и отличается геометрическим
подходом к изучению объектов. Задачи теории графов имеют достаточно широкое
применение. С их решением сталкиваются при распределении авиарейсов,
составлении плана перевозок грузов в транспортных компаниях, размещении
сотрудников на должности в организациях. При решении этих задач приходится
оперировать достаточно большим объемом данных. Отсюда исходит актуальность
разработки программного обеспечения для моделирования комбинаторных задач
на графах.
В данной работе рассматриваются следующие задачи и алгоритмы их
решения:
•
Задача о максимальном потоке – алгоритм Форда-Фалкерсона;
•
Задача о минимальном потоке - алгоритм Дейкстры;
•
Задача о назначениях – Венгерский алгоритм
Для более глубокого понимания данных задач и алгоритмов необходимо
располагать некоторыми теоретическими данными. Рассмотрим их более
подробно.
20
1.2.
Основные теоретические сведения, необходимые для решения
транспортных задач
Граф – основной объект изучения математической теории графов –
совокупность непустого множества вершин и наборов пар вершин (связей между
вершинами). Объекты представляются как вершины, или узлы графа, а связи – как
дуги, или ребра. Для разных областей применения виды графов различаются по
направленности, ограничениям на число связей и иными данными о вершинах и
ребрах [9].
Говорят, что две вершины u и v графа смежны, если множество {u, v}
является ребром, и не смежны, в противном случае. Если e = {u, v} – ребро, то
вершины u и v называют его концами. В этой ситуации говорят также, что ребро
e соединяет вершины u и v, и что вершина u ( или v) и ребро e инцидентны. Два
ребра называются смежными, если они имеют общую вершину.
Ориентированный граф – совокупность непустого множества вершин и
ребер (дуг) между ними, имеющих определенное направление.
Графы можно задавать несколькими способами:
– геометрически;
– матрицей инцидентности;
– матрицей смежности.
Мы будем использовать последний способ. Матрицей смежности графа G
называется матрица порядка n×n, элементы которой определяются следующим
образом:
– 1, если дуга из вершины i в вершину j существует;
– 0, если дуга из вершины i в вершину j отсутствует.
Определение графа в виде матрицы смежности так же является наиболее
предпочтительным для представления графа в памяти компьютера, поскольку
такой способ представления позволяет значительно облегчить работу с так
называемыми плотными графами (плотным графом в математике называют граф,
21
в котором число ребер близко к максимальному). Так же матрица смежности
позволяет максимально быстро определить наличие ребра между двумя
произвольными вершиными.
Транспортная сеть–это ориентированный граф (, ), где E – множество
вершин графа, U – множество дуг. Дуги графа будем обозначать через (, ),
где , . Это означает, что дуга выходит из вершины u и входит в вершину v
[10].
В транспортной сети выполняются следующие условия:
•
Существует одна и только одна вершина из множества E, в
которую не заходит ни одна дуга из множества U. Эта вершина называется
истоком и обозначается s.
•
Существует одна и только одна вершина из множества E, из
которой не выходит ни одной дуги из множества U. Эта вершина
называется стоком и обозначается t.
•
Каждой дуге поставлено в соответствие целое число (, ) ≥ 0,
которое называется пропускной способностью дуги.
Пропускные способности дуг задаются в виде квадратной матрицы
смежности C размерности n×n. Она немного отличается от обычной матрицы
смежности. Каждому элементу  будет присваиваться значение не единицы, а
соответствующей величины пропускной способности дуги из i-той вершины в jтую. Соответственно, если дуги из i в j не существует, то значение пропускной
способности равно нулю. Такая матрица называется матрицей пропускных
способностей сети.
Потоком называют функцию (, ), определенную на множестве U и
обладающую следующими свойствами:
•
(, ) ≤ (, ) – значение потока не превышает значение
пропускной способности дуги.
•
(, ) = −(, )
–
поток
из
i-той
противоположен потоку из j-той вершины в i-тую.
вершины
в
j-тую
22
•
(, ) ≥ 0 – поток является величиной неотрицательной.
Квадратная матрица смежности F размерности n×n, в которой каждому
элементу  соответствует величина потока, протекающего по дуге из i-той
вершины в j-тую, называется матрицей потоков сети. Начальное значение
потока, а соответственно и величина всех элементов матрицы  равняется нулю.
1.3. Постановка задачи о нахождении максимального потока в сети
Дуга (u,v) называется насыщенной в том случае, если выполняется условие
(, ) = (, )
(1)
То есть, если значение потока становится равным значению пропускной
способности дуги. Это означает, что более через эту дугу нельзя пройти при
построении цепей в графе.
Поток называется полным, если любой путь из источника в сток содержит
в себе хотя бы одну насыщенную дугу.
Поток
называется
максимальным,
если
его
величина
принимает
максимальное значение по сравнению с другими допустимыми потоками в сети.
Очевидно, что максимальный поток является полным потоком. При этом
следует помнить, что значение потока - сумма исходящего потока из истока,
должны быть равна сумме входящего потока в сток.
Задача о максимальном потоке: необходимо найти такой поток, чтобы
величина
∑ (, )
(2)
(,)
принимала
максимальное
значение. Требуется
определить
значение
максимального потока в сети, который можно пропустить из источника в сток и
его распределение по дугам [11].
Для того чтобы решить эту задачу, помимо алгоритма вычисления,
необходимо будет применить какой-либо метод систематического обхода графа.
23
Он будет заключаться в посещении всех вершин графа и исследовании всех его
ребер. Такой обход можно совершить различными способами. Наиболее
подходящим
в
эффективности,
данной
будет
ситуации,
являться
в
силу
алгоритм
своей
простоты
поиска
в
и
ширину
высокой
(BFS –
Breadth First Search) [12].
Алгоритм не определяет действия, выполняющиеся при посещении
вершины или исследовании ребра. Он определяет эффективную стратегию
посещения всех необходимых вершин, что является не менее важной задачей.
Введем необходимые определения, для лучшего понимания работы алгоритма.
Посещенная вершина – вершина с момента ее посещения и до конца
работы алгоритма (факт посещения запоминается).
Новая вершина – вершина, которая еще не посещена.
Открытая вершина – посещенная вершина, до момента исследования всех
инцидетных ей ребер, то есть ребер, через которые у нее есть связь с другими
вершинами.
Закрытая вершина – посещенная вершина, после того, как исследованы все
инцидентные ей ребра.
Идея поиска в ширину состоит в том, чтобы посещать вершины в порядке
их удаленности от начальной вершины – источника. Сначала посещается сама
вершина – источник, затем все вершины, смежные с ней, то есть находящиеся от
нее на расстоянии 1, затем вершины, находящиеся от нее на расстоянии 2 и так
далее.
Вначале все вершины помечаются как новые. Первой посещается вершина –
источник, она становится единственной открытой вершиной. В дальнейшем
каждый очередной шаг начинается с выбора некоторой открытой вершины X. Эта
вершина становится активной. После исследуются все ребра, инцидентные
активной вершине. Если ребро соединяет вершину X с новой вершиной Y, то
вершина Y посещается и превращается в открытую. Когда все ребра, инцидентные
активной вершине, исследованы, становится закрытой. Зачем выбирается новая
24
активная вершина, и описанные выше действия повторяются вновь. Процесс
продолжается до того момента, пока множество активных вершин не станет
пустым.
Основная особенность данного алгоритма, которая отличает его от
остальных способов обхода графа, состоит в том, что в качестве активной
вершины выбирается та из открытых, которая была посещена раньше других.
Именно эти обуславливается основное свойство поиска в ширину: чем ближе
вершина находится к источнику, тем раньше она будет посещена.
Основные свойства процедуры BFS:
• Процедура заканчивает работу после конечного числа шагов;
• В результате выполнения процедуры будут посещены все вершины из
компоненты связности, содержащей вершину – источник, и только
они;
• Время работы процедуры есть (), где m – число ребер в
компоненте связности, содержащей вершину – источник.
Применение алгоритма Форда–Фалкерсона к решению задачи
нахождения максимального потока
Алгоритм Форда-Фалкерсона заключается в итерационном построении
1.4.
максимального потока путем поиска на каждом шаге увеличивающей цепи, то
есть последовательности дуг, поток по которым можно увеличить. Данный
алгоритм применим к любой транспортной сети.
Приведем теоремы, используемые в качестве теоретической базы для
реализации алгоритма.
Теорема 1. Пусть µ – путь (цепь) из источника в сток. Если все дуги,
входящие в этот путь являются ненасыщенными, то поток (, ) , можно
увеличить, не нарушив при этом соотношения [13,14].
Действительно, если рассмотрим разности
(, ) = (, ) − (, ) > 0
(3)
25
и выберем среди них наименьшую *. При увеличении потока в каждой
дуге на величину * получим поток  +  ∗
(,  → )
–
символ,
обозначающий
совпадение
ориентации
дуги
с
направлением прохождения цепи;
(,   ) – символ, обозначающий противоположную ориентацию дуги по
отношению к направлению прохождения цепи;
Положим:
() = (,  → ) − (,  → )
(4)
разница между величиной пропускной способности и величиной потока;
 ∗ =  (,   )
(5)
минимальное значение потока среди обратных дуг;
∗ =  (,   )
(6)
минимальная разница между величиной пропускной способности и
величиной потока среди обратных дуг;
∗ = [ ∗,  ∗]
(7)
минимум из всех минимальных значений потока и разниц между величиной
пропускной способности и величиной потока среди обратных дуг.
Теорема 2: Если  ∗> 0, то увеличивая на * поток на каждой дуге (,  → ) и
уменьшая на * поток на каждой дуге  цепи µ, поток f так же увеличивается на
* [13,14].
Цепь, для которой  ∗= 0 называется насыщенной.
Теорема 3: Если не существует цепи µ из источника в сток с  ∗> 0, то
поток f нельзя больше увеличить, то есть он максимальный [13,14].
Алгоритм поиска ненасыщенных дуг и построения максимального потока
достаточно сложен. При вычитании из транспортной сети потока (, ), мы
получаем остаточную сеть. Множество вершин остаточной сети остается
прежним, а пропускные способности дуг изменяются по правилу
 (, ) = (, ) − (, )
(8)
26
Остаточная пропускная способность ребра  (, ) содержит величину, на
которую может быть увеличен поток по дуге, не превышая его общей пропускной
способности.
представляют
Остаточные
собой
ребра,
ребра
с
из
которых
неотрицательной
состоит
остаточная
остаточной
сеть,
пропускной
способностью. Множество остаточных ребер меняются следующим образом:
ребра, принадлежащие U такие, что
 (, ) = 0
(9)
более не принадлежат  .
Из вышесказанного Теорему 3 можно сформулировать иначе: поток (, )
максимален тогда и только тогда, когда в графе не существует более пути из
источника в сток.
Дуга (, ) транспортной сети является допустимой дугой из вершины u в v
относительно потока f , если
(, ) < (, )
(10)
Или
(, ) = 0
(11)
(, ) < (, )
(12)
Дуги, в которых
называются согласованными.
Дуги, в которых
(, ) = 0,
(13)
то есть те, которые входят в вершину u и по которым пропущен ненулевой
поток, называются несогласованными.
Увеличивающая цепь – последовательность всех попарно различных
между собой вершин и дуг
 = 0 , 1 = (0 , 1 ), 1 , 2 = (1 , 2 ), 2 , . . , −1 ,  = (−1 ,  ),  =  (14)
.
27
Для каждого  ≤  дуга  является допустимой дугой из −1 в 
относительно потока f. Если такая цепь найдена, то поток может быть увеличен на
минимальную величину из всех
(, ) = (, ) − (, ),
(15)
при условии, что все дуги в цепи согласованные. Этот же поток может
уменьшиться на минимальную величину из всех (, ) и (, ), когда хотя бы
одна дуга в цепи является несогласованной.
Эквивалентные
условия,
обязательные
для
завершения
построения
максимального потока:
На
•
поток из s в t максимален;
•
увеличивающей цепи для потока f не существует.
каждом
своем
шаге
алгоритм
Форда-Фалкерсона
добавляет
увеличивающий поток к потоку уже имеющемуся. Если за каждый шаг поток
будет увеличиваться как минимум на единицу, то алгоитм сойдется через ()
шагов, где  - максимальный поток в графе. Каждый шаг можно выполнить за
время (), где  – число ребер в графе. Таким образом общее время выполнения
алгоритма – ( ∗ ).
Применение алгоритма Дейкстры к решению задачи о нахождении
кратчайшего пути
Задача о «кратчайшем пути» состоит в нахождении кратчайшего пути от
1.5.
заданной начальной вершины s до заданной конечной вершины t, при условии,
что такой путь существует и все циклы в графе имеют неотрицательный
суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным
суммарным весом и х - некоторая его вершина, то, двигаясь от s к х, обходя этот
цикл достаточно большое число раз и попадая, наконец в t, получится путь со
сколь угодно малым весом. Таким образом, в этом случае кратчайшего пути не
существует. Так что неориентированные дуги (ребра) графа G не могут иметь
отрицательные веса [15].
28
Алгоритм Дейкстры решает задачу о кратчайшем пути между двумя
выделенными вершинами для взвешенного ориентированного графа G = (V, E) с
исходной вершиной s, в котором веса всех рёбер неотрицательны.
Формальное объяснение
В процессе работы алгоритма Дейкстры поддерживается множество S
V,
состоящее из вершин v, для которых δ(s, v) уже найдено. Алгоритм выбирает
вершину u
V\S с наименьшим d[u], добавляет u к множеству S и производит
релаксацию всех рёбер, выходящих из u, после чего цикл повторяется. Под
релаксацией
ребра
понимается
попытка
улучшить
текущее
значение
минимального пути в вершину b (d[b]) значением d[a]+ d[b]. Фактически это
значит, что мы пытаемся улучшить ответ для вершины b, пользуясь ребром (a,b) и
текущим ответом для вершины a [8] [16].
Не формальное объяснение
Каждой вершине из множества V сопоставим метку — минимальное
известное расстояние от этой вершины до s. Алгоритм работает пошагово — на
каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа
алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины s полагается равной 0, метки
остальных вершин — бесконечности. Это отражает то, что расстояния от s до
других вершин пока неизвестны. Все вершины графа помечаются как не
посещенные.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В
противном случае из еще не посещенных вершин выбирается вершина u,
имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в
которых u является
предпоследним
пунктом.
Вершины,
соединенные
с
вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа
рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра,
соединяющего u с этим соседом. Если полученная длина меньше метки соседа,
29
заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как
посещенную и повторим шаг.
Подробное математическое описание шагов алгоритма.
Каждой дуге (, ) исходного графа G поставим в соответствие число
(, ). Если в графе G отсутствует некоторая дуга (, ), положим (, ) = ∞.
Будем называть число (, ) длиной дуги (, ), хотя (, ) можно также
интерпретировать как соответствующие затраты или соответствующий весовой
коэффициент. Определим длину пути как сумму длин отдельных дуг,
составляющих этот путь.
Шаг 1. Перед началом выполнения алгоритма все вершины и дуги не
окрашены. Каждой вершине в ходе выполнения алгоритма присваивается число
(), равное длине кратчайшего пути из s в x, включающего только окрашенные
вершины.
Положить () = 0 и () = ∞ для всех x, отличных от s. Окрасить
вершину s и положить  =  (y – последняя из окрашенных вершин).
Шаг 2. Для каждой неокрашенной вершины x следующим образом
пересчитать величину ():
() = min{(), () + (, )}.
(16)
Если () = ∞ для всех неокрашенных вершин x, закончить процедуру
алгоритма: в исходном графе отсутствуют пути из вершины s в неокрашенные
вершины. В противном случае окрасить ту из вершин x, для которой величина
() является наименьшей. Кроме того, окрасить дугу, ведущую в выбранную на
данном шаге вершину x (для этой дуги достигался минимум в соответствии с
выражением (1)). Положить  = .
Шаг 3. Если  = , закончить процедуру: кратчайший путь из вершины s в
вершину t найден (это единственный путь из s в t, составленный из окрашенных
дуг). В противном случае перейти к шагу 2.
30
Отметим, что каждый раз, когда окрашивается некоторая вершина (не
считая вершины s), окрашивается и некоторая дуга, заходящая в эту вершину.
Таким образом, на любом этапе алгоритма в каждую вершину заходит не более
чем одна окрашенная дуга. Кроме того, окрашенные дуги не могут образовать в
исходном графе цикл, так как в алгоритме не может окрашиваться дуга, концевые
вершины которой уже окрашены. Следовательно, можно сделать вывод о том, что
окрашенные дуги образуют в исходном графе ориентированное дерево с корнем в
вершине s. Это дерево называется ориентированным деревом кратчайших путей.
Единственный путь от вершины s до любой вершины x, принадлежащей дереву
кратчайших путей, является кратчайшим путем между указанными вершинами. Т.
е. если кратчайшему пути из вершины s в вершину x в дереве кратчайших путей
принадлежит вершина y, то часть этого пути, заключенная между x и y, является
кратчайшим путем между этими вершинами [16].
Если бы мы хотели определить кратчайшие пути из вершины s во все
вершины исходного графа, то процедуру наращивания дерева следовало бы
продолжить до тех пор, пока все вершины графа не были бы включены в
ориентированное дерево кратчайших путей.
В случае когда для поиска вершины с минимальным весом просматривается
множество всех имеющихся вершин и для хранения значения минимальных весов
используется массив, время работы алгоритма – (2 ). Здесь основной цикл
выполняется около n раз и каждый раз на поиск минимума уходит n операций.
Так общее время работы алгоритма составляет (2 ).
1.6. Постановка задачи о назначениях
В общем виде задача о назначениях формулируется следующим образом:
Имеется некоторое число работ и некоторое число исполнителей. Любой из
исполнителей может быть назначен на выполнение любой, но только одной
работы. При этом эффективность работы и время, затрачиваемое на выполнение
31
исполнителем каждой работы различно. Необходимо распределить работы по
исполнителям таки образом, чтобы целевая функция была минимальной (в случае
минимизации затрачиваемого на выполнение работ времени) или максимальной
(в случае вычисления наибольшей эффективности).
Математическая постановка задачи. Введем несколько вспомогательных
определений.
Пусть имеются  работников,  должностей и мера стоимости работника 
на должности  равна  ≥ 0. Компоненты  образуют матрицу || ||, будем
называть ее матрицей распределения[17].
Булева матрица || || размера  ×  такая, что
,
∑  ≤ 1
(17)
=1,=1
называется матрицей назначения.
Если


∑ ∑  = min(, ) ,
(18)
=1 =1
то матрица назначения называется насыщенной.
Используя
выше
обозначенные
термины,
сформулируем
задачу
о
назначениях.
Дана
матрица
распределения
|| ||.
Необходимо
найти
для
нее
насыщенную матрицу назначения || ||, для которой


∑ ∑  
=1 =1
(19)
32
минимальна.
Различают открытую и закрытую задачу о назначениях. Закрытой
задачей о назначениях называют случай, когда число исполнителей равно числу
работ. Если исполнителей больше, чем работ или, наоборот, работ больше, чем
исполнителей, задачу называют открытой [18].
Предположим, что некоторое предприятие располагает тремя рабочими
станками. Так же есть три участка, на которых могут работать эти станки. При
этом каждый из станков потребляет различное количество электроэнергии при
работе на каждом из участков. Решение задачи будет сводиться к распределению
станков по участкам, причем такое, что суммарные траты на электроэнергию
будут минимальны.
Метод решения закрытой и открытой задач не сильно разнится. В случае
открытой задачи, например, когда число станков превосходит число рабочих
участков, некоторой машине назначается дополнительный участок с ценой 0.
Таким образом, сравняется количество станков и участков. После этого задача
решается
тем же способом, что и закрытая. Аналогично можно поступить в
случае, когда число участков превышает число станков. Так же можно поставить
задачу не на минимизацию расходов, а на максимизацию продуктивности.
Для того чтобы решить задачу на максимум исходную матрицу
необходимо несколько видоизменить:
1. Среди всех элементов матрицы находится максимальный элемент.
2. Составляется новая матрица, элементы которой представляют собой
разность найденного максимального элемента и элементов исходной
матрицы
Далее задача решается аналогично задаче на нахождение минимума. Очень
важно не переписывать исходную матрицу, а создать новую с элементамиразностями, так как при нахождении значения целевой функции должны
учитываться
пользователем.
значения
исходной,
неизмененной
матрицы,
заданной
33
1.7.
Применение Венгерского алгоритма для решения задачи о назначениях
Наиболее эффективным способом решения задачи о назначениях является
Венгерский алгоритм. Основная идея
этого
алгоритма заключается в
осуществлении перехода от исходной матрицы распределений к равносильной ей
матрице с нулевыми или положительными элементами и системой независимых
нулей. Особенность системы независимых нулей в том, что никакие два случайно
взятых нуля их этой системы не принадлежат одному и тому же столбцу или
строке [19].
Алгоритм строится итерационно. На каждой итерации происходит попытка
увеличить количество нулей хотя бы на один. Происходит это путем вычитания
из всех элементов таблицы одного минимального элемента. Процесс происходит
до тех пор, пока значение целевой функции не станет нулевым, а значит
оптимальным.
Основная сложность реализации алгоритма состоит в «запоминании»
номеров столбцов и строк, формирующих оптимальное решение таким образом,
чтобы их можно было сравнивать с другими найденными решениями.
Поэтапное описание Венгерского алгоритма. Данный алгоритм состоит
из трех этапов
Первый этап:
1. В каждой строке находится минимальный элемент. Этот элемент
вычитается из всех элементов данной строки. Таким образом в каждой
строке появляется минимум один нуль.
2. В каждом столбце находится минимальный элемент и так же вычитается из
всех элементов данного столбца.
Второй этап:
1. Допустимым будет являться решение, при котором каждой строке и
каждому столбцу будет соответствовать только один элемент. Элементы
34
помещаются в клетки с нулевой стоимостью, именно это приводит к
получению решения с минимальным значением искомой целевой функции.
2. На данном этапе необходимо выделить нулевые элементы таким образом,
чтобы в каждой строке и каждом столбце было по одному такому элементу.
Если это сделать невозможно, следует перейти к этапу 3.
Третий этап:
1. Проводится минимальное число прямых линий через строки и столбцы,
содержащие нулевые элементы. Проще говоря, необходимо вычеркнуть
все нули в таблицы минимальным количеством прямых.
2. Среди не вычеркнутых элементов находится самый минимальный
элемент
3. Найденное значение вычитается из всех элементов, через которые не
проходят прямые. Таким образом среди не вычеркнутых элементов
появляются один или несколько нулей.
4. Это же значение прибавляется ко всем элементам таблицы, которые
располагаются на пересечении прямых линий.
5. Оставшиеся вычеркнутые элементы не подвергаются изменениям.
6. Следом вернуться к этапу 2.
Возврат к этапу 2 и повторение этапа 3 повторяется до тех пор, пока не
будет достигнуто оптимальное решение. Идея Венгерского метода заключается в
том, чтобы продолжать процесс приведения матрицы до тех пор, пока все
распределяемые единицы не попадут в клетки с нулевой стоимостью. Таким
образом значение приведенной целевой функции становится равным нулю [19].
Временная сложность алгоритма составляет (4 ).
35
ГЛАВА 2. РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
Рассмотрим
программное
обеспечение,
разработанное
в
связи
с
поставленными задачами.
Для
реализации
программного
используется
современный
высокоуровневый язык программирования общего назначения Python [20].
Помимо стандартной, достаточно богатой библиотеки языка Python для
реализации ПО, была использована библиотека Graphviz, предназначенная для
непосредственной визуализации графов [21]. Данная библиотека достаточно
проста в использовании. Она позволяет быстро и эффективно построить графы
различной размерности, путем создания необходимого количества вершин(Node)
и последовательного соединения их между собой ребрами графа(Edge).
Пользовательский интерфейс программного обеспечения был реализован с
помощью мощного инструментария для разработки GUI приложений – PyQt4
[22]. Он представляет собой смесь Python и кроссплатформенной библиотеки для
разработки ПО – Qt. PyQt4 располагает более 600 классов и 6000 функций и
методов. Особый интерес в этой работе представляет существующий в PyQt4
набор виджетов графического интерфейса [23].
2.1. Программная реализация алгоритма Форда – Фалкерсона
Программный код реализован в двух исходных файлах:
❖ maxflow.py – исходный файл с полной математической реализацией
алгоритма. При вызове данного файла производятся подсчеты,
основанные
на
алгоритме
Форда-Фалкерсона,
и
отрисовка
построенной транспортной сети;
❖ window.py
–
исходный
файл
с
описанием
пользовательского
интерфейса. Здесь реализованы все функции для взаимодействия с
кнопками и главным окном приложения;
36
Рассмотрим программный код каждого из этих скриптов более подробно,
опираясь на листинги.
2.1.1. Описание программного обеспечения, реализованного с помощью
языка Python. Содержимое исполняемого файла «maxflow.py»
В первых строках кода подключаются модули, необходимые для работы
(Листинг 1).
import Queue
import graphviz as gv
import sys
import os
Листинг. 1. Подключение необходимых модулей
Queue – класс для организации очереди.
Graphviz – библиотека для визуализации графов.
Sys – библиотека для работы с интерпретатором.
Os – библиотека для работы с ОС.
Входные
данные,
задаваемые
пользователем:
матрица
пропускных
способностей всех дуг графа – С. Матрицу получаем из файла matrix_C.txt
(Листинг 2).
l = []
for line in open( 'matrix_C.txt' ):
l.append( [ int(x) for x in line.split() ] )
C = list( l )
Листинг 2. Входные данные
В этих строках кода осуществляются построчные итерации по файлу
исходной матрицы. Каждый следующий элемент добавляется в конец списка l.
Далее на основе этого списка формируется матрица C.
37
Основные переменные, с которыми работает программа, представлены в
Листинге 3.
n=len(C)
F=[[0]*n for i in range(n)]
CF=[[0]*n for i in range(n)]
Cut=[[0] for i in range(n)]
P=[[0] for i in range(n)]
for i in range(n):
for j in range(n):
CF[i][j]=C[i][j]-F[i][j]
s=0
t=n-1
u=0
Листинг 3. Основные переменные
n-размерность графа;
F-матрица значений потока;
CF-матрица разности C-F;
Cut-отметки о посещении вершин. Если значение “1”-вершины была
посещена;
P-массив предков. Элемент P[i]-номер вершины, из которой попали в i;
s-вершина-источник;
t-вершина-сток;
u-вспомогательная переменная.
Основную работу в данном программном годе выполняют функции bfs и
maxflow. Именно в них происходит процесс определения существования цепочки
из источника в сток, состоящей из ненасыщенных дуг и последующее увеличение
максимального потока по найденным цепочкам.
38
Рассмотрим более подробно функцию bfs (Листинг 4).
def bfs(s,t):
Cut=[[0] for i in range(n)]
P=[[0] for i in range(n)]
q=Queue.LifoQueue()
q.put(s)
while q.empty()!=True:
u=q.get()
for i in range(1,n):
if CF[u][i]!=0 and Cut[i]!=1:
q.put(i)
Cut[i]=1
P[i]=u
return P
Листинг 4. Функция bfs(breadth-first search)
Функция bfs(breadth-first search) осуществляет обход графа в ширину.
Алгоритм обхода графа в ширину заключается в последовательном просмотре
отдельных «уровней» графа, начиная с вершины-источника. Вначале посещается
источник, затем произвольная вершина, в которую можно попасть из источника,
затем – все потомки данной вершины, далее-все потомки потомков и т.д. Обход
графа завершается при достижении нужной вершины, в данном случае - при
достижении вершины-стока.
На практике для реализации этого алгоритма удобнее всего использовать
очередь, где будет храниться множество открытых вершин. Когда новая вершина
становится открытой, она добавляется в конец очереди, а активная выбирается в
ее начале.
Для этого создается очередь q, организованная по принципу «последний
зашел - первый вышел». Это означает, что элементы будут извлекаться из очереди
39
в порядке, обратном порядку их попадания в нее. Начиная с вершины-источника
и заканчивая вершиной-стоком, в цикле просматриваются все вершины графа. В
цикле проверяются следующие условия:
- Отлично ли от нуля значение элемента из матрицы CF?(Можно ли
пропустить по дуге ненулевой поток?)
- Равно ли единице значение элемента из массива Cut?(Была ли посещена
ранее данная вершина?)
Если оба условия выполняются, то рассматриваемая вершина помещается в
очередь q, соответствующему элементу массива Cut присваивается значение
единицы (вершина посещена), а в массив P заносится номер предка посещенной
вершины.
Функция bfs возвращает массив предков, по которому в дальнейшем будет
восстановлена цепочка ненасыщенных дуг из вершины источника в вершинусток.
Вторая функция maxflow берет на себя задачу непосредственного
увеличения потока. Рассмотрим ее более подробно (Листинг 5).
def maxflow(s,t):
flow=0
F=[[0]*n for i in range(n)]
for i in range(n):
for j in range(n):
CF[i][j]=C[i][j]
PP=bfs(s,t)
while PP[t]!=[0]:
u=t
cmin=1000000
while u!=s:
i=PP[u]
if CF[i][u]<cmin:
cmin=CF[i][u]
40
u=PP[u]
u=t
while u!=s:
i=PP[u]
F[i][u]+=cmin
CF[i][u]=C[i][u]-F[i][u]
u=PP[u]
flow=0
for i in range(n):
flow+=F[i][t]
PP=bfs(s,t)
return flow
Листинг 5 функция maxflow
Функция maxflow восстанавливает цепочку из вершины - источника в
вершину – сток, на основе данных, переданных от функции bfs, находит
минимальный поток, который можно пропустить по этой цепочке(cmin) и
увеличивает значение общего потока(flow). Восстановление цепочки происходит с
конца графа, т.е. с вершины-стока. Просматриваются все вершины, занесенные в
массив P, начиная с последней:
- Если значение потока, который можно пропустить по данной дуге
наименьшее, то значение потока передается переменной cmin.
- Далее значение потока F на каждой дуге, входящей в цепочку
увеличивается на cmin.
Функция maxflow подсчитывает значение максимального потока сети и
возвращает его в качестве результата работы.
На данном этапе следует позаботиться о сохранении результатов, для
дальнейшей их демонстрации пользователю.
В качестве конечного продукта
работы программы будут выступать следующие данные:
41
❖ Матрица F, содержащая значение потока, пропущенного по каждой из
дуг;
❖ Само значение максимального потока, полученное из переменной
flow;
❖ Изображение конечного графа, с указанием насыщенных дуг
Вся эта информация будет предоставлена пользователю, в случае
корректной работы исходного кода. Однако, могут возникнуть ситуации, в
которых по тем или иным причинам максимальных поток посчитан не будет.
Чаще всего это может произойти из-за некорректно введенных пользователем
данных. В этом случае должно выводиться сообщение об ошибке (Листинг 6).
if flow==0:
file_maxflow=open('MaxFlow.txt','w')
file_maxflow.write("Error")
file_maxflow.close()
Листинг 6. Сообщение об ошибке
MaxFlow.txt – файл для записи значения максимального потока. Если
максимальный поток flow равен нулю, то в данный файл вместо значения потока
записывается сообщение об ошибке «Error». В дальнейшем это сообщение будет
выводиться пользователю на экран, вместе с рекомендациями о замене входных
данных.
В случае, если данные пользователем были введены корректно и
максимальный поток найден, конечные результаты работы ПО так же
записываются в файл(Листинг 7).
else:
file_F=open('matrix_F.txt', 'w')
for i in range(n):
for j in range(n):
file_F.write(str(F[i][j]) + " ")
file_F.write("\n")
42
file_F.close()
file_maxflow=open('MaxFlow.txt','w')
file_maxflow.write(str(flow))
file_maxflow.close()
Листинг 7. Запись результатов в файл
matrix_F.txt – файл для записи конечной матрицы F со значением потока,
пропущенного по каждой из дуг графа. В файл записывается каждый элемент из
матрицы F.
В файл MaxFlow.txt на этот раз заносится значение найденного
максимального потока.
После того как максимальный поток найден и задача решена, необходимо
продемонстрировать результаты проделанной работы. Для этого используются
методы библиотеки graphviz. Данная библиотека позволяет достаточно просто
визуализировать как обычные графы (Graph), так и ориентированные (Digraph) и
сохранять их в виде изображения в различных форматах(ipg, png, pdf, svg e.t.c.)
Ниже представлен исходный код, являющийся частью функции maxflow и
отвечающий за непосредственную визуализацию графа. Разберем его подробно.
Нас интересует изображение исходной сети и конечный результат решения
задачи, поэтому будем рисовать два графа (Листинг 8).
digraph=gv.Digraph(format='png')
maxdigraph=gv.Digraph(format='png')
digraph.body.extend(['rankdir=LR'])
maxdigraph.body.extend(['rankdir=LR'])
Листинг 8. Определение графов
digraph - исходный ориентированный граф, заданный пользователем;
maxdigraph - нагруженный ориентированный граф, с пропущенным по нему
максимальным потоком, т.е. результат решения задачи;
43
rankdir=LR - расположение графа слева направо(Left-Right).
Библиотека Graphviz создает графы по следующему принципу:
- Создаются вершины (узлы) графа (Листинг 9, Листинг 10);
-
Вершины
соединяются
между
собой
дугами
(ребрами)
и
при
необходимости помечаются надписями (метками) (Листинг 11).
for i in range(n):
digraph.node=(i)
maxdigraph.node=(i)
Листинг 9. Создание вершин графа
Node - вершины графа, впоследствии соединенные дугами. Создаем n
вершин.
for i in range(n):
for j in range(n):
A=str(i)
B=str(j)
Листинг 10. Введение условных обозначений вершин
A, B – условное обозначение двух вершин, между которыми будут
отрисовываться дуги. str(i), str(j) – будущие названия узлов графа.
Далее в цикле происходит построение сразу двух графов (Листинг 11):
if C[i][j]!=0:
L='0('+str(C[i][j])+')'
digraph.edge(A,B, label=L)
if F[i][j]!=[0] and F[i][j]==C[i][j]:
L=str(F[i][j])+'('+str(C[i][j])+')'
maxdigraph.edge(A,B, color="red", label=L)
elif F[i][j]>0:
L=str(F[i][j])+'('+str(C[i][j])+')'
44
maxdigraph.edge(A,B, color="green",label=L)
else:
L='0('+str(C[i][j])+')'
maxdigraph.edge(A,B, label=L)
Листинг 11. Создание ребер графов
digraph формируется по всем ненулевым значениям матрицы пропускных
способностей C;
edge - дуга(стрелка), связывающая вершины A и B между собой;
label=L – метка (подпись) над дугой графа. В данном случае отображает
данные из матрицы C.
Для графа maxdigraph определены три типа дуг:
- нагруженные. Те, в которых величина пропущенного потока совпадает со
значением величины пропускной способности дуги(F=C). будут в дальнейшем
обозначены красным цветом(color=”red”);
- посещенные. Те, через которые был пропущен поток, но он не превышает
максимального значения пропускной способности дуги(F<C), обозначены
зеленым цветом(color=”green”);
- не посещенные. Те, через которые был пропущен нулевой поток(F=0), по
умолчанию будут черного цвета.
Затем необходимо вывести оба графа на печать (Листинг 12).
print(digraph.source)
print(maxdigraph.source)
digraph.render('PNG/digraph')
maxdigraph.render('PNG/maxdigraph')
Листинг 12. Вывод графов на печать.
Source и render отвечают за обработку/печать графов и помещение их в
файл-изображение с соответствующим именем (Рис. 1).
45
Рисунок 1. Содержимое папки PNG
Так как вызов функции bfs, восстановление цепи, увеличение потока
и создание и отрисовка графов происходят в функции maxflow, то в конечном
счете остается лишь присвоить результат работы данной функции какой-либо
переменной и вывести его на печать (Листинг 13).
maxf=maxflow(s,t)
print "maxflow=", maxf
Листинг 13. Вывод результата
В терминал выводится результат работы функции maxflow, т.е. значение
максимального потока данной сети. Изображения графов сохраняются в виде
изображений “digraph.png” и
“maxdigraph.png” и располагаются в той же
директории, в которой находится исходный код.
46
2.1.2. Описание программного обеспечения, реализующего интерфейс для
пользователя. Содержимое исполняемого файла «window.py»
PyQt4 - это набор Python библиотек для создания графического интерфейса.
PyQt4 реализован в виде набора python-модулей. Именно с подключения
необходимых модулей мы начнем описание программного обеспечения (Листинг
14).
import sys
import os
from PyQt4.QtCore import *
from PyQt4.QtGui import *
from PyQt4 import *
Листинг 14. Подключение необходимых модулей
Sys – библиотека для работы с интерпретатором;
Os – библиотека для работы с ОС;
PyQt4.QtCore – графическая библиотека;
PyQt4.Qt.Gui – дополняет QtCore функциональностью GUI – графический
интерфейс.
Каждое приложение PyQt4 должно создать объект приложения – экземпляр
QApplication()(Листинг 15).
a=QApplication(sys.argv)
Листинг 15. Создание объекта приложения
Класс QApplication() руководит управляющей логикой GUI и основными
настройками. Он содержит основной цикл событий, в котором все события от
оконной системы и других источников обрабатываются и координируются. Он
также обрабатывает инициализацию и завершение приложения. Параметр
sys.argv – это список аргументов командной строки. Скрипты Python можно
запускать из командной строки. Это способ, которым мы можем контролировать
запуск наших сценариев.
47
Далее следует определить главное окно приложения и его основные
параметры. Для этого необходимо создать объект класса QWidget() (Листинг 16).
window=QWidget()
window.move(20,10)
window.setWindowTitle("Graph")
Листинг 16. Определение главного окна
QWidget() – это базовый класс для всех объектов пользовательского
интерфейса в PyQt4. Виджет - это элементарный объект пользовательского
интерфейса, который получает события мыши, клавиатуры и другие события от
оконной системы и рисует свое изображение на экране. Каждый виджет имеет
прямоугольную форму. Мы предоставляем конструктор по умолчанию для
QWidget(). Конструктор по умолчанию не имеет родителя. Виджет, не встроенный
в родительский виджет, то есть, виджет без родителей, называется окном.
Метод move() двигает виджет на экране на координату (x,y), в нашем случае:
x=20, y=10 (Рис. 2).
Рисунок 2. Главное окно window
48
Обычно окно имеет рамку и полосу с заголовком. Заголовок задается
свойством setWindowTitle(). Когда мы запустим приложение, в полосе заголовка
главного окна появится надпись "Graph" (Рис. 2).
В верхней части окна приложения будет располагаться панель
инструментов, с кнопками «Открыть» и «Сохранить как».
Основная цель панели инструментов — предоставить пользователю
быстрый доступ к командам программы одним нажатием кнопки мыши. Это
делает панель инструментов более удобной по сравнению с меню, в котором
нужно сделать, по меньшей мере, два нажатия. Еще одно достоинство состоит в
том, что панель инструментов всегда видима, и не нужно тратить время на
поиски необходимой команды в меню или вспоминать комбинацию клавиш
ускорителя.
Панель инструментов представляет собой область, в которой
расположены кнопки, дублирующие часто используемые команды меню. Эта
панель в PyQt4 создается при помощи класса QToolBar() (Листинг 17).
toolbar=QToolBar(window)
size=QSize(40,40)
toolbar.setIconSize(size)
Листинг 17. Создание панели QToolBar
Создаем объект класса, принадлежащий главному окну window. Size –
объект класса QSize(), определяющий размер двумерного объекта. Свойство
setIconSize() определяет размер значков на панели инструментов в главном окне.
В дальнейшем на область главного окна будут помещены и другие
элементы. Для свободного доступа к ним из различных функции, определим их
заранее (Листинг 18).
label_result=QLabel(u'Матрица максимального потока:')
label_maxflow=QLabel()
table=QTableWidget()
49
button_count_up = QPushButton("Count up")
Листинг 18. Определение основных элементов главного окна
Виджет QLabel() позволяет отображать текст или рисунок. Мы будем
использовать его объекты для помещения на экран сообщений для пользователя.
label_result будет отображать текст «Матрица максимального потока» по
завершении подсчетов.
label_maxflow пока останется пустой. В дальнейшем в нее будет передано
значение максимального потока.
Класс QTableWidget() является сеткой, представляющей собой двумерный
разряженный массив. На нем отображается часть ячеек всей сетки, полученная
при прокрутке изображения пользователем. В объект table будет помещаться
исходная и конечная матрицы.
Виджет QPushButton() представляет собой командную кнопку. Кнопка, или
командная кнопка, является наиболее часто используемым виджетом в любом
графическом пользовательском интерфейсе.
Нажатие (щелчок) кнопки указывает компьютеру, что необходимо
выполнить действие или ответить на вопрос. Командная кнопка, обычно,
прямоугольна и отображает текстовый ярлык описывающий ее действие. В
данном случае создаем кнопку button_count_up, при нажатии на которую в
дальнейшем будет отсылаться сигнал приложению о необходимости произвести
расчеты.
Теперь вернемся к описанию объектов QToolBar().
В приложениях множество общих команд может быть вызвано через
панель инструментов и сочетания клавиш. Поскольку пользователь ожидает, что
каждая команда будет выполняться одним и тем же способом, независимо от
используемого пользовательского интерфейса, то полезно представить каждую
команду как действие.
50
Класс QAction() предоставляет абстрактное действие пользовательского
интерфейса, которое может быть вставлено в виджеты. Рассмотрим создание
такого объекта на примере действия «Open» («Открыть») (Листинг 19).
openFile=QAction(QIcon('ICON/open_icon.jpg'), 'Open,Ctrl+O ', window)
openFile.setShortcut('Ctrl+O')
openFile.triggered.connect(OpenDialog)
toolbar.addAction(openFile)
Листинг 19. Создание действия «Открыть»
В конструкторе объекта openFile класса QAction() объявляем пиктограмму и
всплывающую
подсказку.
Путь
к
пиктограмме
–
'ICON/open_icon.jpg'.
Всплывающая подсказка представляет собой название действия и комбинацию
горячих клавиш для него.
Свойство
setShortcut()
определяет
комбинацию
горячих
клавиш
действия(Ctrl+O).
Действие необходимо соединить сигналом с функцией, описывающей это
действие. Сигнал посылается, когда действие активируется пользователем:
например, когда пользователь щёлкает по кнопке панели инструментов или
нажимает комбинацию горячих клавиш действия. В данном случае при активации
действия будет вызываться функция OpenDialog.
Для того чтобы поместить кнопку на панель инструментов вызываем метод
addAction(). Он добавит действие в список действий этого виджета (Рис 3).
Рисунок 3. Действие «Открыть»
51
Аналогичным образом объявим действие «Save as» («Сохранить как»)
(Листинг 20) (Рис 4.).
save_asFile=QAction(QIcon('ICON/save_as_icon.jpg'), 'Save, Ctrl+S', window)
save_asFile.setShortcut('Ctrl+S')
save_asFile.triggered.connect(SaveAsDialog)
toolbar.addAction(save_asFile)
Листинг 20. Создание действия «Сохранить как»
Рисунок 4. Действие «Сохранить»
Опишем функции, к которым обращаются действия в панели инструментов.
Начнем с функции «OpenDialog()»(Листинг 21).
def OpenDialog():
file_name = QFileDialog.getOpenFileName(window,'Open file', '/home')
Листинг 21. Объявление функции «OpenDialog()»
Функция OpenDialog() будет отвечать за открытие файлов с исходными
данными для решения задачи.
file_name – объект класса QFileDialog(), который предназначен для выбора
одного или нескольких файлов и включающий в себя такие возможности, как
переименование файлов и создание директорий.
Класс QFileDialog() предоставляет реализацию диалогового окна выбора
файлов и отвечает за создание и работоспособность сразу трех диалоговых окон.
Одно из них позволяет осуществлять выбор файла для открытия, второе –
предназначено для выбора пути и имени файла для его сохранения, а третье —
предназначено для выбора директории.
52
Один из методов данного класса – getOpenFileName(), создает диалоговое
окно для выбора одного файла. Этот метод не открывает файлы, а только
открывает диалоговое окно и возвращает имя файла. В скобках указано название
окна('Open file') и директория, которая откроется по умолчанию('/home') (Рис. 5).
Рисунок 5. Диалоговое окно «Open file» для выбора файла
Далее, в Листинге 22 представлена уже знакомая часть программного кода,
необходимая для открытия выбранного файла и сбора данных из него для
предоставления пользователю.
l = [] #список для хранения текста
for line in open(file_name):
l.append( [ int(x) for x in line.split() ] )
C = list( l )
print C
n=len(C)
Листинг 22. Сбор данных из файла
53
Теперь у нас есть входные данные, полученные из загруженного файла –
исходная матрица и ее размерность. Можно приступать к помещению этих
данных на экран (Листинг 23).
table.setColumnCount(n)
table.setRowCount(n)
for i in range(n):
for j in range(n):
item=QTableWidgetItem(str(C[i][j]))
table.setItem(i,j,item)
table.resizeColumnsToContents()
table.resizeRowsToContents()
Листинг 23. Создание таблицы на основе входных данных
Свойство setColumnCount() определяет количество столбцов в таблице, а
свойство setRowCount() – количество строк.
С помощью QTableWidgetItem() формируем элемент таблицы из элемента
матрицы C. setItem() устанавливает в i-тую строку и j-тый столбец элемент,
сформированный с помощью QTableWidgetItem().
Для того чтобы подогнать ширину колонки под данные QTableWidget()
используются слоты resizeColumnsToContents() и resizeRowsToContents(), который
изменяют размер столбца и строки соответственно.
Так как теперь изменилось содержимое главного окна, следует изменить и
его размеры (Листинг 24).
new_size_h=table.verticalHeader().width() +
table.horizontalHeader().length()+25
new_size_v=table.verticalHeader().length()+200
window.resize(new_size_h, new_size_v)
Листинг 24. Изменение размера виджета
54
new_size_h – новый размер по – горизонтали. Складываются из
–
verticalHeader().width()
ширины
вертикального
заголовка,
horizontalHeader().length() – длины горизонтального заголовка + 25 пикселей,
оставленные на рамку главного виджета.
new_size_v
–
новый
размер
по
–
вертикали.
Складывается
из
verticalHeader().length() – длины вертикального заголовка + 200 пикселей,
оставленные на рамку главного виджета и остальные элементы главного окна.
Метод resize() изменяет размеры главного окна на новые. (Рис. 6)
Рисунок 6. Расчет новых размеров виджета
Осталось лишь поместить таблицу на экран(Листинг 25).
vbox.addWidget(table)
vbox.addWidget(button_count_up)
Листинг 25. Размещение элементов
Метод addWidget() добавляет элементы на вертикальный компановщик.
Помимо таблицы добавляем так же кнопку «Count up» (Рис. 7).
55
Рисунок 7. Кнопка «Count up»
Теперь опишем функцию SaveAsDialog() (Листинг 26).
def SaveAsDialog():
file_name=QFileDialog.getSaveFileName(window,'Save as file', '/home', filter
= "txt (*.txt)")
Листинг 26. Объявление функции «SaveAsDialog()»
Функция SaveAsDialog() будет отвечать за сохранение исходной таблицы,
введенной пользователем, для ее дальнейшего использования.
Метод
getSaveFileName()
класса
QFileDialog()
создает
стандартное
диалоговое окно, которое позволяет пользователю определить диск, каталог и имя
файла, которое нужно сохранить. В скобках указывается родительский виджет,
название диалогового окна (‘Save as file’), директория, которая открывается для
сохранения по умолчанию (‘/home’) и формат, в котором будут сохраняться
файлы по умолчанию(“*.txt”) (Рис. 8).
56
Рисунок 8. Диалоговое окно «Save as file» для сохранения файла
Рассмотрим часть программного кода, отвечающую за запись информации
из таблицы в файл(Листинг 27).
new_file=open(file_name, 'w') #открыть файл на запись
for i in range(table.columnCount()): #число столбцов
for j in range(table.rowCount()): #число строк
item=str(table.item(i, j).text()) #переменная со значением из таблицы.
из i-той строки и j-того столбца
new_file.write(item + " ") #записать в файл значение+пробел
new_file.write("\n") #записать в файл код перевода строки
new_file.close() #закрыть файл
Листинг 27. Запись информации в файл
57
Функцией open() открываем файл на запись(‘w’). Двигаясь по каждой из
ячеек таблицы, извлекаем их содержимое с помощью item(i, j).text(). С помощью
write() записываем в файл значение из таблицы. Элементы таблицы отделяются
друг от друга пробелами (“ ”), строки – кодом перевода строки (“\n”). close()
закрывает файл.
Определим еще несколько объектов главного окна, которые будет
использовать пользователь в процессе работы с приложением (Листинг 28).
vbox=QVBoxLayout()
window.setLayout(vbox)
vbox.addWidget(toolbar)
label=QLabel(u"Введите количество вершин графа°")
vbox.addWidget(label)
hbox=QHBoxLayout()
vbox.addLayout(hbox)
spinbox=QSpinBox(parent=window)
hbox.addWidget(spinbox)
button_ok=QPushButton("OK")
hbox.addWidget(button_ok)
Листинг 28. Определение элементов главного окна
Класс
QVBoxLayout()
–
компановщик,
выстраивающий
виджеты
в
вертикальную линию. Данный класс используется для создания вертикального
ряда из выравниваемых объектов.
setLayout() устанавливает vbox в качестве менеджера компоновки данного
виджета.
58
Создаем метку – подсказку для пользователя «Введите количество вершин
графа».
Spinbox – объект класса QSpinBox(), представляет собой виджет счетчика.
QSpinBox() позволяет пользователю указать значение щелкая мышью по кнопкам
вверх/вниз
или
нажимая
клавиши
клавиатуры
вверх/вниз
для
увеличения/уменьшения значения, отображенного в настоящий момент. Также
пользователь может ввести значение вручную. Этот элемент необходим для того,
чтобы
пользователь
мог
самостоятельно
ввести
количество
вершин
предполагаемого графа, для дальнейшего создания таблицы ввода данных в
матрицу С.
button_ok – кнопка «OK». Ее функция будет описана ниже.
QHBoxLayout() аналогично QVBoxLayout() структурирует виджеты в одну
линию. Отличие состоит лишь в том, что QHBoxLayout() выстраивает их по
горизонтали.
addLayout() позволяет добавить один компановщик внутрь другого. Это
необходимо для более комфортного расположения виджетов в главном окне.
addWidget() добавляет элементы на компановщик.
Панель управления (toolbar) и метка – подсказка (label) будут располагаться
на вертикальном компановщике (vbox), а виджет счетчика (spinbox) и кнопка
button_ok – на горизонтальном (hbox) (Рис. 9).
Рисунок 9. Размещение элементов на компановщике
Осталось определить функции для объявленных ранее кнопок. Начнем с
кнопки button_ok (Листинг 29).
59
def OK():
label_result.hide()
label_maxflow.hide()
n=spinbox.value()
table.setColumnCount(n)
table.setRowCount(n)
for i in range(n):
for j in range(n):
item=QTableWidgetItem("0") #элемент для таблицы- "0"
table.setItem(i,j,item) #в ячейку i j поместить значение
table.resizeColumnsToContents() #подогнать размер столбца под значение
table.resizeRowsToContents() #подогнать размер строки под значение
Листинг 29. Функция OK()
Вызов функции OK будет запускать создание матрицы на основе данных,
полученных из spinbox.
Для начала с помощью hide() скроем объекты, которые не понадобятся на
данном этапе (label_result и label_maxflow).
value() позволяет извлечь значение, введенное пользователем из spinbox. На
основе этих данных формируем таблицу из n столбцов и строк и заполняем
каждую из ячеек значением по умолчанию (“0”). Далее подгоняем размеры
таблицы под содержимое.
Так же не забываем про изменение размеров самого главного окна, с учетом
всех располагающихся на нем элементов (Листинг 30).
new_size_h=table.verticalHeader().width() +
table.horizontalHeader().length()+25
new_size_v=table.verticalHeader().length()+200
window.resize(new_size_h, new_size_v)
Листинг 30. Изменение размеров главного окна
60
Делаем таблицу видимой для пользователя, помещая ее на вертикальный
компановщик (Листинг 31).
vbox.addWidget(table)
vbox.addWidget(button_count_up)
Листинг 31. Размещение объектов
Теперь пользователь видит таблицу n×n, заполненную нулями. Он может
изменять значения внутри ячеек и создавать тем самым свою матрицу входных
данных C.
После ввода данных пользователю предлагается нажать кнопку «Count up».
Рассмотри функцию, связанную с этой кнопкой (Листинг 32).
def COUNT_UP():
new_file=open('matrix_C.txt', 'w')
for i in range(table.columnCount()):
for j in range(table.rowCount()):
item=str(table.item(i, j).text())
new_file.write(item + " ")
new_file.write("\n")
new_file.close()
os.system('python maxflow.py')
Листинг 32. Функция COUNT_UP()
Функция COUNT_UP() будет отсылать сигнал к запуску скрипта maxflow.py,
осуществляющего основные расчеты по алгоритму.
Функция формирует файл 'matrix_C.txt', в который передается введенная
пользователем матрица входных данных C.
os.system исполняет системную команду. В данном случае запускает скрипт
maxflow.py.
Как описывалось ранее, по завершении подсчетов в скрипте maxflow.py
происходит создание файлов, хранящих матрицу и значение максимального
61
потока. Следует извлечь эти данные из файлов, для дальнейшей демонстрации их
пользователю.
Сначала рассмотрим случай некорректного ввода данных пользователем
(Листинг 33).
file_maxflow = open('MaxFlow.txt','r')
if file_maxflow.read()=="Error":
table.hide()
button_count_up.hide()
label_maxflow.setText(u'Error: Максимальный поток не найден.
Проверьте корректность исходных данных)
vbox.addWidget(label_maxflow)
label_maxflow.show()
Листинг 33. Сообщение об ошибке
Открывается файл 'MaxFlow.txt' на чтение ('r') и функцией read()
извлекается информация из него. Если в файл записано слово "Error"("Ошибка"),
то таблица и кнопка «Count up» остаются скрытыми. Пользователю на экран
выдается сообщение с текстом «Максимальный поток не найден. Проверьте
корректность исходных данных» (Рис. 10).
62
Рисунок 10. Вывод сообщения об ошибке
В случае, если в файле 'MaxFlow.txt' находится другая информация,
пользователь получает доступ к результатам работы ПО (Листинг 34).
else:
vbox.addWidget(label_result)
label_result.show()
file_F = open('matrix_F.txt','r')
l = []
for line in (file_F):
l.append( [ int(x) for x in line.split() ] )
C = list( l )
n=len(C)
table.setColumnCount(n)
table.setRowCount(n)
for i in range(n):
for j in range(n):
item=QTableWidgetItem(str(C[i][j]))
table.setItem(i,j,item)
table.resizeColumnsToContents()
63
table.resizeRowsToContents()
new_size_h=table.verticalHeader().width() +
table.horizontalHeader().length()+25
new_size_v=table.verticalHeader().length()+250
window.resize(new_size_h, new_size_v)
vbox.addWidget(table)
Листинг 34. Печать результатов из файла 'matrix_F.txt'
На экран выводится метка с текстом «Матрица максимального потока:».
Далее из файла matrix_F.txt уже привычным способом извлекаются данные,
которые впоследствии заносятся в таблицу и выводятся на экран пользователю.
Ниже таблицы будет располагаться само значение максимального потока
(Листинг 35).
file_maxflow=open('MaxFlow.txt','r')
S=file_maxflow.read()
label_maxflow.setText(u'Максимальный поток:' + S)
vbox.addWidget(label_maxflow)
label_maxflow.show()
Листинг 35. Печать результатов из файла 'MaxFlow.txt'
Из файла MaxFlow.txt извлекается значение максимального потока и
временно помещается в переменную S. Далее на экран выводится метка
label_maxflow,
на
которую
с
помощью
setText()
устанавливается
текст
«Максимальный поток:» и записывается значение из переменной S. Метка
устанавливается на компановщик и становится видимой для пользователя (Рис.
11).
64
Рисунок 11. Вывод результата на экран
Так же предоставляем пользователю изображение конечного графа, с
детальным указанием насыщенных дуг (Листинг 36).
os.system('shotwell PNG/maxdigraph.png')
Листинг 36. Вывод изображения на экран
os.system запускает в shotwell – стандартном фото менеджере для Linux
изображение,
располагающееся
в
директории,
путь
к
которой
PNG/maxdigraph.png.
Описание функций окончено. Соединим их с кнопками при помощи
сигналов (Листинг 37).
QObject.connect(button_ok, SIGNAL("clicked()"), OK)
QObject.connect(button_count_up, SIGNAL("clicked()"), COUNT_UP)
Листинг 37. Соединение кнопок с функциями.
65
connect() соединяет кнопки сигналом clicked() с соответствующими им
функциями. Сигнал clicked() испускается при активизации кнопки (т.е. когда
нажатая кнопка отпускается при нахождении указателя мыши внутри кнопки).
Для успешной работы всего приложения необходимо не забыть сделать
видимым главный виджет (Листинг 38).
window.show()
sys.exit(a.exec_())
Листинг 38. Главное окно
В последней строке выполняется запуск цикла обработки сообщений
операционной системы направленный в окно приложения. После вызова
метода exec() произойдет блокировка исполнения всех дальнейших команд
приложения.
2.2.
Программная реализация алгоритма Дейкстры
Программный код реализован в трех исходных файлах:
•
deikstra.py – исходный файл с полной программной реализацией
алгоритма. При вызове данного файла производятся подсчеты, основанные
на алгоритме Дейкстры, и сохранение результатов работы в файлы;
•
window_deikstra.py –
исходный
файл
с
описанием
пользовательского интерфейса. Здесь реализованы такие функции, как
открытие/сохранение файла и ввод исходных данных.
•
window_result_deikstra.py – исходный файл, реализующий вывод
результатов программы в отдельное окно. Это необходимо для того, чтобы
не «перегружать» исходное окно приложения информацией и метками.
Пользователь может в любой момент закрыть окно с результатом и
пересчитать задачу с другими исходными данными.
66
2.2.1. Описание программного обеспечения, реализованного с помощью
языка Python. Содержимое исполняемого файла «deikstra.py»
Подключаемые библиотеки:
Sys - содержит функции, относящиеся к интерпретатору Python и его среде,
т.е. к системе (system);
Os - предоставляет множество функций для работы с операционной
системой;
Numpy - библиотека, добавляющая поддержку больших многомерных
массивов и матриц, вместе с большой библиотекой высокоуровневых (и очень
быстрых) математических функций для операций с этими массивами;
Queue - класс для организации очереди.
В самом начале происходит загрузка исходных данных, заданных
пользователем – матрицы пропускных способностей сети и номер вершины, до
которой необходимо найти кратчайшее расстояние. Значения выгружаются из
файлов и присваиваются соответствующим переменным в программе (Листинг
39).
file_maxflow=open('K.txt','r')
k=int(file_maxflow.read())
l = []
for line in open( 'matrix_C.txt' ):
l.append( [ int(x) for x in line.split() ] )
C = list( l )
Листинг 39. Загрузка исходных данных
K – номер переменной, C – массив, хранящий значения пропускных
способностей.
Определяем остальные переменные и структуры для работы алгоритма
(Листинг 40).
SIZE=len(C)
67
D=[[0] for i in range(SIZE)]
V=[[0] for i in range(SIZE)]
temp=0
min_index=0
minimum=0
pred=[[0] for i in range(SIZE)]
q=Queue.LifoQueue()
Листинг 40. Определение основных переменных и структур
SIZE – размерность массива C;
D – массив, хранящий значения минимальных расстояний до вершины;
V – массив, хранящий метки посещенных вершин;
temp – вспомогательная переменная;
min_index – хранит индекс минимального значения из массива;
minimum – хранит значение текущего минимального элемента;
pred – массив предков вершин, необходимый для восстановления путей;
q – очередь по принципу «последний зашел – первый вышел», необходимая
для восстановления путей.
Инициализируем вершины и расстояния (Листинг 41).
for i in range(SIZE):
D[i]=10000
V[i]=0
D[0]=0
Листинг 41. Инициализация вершин и расстояний
Изначально все значения матрицы минимальных расстояний, кроме одной
(самой первой), принимаем за бесконечность (10000). Значение 0 в массиве
«посещенных вершин», говорит о том, что вершина еще не была посещена.
68
Далее запускаем цикл с постусловием, который будет выполняться до тех
пор, пока еще возможно найти минимальный путь до какой-либо из имеющихся
вершин (Листинг 42.).
while True:
min_index=10000
minimum=10000
for i in range(SIZE):
if V[i]==0 and D[i]<minimum:
minimum=D[i]
min_index=i
if min_index !=10000:
for i in range(SIZE):
if C[min_index][i]>0:
temp=minimum+C[min_index][i]
if temp<D[i]:
D[i]=temp #
pred[i]=min_index
V[min_index]=1
if not min_index<10000:
break
Листинг 42. Реализация шага алгоритма
Поочередно просматриваются все не посещенные вершины, в которые
можно попасть из текущей. Выявляется минимальное значение пути и
прибавляется к текущему значению пути в эту вершину. После этого вершина
помечается как посещенная. Таким образом итерации продолжаются до тех пор,
пока все вершины не будут посещены.
После отработки алгоритма необходимо сохранить найденное значение
минимального потока в файл, для дальнейшего вывода на экран пользователю
(Листинг 43).
69
file_maxflow=open('MinFlow.txt','w')
file_maxflow.write(str(D[k]))
file_maxflow.close()
Листинг 43. Сохранение результатов работы в файл
Полученный минимальный поток до заданной вершины k будет сохранен в
файле 'MinFlow.txt'.
В программном обеспечении так же реализована процедура восстановления
пути до вершины. Восстановление происходит с помощью «массива предков»
pred (Листинг 44).
while k!=0:
q.put(k)
k=pred[k]
q.put(0)
Листинг 44. Восстановление маршрута
В массиве уже хранятся все необходимые номера вершин, остается лишь
извлечь их оттуда. Для этого используется очередь, в которую последовательно
помещаются вершины от конечной до начальной. Так как очередь построена по
принципу «первый зашел-последний вышел», при извлечении номеров вершин из
очереди они будут располагаться в необходимом нам порядке. Остается лишь
записать ее в файл, для дальнейшей демонстрации пользователю (Листинг 45).
file_F=open('MinPut.txt', 'w')
while q.empty()!=True:
file_F.write(str(q.get()) + " ")
file_F.close()
Листинг 45. Запись результатов в файл
70
Найденный минимальный путь из начальной вершины в заданную будет
храниться в файле 'MinPut.txt'.
2.2.2. Описание программного обеспечения, реализующего интерфейс для
пользователя. Файл «window_deikstra.py»
Исходное окно приложения идентично рассматриваемому уже ранее в
пункте про задачу о максимальном потоке. Пользователю предоставляются те же
самые функции открытия или заполнения вручную исходных данных (Рис. 12).
Рисунок 12. Исходный вид приложения при запуске
После ввода данных у пользователя так же запрашивается номер вершины,
до которой необходимо найти минимальный поток (Рис.13).
71
Рисунок 13. Файл «10.txt» после загрузки в ПО
После воода значения необходимо нажать кнопуку «Count up», которая
запустит работу алгоритма (Рисунок 14).
Рисунок 14. Результат работы ПО после нажатия кнопки «Count up»
Итак, минимальный путь до заданной вершины найден. Пользователю
предоставляется не только само значение минимального пути, но и весь маршрут
от вершины - истока до конечной (в данном случае 3).
Сохранять эти данные нет необходимости – в процессе работы программы
они автоматически располагаются в файлах «MinFlow.txt» и «MinPut.txt»
(Рисунок 15-16).
72
Рисунок 15. Содержимое файла «MinFlow.txt»
Рисунок 16. Содержимое файла «MinPut.txt»
2.2.3 Описание процесса разработки откна для вывода результатов.
Файл «window_result_deikstra.py»
Для удобства отображения было решено вынести результаты работы
программы в отдельное окно. Рассмотрим фрагмент кода, отображающий
извлечение данных, для их последующей передачи пользователю (Листинг 46).
file_D = open('K.txt','r')
k = file_D.read()
73
file_D = open('MinFlow.txt','r')
D = file_D.read()
file_D = open('MinPut.txt','r')
l = []
for line in (file_D):
l=line
Листинг 46. Извлечение данных из файлов
В переменную k из файла «K.txt» записывается номер вершины, до кторой
необходимо было найти минимальный поток. Из файла «MinFlow.txt» в
переменную D считывается само значение найденного минимального потока.
Строка l хранит в себе последовательность номеров вершин, представляющих
собой минимальный путь до искомой вершины и хранящихся в файле
«MinPut.txt».
Далее необходимо собрать все эти данные воедино для корректного вывода
пользователю (Листинг 47).
label_maxflow=QLabel()
label_maxflow.setText(u'Минмальный поток из вершины 0 в вершину ' +
str(k) + ' = ' + D + u'Минимальный путь:' + l)
Листинг 47. Формирование метки с данными
74
На Рисунке 17 представлено как выглядит вывод результатов в приложении.
Рисунок 17. Окно вывода результатов
Результаты работы программы выводятся автономно в отдельном окне, при
этом окно с вводом данных так же остается открытым. Поэтому пользователь в
любой момент может вернуться и пересчитать задачу с другими входными
данными.
2.3.
Программная реализация решения задачи о назначениях с помощью
Венгерского алгоритма
Программный код реализован в пяти исходных файлах:
• n_min.py – исходный файл, содержащий реализацию Венгерского
алгоритма для поиска минимума целевой функции. При вызове
данного файла запускается работа алгоритма, а найденное решение
сохраняется в файл;
• n_max.py - исходный файл, содержащий реализацию Венгерского
алгоритма для поиска максимума целевой функции;
• window_naz.py
–
исходный
файл,
содержащий
описание
пользовательского интерфейса. Здесь пользователь может открывать,
вводить и сохранять исходные данные;
• window_result_naz_min.py – исходный файл, при запуске которого
выводится отдельное окно с результатами решенной задачи на
минимум;
75
• window_result_naz_max.py - исходный файл, при запуске которого
выводится отдельное окно с результатами решенной задачи на
максимум;
2.3.1. Описание программного обеспечения, реализованного с помощью
языка Python. Содержимое исполняемых файлов «n_min.py» и
«n_max.py»
Поскольку решение задач на максимум и минимум различаются лишь в
предварительной подготовке исходной матрицы, будем рассматривать их вместе.
Рассмотрим основные переменные, используемые в программе:
matrix – исходная матрица размера n на m. В данном примере будем
рассматривать случай, когда n = m;
height, width – размеры n и m соответственно (Листинг 48);
l = []
for line in open( 'matrix_C.txt' ):
l.append( [ int(x) for x in line.split() ] )
matrix = list( l )
height=len(matrix)
width=len(matrix[1])
Листинг 48. Определение основных переменных
В случае открытой задачи, когда количество строк и столбцов не совпадает,
необходимо ввести дополнительную нулевую строку или столбец, а затем
пересчитать заново размерность матрицы (Листинг 49).
76
if height > width:
for i in range(height):
matrix[i].append(0)
elif width > height:
d=[0 for k in range(width)]
matrix.append(d)
height=len(matrix)
width=len(matrix[1])
Листинг 49. Переопределение размерности матрицы
u, v – одномерные массивы размеров height и width соответственно. Эти
значения будут вычитаться из элементов матрицы следующим образом:
[][] − [] − [];
markIndices – массив размерности width, в котором хранится значение
текущего множества нулевых элементов (нулевой цепи). Для некоторого нулевого
элемента (i,j) в markIndices[j] будет храниться значение i – строки этого элемента
или -1, если нулевого элемента нет (Листинг 50).
u=[0 for i in range(height)]
v=[0 for i in range(width)]
markIndices=[-1 for i in range(width)]
Листинг 50. Определение основных массивов
Еще несколько вспомогательных массивов размера width:
links – в нем хранятся ссылки на последующий столбец. Этот массив
необходим для восстановления найденной цепи. Изначально инициализирован -1;
mins - содержит информацию только о не посещенных столбцах. Хранит
минимальное значение текущего столбца;
77
visited - является массивом флагов. В нем единицами отмечены посещенные
столбцы.
Нет необходимости хранить информацию о посещенных строках, поскольку
при помощи массива markIndices по номерам посещенных столбцов можно узнать
положение всех посещенных элементов.
Положение
последнего
посещенного
элемента,
который
претерпел
коллизию задается переменными markedI и markedJ (Листинг 51).
links=[-1 for k in range(width)]
mins=[100 for k in range(width)]
visited=[0 for k in range(width)]
markedI=i
markedJ=-1
Листинг 51. Определение вспомогательных переменных и массивов
В программе два основных цикла. Первый отвечает за переход между
просматриваемыми строками. При рассмотрении каждой строки происходит
попытка увеличить количество отмеченных нулевых элементов хотя бы на
единицу. За эту процедуру отвечает второй цикл (Листинг 52).
for j1 in range(width):
if visited[j1]==0:
if matrix[markedI][j1]-u[markedI]-v[j1]<mins[j1]:
mins[j1]=matrix[markedI][j1]-u[markedI]-v[j1]
links[j1]=markedJ
if j==-1 or mins[j1]<mins[j]:
j=j1
delta=mins[j]
for j1 in range(width):
78
if visited[j1]==1:
u[markIndices[j1]]+=delta
v[j1]-=delta
else:
mins[j1]-=delta
u[i]+=delta
Листинг 52. Поиск нулевых элементов
Здесь происходит поиск минимальных элементов по строке и столбцу и
вычитание этого элемента из всех элементов матрицы. При этом увеличивается
число нулей. Если в столбце с найденным нулем больше нет других нулей, то он
становится компонентом искомой нулевой цепи. В противном случае, если в
текущем столбце уже есть один нуль, возникает конфликт, который будем
называть коллизией. Решением коллизии считается такое решение, при котором в
одной строке и в одном столбце матрицы будет стоять ровно один нуль. Эти нули
и будут представлять собой искомую нулевую цепь.
После того, как нулевая цепь найдена, необходимо вернуть результат
пользователю. В первую очередь в файл «Naz.txt» записываются пары (i,j),
представляющие собой номера назначений и исполнителей. Номера вершин
восстанавливаются с помощью массива markIndices (Листинг 53).
file_F=open('Naz.txt', 'w')
for j in range(width):
if markIndices[j]!=-1:
file_F.write(str(markIndices[j]) + " " + str(j) + '\n')
file_F.close()
Листинг 53. Запись найденной нулевой цепи в файл
79
Кроме того в вычисляется значение целевой функции. Эти данные
помещаются в файл «MinNaz.txt» (Листинг 54).
MinFunk=0
for j in range(width):
MinFunk+=matrix[markIndices[j]][j]
file_F=open('MinNaz.txt', 'w')
file_F.write(str(MinFunk))
file_F.close()
Листинг 54. Запись в файл значения минимума функции
Значение целевой функции складывается из суммы значений исходной
матрицы matrix, находящихся на пересечении i-той строки и j-того столбца, где i –
элемент markIndices[j].
Алгоритм нахождения минимума и максимума целевой функции полностью
совпадает. Единственный нюанс – при нахождении максимума, исходную
матрицу необходимо подготовить к расчетам.
Необходимо найти максимальный элемент, среди всех элементов исходной
матрицы и создать новую матрицу, каждый элемент которой будет представлять
собой разность найденного максимального элемента и элемента исходной
матрицы (Листинг 55).
max_el=max([e for elem in matrix_is for e in elem])
for i in range(height):
for j in range(width):
matrix[i][j]=max_el-matrix_is[i][j]
Листинг 55. Преобразование исходной матрицы
80
Измененную матрицу следует использовать во время вычислений вместо
исходной. Однако значение целевой функции будет вычисляться из значений
элементов исходной матрицы. Данные сохраняются в файл «MaxNaz.txt» (Листинг
56).
MaxFunk=0
for j in range(width):
MaxFunk+=matrix_is[markIndices[j]][j]
file_F=open('MaxNaz.txt', 'w')
file_F.write(str(MaxFunk))
file_F.close()
Листинг 56. Запись в файл максимума функции
2.3.2. Описание программного обеспечения, реализующего интерфейс для
пользователя. Файл «window_ naz.py»
Как и в случаях с вышеописанными алгоритмами при запуске приложения
пользователю необходимо ввести исходные данные. Различие в том, что на этот
раз у пользователя запрашивается размерность матрицы и по строкам и по
столбцам, поскольку для этой задачи данные параметры могут не совпадать
(Рисунок 18).
Рисунок 18. Исходное окно приложения
81
После ввода количества назначений и исполнителей, приложением
генерируется матрица с нулевыми элементами, которые впоследствии можно
изменить. Введем например количество назначений – 4 и количество
исполнителей -5 (Рисунок 19).
Рисунок 19. Формирование матрицы по данным от пользователя
При решении задач с большим объемом исходных данных матрицу можно
загрузить из файла, воспользовавшись кнопкой в левом верхнем углу экрана
приложения (Рисунок 20).
Рисунок 20. Ввод исходных данных
82
Как видно из рисунков после ввода исходных данных появились еще две
кнопки. Нажав на одну из них, пользователь может запустить процесс решения
данной задачи либо на минимум, либо на максимум.
Рассмотрим как это выглядит в исходном коде программы на примере
нажатия кнопки «min» (Листинг 57).
def MIN():
new_file=open('matrix_C.txt', 'w')
for i in range(table.rowCount()):
for j in range(table.columnCount()):
item=str(table.item(i,j).text())
new_file.write(item + " ")
new_file.write("\n")
new_file.close()
os.system('python n_min.py')
os.system('python window_result_naz_min.py')
Листинг 57. Функция MIN()
При нажатии пользователем на кнопку приложению отправляется сигнал о
том, что необходимо запустить подсчет задачи. Первым делом из окна
приложения считываются исходные данные задачи и сохраняются в файл. Эта
матрица передается в исполняемый файл «python n_min.py», в котором находится
реализация самого алгоритма. Далее запускается окно вывода результатов на
экран
83
2.3.3. Описание процесса разработки откна для вывода результатов.
Файлы «window_result_naz_max.py» и «window_result_naz_min.py»
Два отдельных скрипта реализуют вывод результатов для максимума и
минимума в отдельное окно. Поскольку принцип вывода данных для
пользователя в случае максимума и минимума аналогичен, рассмотрим это
процесс на примере файла «window_result_naz_max.py» (Листинг 58).
file_Naz = open('Naz.txt','r')
L=file_Naz.read()
file_Naz = open('MaxNaz.txt','r')
Naz = file_Naz.read()
label_minflow=QLabel()
label_minflow.setText(u'Назначение-> исполнитель\n'+ L + u'\n
Максимальная прибыль\n ' + Naz)
hbox.addWidget(label_minflow)
label_minflow.show()
Листинг 58. Вывод данных для пользователя
Из файлов «Naz.txt» и «MaxNaz.txt» считываются значение целевой функции
и распределение назначений между работниками соответственно. Вся эта
информация помещается на метку, которая потов выводится на экран виджета
(Рисунок 21).
84
Рисунок 21. Окно вывода данных для пользователя. Случай максимума
Аналогичная
информация
считывается
из
файла
«MinNaz.txt»
в
исполняемом файле «window_result_naz_min.py». На рисунке 22 представлен
результат работы этого файла.
Рисунок 22. Окно вывода данных для пользователя. Случай минимума
85
2.4.
Разработка дополнительных скриптов
• window.py – стартовое окно приложения, содержащие кнопки для
выбора пользователем задачи;
• randomgraph.py – вспомогательный скрипт, осуществляющий
генерирование случайных графов различной размерности,
разработанный для тестирования ПО
2.4.1. Разработка стартового окна приложения
Как можно понять из всего вышесказанного, было разработано три
программы, каждая из которых решает определенную задачу. Любое из этих
приложений можно использовать автономно. В рамках данной работы было
решено объединить их в одно приложение. Отсюда возникла задача разработать
некое стартовое окно приложения, в котором пользователю будет предоставлен
выбор решить одну из трех задач. При выборе пользователем определенной
задачи, в отдельном окне будет запускаться приложение, работающее над этой
задачей. Окно будет полностью автономно, в любой момент пользователь может
вернуться к стартовому окну без перезапуска приложения и решить другую
задачу.
Стартовое окно представляет собой виджет, содержащий три кнопки,
нажатие каждой из которых провоцирует запуск приложения с определенной
задачей (Листинг 59).
button_MF= QPushButton("MaxFlow")
button_D = QPushButton("Deikstra")
button_N = QPushButton('Naznacheniya')
hbox.addWidget(button_MF)
hbox.addWidget(button_D)
hbox.addWidget(button_N)
86
def MF():
os.system('python window_maxflow.py')
def D():
os.system('python window_deikstra.py')
def N():
os.system('python window_naz.py')
QObject.connect(button_MF, SIGNAL("clicked()"), MF)
QObject.connect(button_D, SIGNAL("clicked()"), D)
QObject.connect(button_N, SIGNAL("clicked()"), N)
Листинг 59. Описание работы стартового окна
На рисунке 23 представлено изображение готового стартового окна.
Рисунок 23. Стартовое окно
87
2.4.2. Описание программного обеспечения, реализующего генерацию
случайных входных данных. Содержимое исполняемого файла
«randomgraph.py»
В процессе отладки и тестирования ПО возникла необходимость в создании
скрипта, который бы генерировал случайные графы различной размерности.
Создание этого скрипта избавило от ввода данных вручную и значительно
ускорило процесс тестирования ПО.
Рассмотрим переменные и функции, используемые в данном скрипте более
подробно.
n – количество вершин графа;
C – пока что пустая исходная матрица пропускных способностей графа;
w –
некоторая вероятность, с которой граф заполняется случайными
числами.
random.choice()
–
выбирает
случайный
элемент
из
непустой
последовательности, указанной в скобках.
Если значение переменной w, отвечающей за вероятность, равно нулю, то и
в элемент матрицы C так же помещается значение «нуль». Иначе, если w='1', то в
элемент матрицы C помещается случайное число.
random.randint() – выбирает случайное целое число из предоставленного
списка, в данном случае число будет в диапазоне от 0 до 10.
Если элемент находится:
• на диагонали (петля);
• в первом столбце (возврат в вершину – исток);
• в последней строке (выход из вершины – стока),
то его значение по умолчанию – «нуль».
Необходимо помнить о том, что сумма пропускных способностей дуг,
выходящих из вершины – источника, должна быть равна сумме пропускных
способностей дуг, входящих
в вершину
необходимые расчеты (Листинг 60).
–
сток. Поэтому производим
88
istok=0
stok=0
k=0
i=0
for j in range(n):
istok+=C[i][j]
j=n-1
for i in range(n):
stok+=C[i][j]
if istok>stok:
k=istok-stok
j=n-1
for i in range(0,n-1):
if C[i][j]==0:
C[i][j]=k
break
elif stok>istok:
k=stok-istok
i=0
for j in range(1,n-1):
if C[i][j]==0:
C[i][j]=k
break
Листинг 60. Реализация правила о сумме пропускных способностей дуг
89
Переменная istok будет хранить сумму пропускных способностей дуг,
выходящих из вершины – источника, а переменная stok – сумму пропускных
способностей дуг, входящих в вершину – сток.
k – переменная для хранения разницы между значениями переменных istok
и stok.
Двигаясь в одном цикле по первой строке, а в другом по последнему
столбцу, считаем сумму пропускных способностей дуг и сравниваем их между
собой.
Если значение переменной istok больше значения переменной stok, т.е.
сумма пропускных способностей дуг, выходящих из вершины – источника
больше суммы пропускных способностей дуг, входящих в вершину – сток, то в
переменную k заносится разность между этими значениями. Недостающую
разность необходимо поместить в последний столбец матрицы. Поэтому
значение, хранящееся в переменной k, присваивается любому нулевому элементу
матрицы из последнего столбца.
break прерывает выполнение цикла.
Если ситуация обратная – значение переменной stok больше значения
переменной istok, то недостающая разность помещается в любой пустой элемент,
находящийся в первой строке матрицы.
После того как матрица сформирована, необходимо записать ее в файл для
дальнейшего использования в программе (Листинг 61).
File=open('matrix_C.txt', 'w')
for i in range(n):
for j in range(n):
File.write(str(C[i][j]) + " ")
File.write("\n")
File.close()
Листинг 61. Запись сформированной матрицы в файл
90
Граф сохраняется в текстовом файле в той форме, в которой его удобно
передавать в приложения. Дополнительных действия над матрицей производить
не нужно. Матрица сгенерированная данным скриптом может в дальнейшем
использоваться в приложении для решения тестовых задач.
91
ГЛАВА 3. ИССЛЕДОВАНИЕ ЗАДАЧ
Говоря о работе аэропорта, завода, крупного предприятия или компании,
следует помнить о больших объемах данных, которые приходится обрабатывать
при решении каждой из представленных в данной работе задач. Поэтому очень
важно
проанализировать
работоспособность
разработанного
программного
обеспечения на конкретных примерах с различным объемом исходных данных.
3.1. Исследование задач на нахождение максимального потока в сети с
помощью алгоритма Форда-Фалкерсона
Продемонстрируем наглядно на примерах поиск и построение
максимального потока в сети с помощью разработанного программного
обеспечения
на
языке
Python.
рассматриваемых
задач
будет
полученных
в
ходе
работы
Процесс
нахождения
сопровождаться
программного
решения
изображениями
обеспечения
и
для
графов,
подробными
пояснениями.
3.1.1. Пошаговый пример применения алгоритма Форда-Фалкерсона для
решения задачи о нахождении максимального потока в сети
Дана сеть, представленная в виде ориентированного графа. Задается
исходный граф в виде матрицы C пропускных способностей сети, где на
пересечении i-той строки и j-того столбца располагаются значения пропускной
способности дуги из i-той вершины в j-тую. Число вершин графа – 5 (Таблица 1).
Таблица 1. Исходная матрица
0
5
2
4
3
0
0
1
0
2
0
0
0
0
6
92
0
3
2
0
3
0
0
0
0
0
Требуется найти максимальный поток для данной сети.
На Рисунке 12 представлено графическое представление заданного графа,
сохраненное в файл “digraph.png” (Рис. 24).
Рисунок 24. Исходный граф (“digraph.png”).
Как уже отмечалось ранее, кроме матрицы пропускных способностей C
ключевую роль играют:
- матрица F потоков сети, которая будет изменяться на каждой итерации в
процессе построения максимального потока;
- массив P, являющийся результатом, возвращаемым функцией bfs и
представляющий собой некий массив «предков», где P[i] - номер вершины, и
которой мы попали в вершину i;
- flow-переменная, хранящая текущее значение максимального потока
транспортной сети и являющаяся результатом работы фукции maxflow.
Именно
поэтому
дальнейшее
рассмотрение
примера
построения
максимального потока будет сопровождаться демонстрацией промежуточных
значений данных переменных.
Переходим к первой итерации (Листинг 62).
93
P=[[0],0,0,0,0]
flow=3
Листинг 62. Первая итерация
Следует напомнить, что функция maxflow собирает цепочку дуг из
источника в сток на основании данных из массива P, начиная с конца. Из
Листинга 43 можно увидеть, что P[4]=0 - это означает, что в вершину 4 мы
попали из вершины 0.
Увеличивающая цепь: 0->4.
Так как 4 - вершина-сток, а 0 –вершина-источник, то поиск дуги завершен.
По данному пути и будет строиться максимальный поток. Учитывая, величину
потока flow=3, матрица потока F на первой итерации будет выглядеть следующим
образом (Таблица 2):
Таблица 2. Первая итерация
0
0
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
На
основании
данной
приведенный на Рисунке 25.
матрицы
программой
был
построен
граф,
94
Рисунок 25. Первая итерация
Дуги, отмеченные красным цветом – насыщенные дуги, по которым более
нельзя пропустить поток.
Разберем подробно еще одну итерацию (Листинг 63).
P=[[0],0,0,0,3]
flow=6
Листинг 63. Вторая итерация
Следуя листингу видно, что P[4]=3 (в вершину 4 попадаем из вершины 3),
P[3]=0 (в вершину 3 попадаем из вершины 0). Эта запись аналогична записи
увеличивающей цепи 0->3->4. Максимальный поток на второй итерации
увеличился на 3 (flow+=3), следовательно, текущий максимальный пропущенный
поток flow=6.
В таблицу 3 показано как изменится матрица F.
Таблица 3. Вторая итерация
0
0
0
3
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
95
Граф, построенный по данным матрицы F, представлен на Рисунке 26.
Рисунок 26. Вторая итерация
Дуги, отмеченные зеленым цветом - те, по которым был пропущен какой-то
поток, но он не является для них максимальным.
Рассмотрим последующие итерации. (Листинг 45-48, Рисунок 15-18)
Третья итерация (Листинг 64, Таблица 4, Рисунок 27):
P=[[0],0,0,0,2]
flow=8
Листинг 64. Третья итерация
Увеличивающая цепь 0->2->4, flow+=2, F=
Таблица 4. Третья итерация
0
0
2
3
3
0
0
0
0
0
0
0
0
0
2
0
0
0
0
3
0
0
0
0
0
96
Рисунок 27. Третья итерация
Четвертая итерация (Листинг 65, Таблица 5, Рисунок 28):
P=[[0],0,3,0,2]
flow=9
Листинг 65. Четвертая итерация
Увеличивающая цепь 0->3->2->4, flow+=1, F=
Таблица 5. Четвертая итерация
0
0
2
4
3
0
0
0
0
0
0
0
0
0
3
0
0
1
0
3
0
0
0
0
0
97
Рисунок 28. Четвертая итерация
Пятая итерация (Листинг 66, Таблица 6, Рисунок 29):
P=[[0],0,1,[0],1]
flow=11
Листинг 66. Пятая итерация
Увеличивающая цепь 0->1->4, flow+=2, F=
Таблица 6. Пятая итерация
0
2
2
4
3
0
0
0
0
2
0
0
0
0
3
0
0
1
0
3
0
0
0
0
0
98
Рисунок 29. Пятая итерация
Шестая итерация (Листинг 67, Таблица 7, Рисунок 30):
P=[0],0,1,[0],2]
flow=12
Листинг 67. Шестая итерация
Увеличивающая цепь 0->1->2->4, flow+=1, F=
Таблица 7. Шестая итерация
0
3
2
4
3
0
0
1
0
2
0
0
0
0
4
0
0
1
0
3
0
0
0
0
0
99
Рисунок 30. Шестая итерация. Конечный граф (“maxdigraph.png”).
Рисунок 30 демонстрирует конечное решение данной задачи, с найденным
потоком flow=12. Результаты сохранены в файл “maxdigraph.png”.
3.1.2. Примеры решения более сложных задач и моделирование их путем
использования разработанного программного обеспечения
Разработанное программное обеспечение может использоваться не
только для нахождения максимального потока в простых графах, но и
для решения задач прикладного характера. Как правило,
это
подразумевает работу с большим объемом входных данных. В этом
случае уместно будет рассмотреть вопрос о временных затратах,
которые могут уходить на подсчет максимального потока в сетях с
количеством вершин от 10 и более. Продемонстрируем эффективность
работы ПО на более сложных графах.
Рассмотрим произвольный граф, состоящий из 10-ти вершин
(Рисунок 31).
100
Рисунок 31. Исходный граф. 10 вершин.
В результате работы программного обеспечения мы получим
нагруженный граф, представленный на Рисунке 32.
101
Рисунок 32. Нагруженный граф. 10 вершин
При применении данного программного обеспечения для графов
больших размерностей, очевидно возникает вопрос о временных
затратах на расчеты. Для того чтобы наглядно продемонстрировать
эффективность
разработанного
программного
обеспечения,
в
программный код был добавлен подсчет времени работы программы. В
Листинге 68 представлен результат подсчета максимального потока в
графе с 10-тью вершинами.
Program time: 0.208583116531 seconds
Листинг 68. Время обработки графа с 10-тью вершинами
102
Для
наглядности
продемонстрируем
результаты
работы
программного обеспечения с графами размерности 16 и 20. Проследить
эффективность ПО можно по Листингам 50 – 51 и изображениям
графов (Рисунок 33 – 34).
Граф с количеством вершин n=16 (Рисунок 33, Листинг 69).
Рисунок 33. Нагруженный граф. 16 вершин
103
Program time: 1.06184315681 seconds
Листинг 69. Время обработки графа с 16-тью вершинами
Граф с количеством вершин n=20 (Рисунок 34, Листинг 70).
Рисунок 34. Нагруженный граф. 20 вершин
104
Program time: 2.5166490078 seconds
Листинг 70. Время обработки графа с 20-тью вершинами
Рассмотрим результаты подсчетов затраты времени на графах
размерности
Графы от 20 вершин и более выглядят достаточно громоздко,
однако это несильно сказывается на скорости их подсчетов. На рисунке
35 в виде графика представлены результаты подсчета времени
выполнения ПО, на графах с различным количеством вершин.
Время выполнения
программы
70.00
60.00
50.00
40.00
30.00
20.00
10.00
0.00
20
30
40
50
60
70
80
90
100
Размерность матрицы
Рисунок 35. Результаты подсчета времени выполнения
алгоритма Форда-Фалкерсона
Безусловно, увеличение размерности графа сказывается на
времени, которое затрачивается на подсчеты. Однако, разработанное
105
программное обеспечение, позволяет значительно сократить время
обработки информации. Как видно из листингов, данное программное
обеспечение эффективно работает с
большим объемом входных
данных и может быть использовано для решения задач прикладного
характера.
3.1.3. Решение прикладной задачи на нахождение максимального потока
Практическая область применения данной задачи достаточно обширна.
Задачи на поиск максимального потока встречаются при исследовании сетей
трубопроводов и транспортных путей, моделировании различных процессов
физики и химии, применяются
в коммуникационных и электрических сетях,
некоторых операциях над матрицами и для решения родственных задач теории
графов.
Рассмотрим одну из прикладных задач.
Постановка
задачи.
Во
время
осуществления
военных
действий
необходимо переправить конвой из 50 транспортных единиц, от места
расположения военной базы (источник) до места концентрации войск (сток). Весь
путь разбит на 12 участков дороги. В целях безопасности для каждого из участков
дорог вводится лимит на число транспортных единиц, которые могут по нему
пройти.
Совокупность дорог, связывающих базу с войсками, может быть
представлена в виде графа, в котором дуги соответствуют незащищенным
участкам дорог, а вершины – точкам пересечения этих дорог. Ограничение на
число транспортных средств, проходящих по каждой из дорог – это пропускные
способности дуг.
Задачу поиска наилучших маршрутов движения для транспортных средств,
состоящих в конвое, можно сформулировать как задачу пересылки из источника в
106
сток 50 единиц потока по сети, соответствующей рассматриваемой системе дорог.
При этом не должна быть превышена пропускная способность ни одной дуги.
Сначала задаем исходную систему дорог, состоящую из 12 участков в виде
матрицы смежности (Рис.36).
Рисунок 36. Исходная матрица
Наглядно система дорог представлена на рисунке в виде графа (Рис.37).
107
Рисунок 37. Исходный граф
Запустим решение программы и посмотрим на распределение потока по
сети (Рис.38).
108
Рисунок 38. Конечный граф
Так же пользователю представляется распределение потока в виде матрицы
и само значение максимального потока (Рис.39).
109
Рисунок 39. Вывод результатов в задаче о максимальном потоке
Как можно видеть из рисунка, максимальный поток – 51. Значит, 50 единиц
техники пройдут по данной системе дорог благополучно и без потерь. В случае,
если бы максимальный поток был
меньше необходимого, мы были бы
вынуждены пересмотреть систему дорог и возможно, добавить еще несколько
участков на пути из источника в сток.
3.2. Исследование задач на нахождение минимального потока в сети с
помощь алгоритма Дейкстры
Продемонстрируем примеры поиска и построения кратчайшего пути с
помощью разработанного программного обеспечения. Итерационный процесс
нахождения
решения
будет
подробными пояснениями.
сопровождаться
изображениями
графов
и
110
3.2.1. Пошаговый пример применения алгоритма Дейкстры для решения
задачи о нахождении минимального потока в сети
Дана сеть, представленная в виде неориентированного графа. Задается
исходный граф в виде матрицы C пропускных способностей сети, где на
пересечении i-той строки и j-того столбца располагаются значения пропускной
способности дуги из i-той вершины в j-тую. Число вершин графа – 5 (Таблица 8).
Таблица 8. Исходная матрица
0
2
0
6
0
2
0
4
0
8
6
4
0
6
2
0
0
6
0
4
0
8
2
4
0
Требуется найти минимальный путь из первой вершины – источника в
последнюю вершину-сток.
На Рисунке 40 представлено графическое представление заданного графа.
111
Рисунок 40. Исходный граф
Рассмотри поседовательно все итерации работы алгоритма.
Итерация 1. Начальная вершина помечается, изначальный поток равен
нулю. Все остальные вершины,путь до которых не известен помечаем знаком
бесконечности (Таблица 9).
Таблица 9. Итерация 1
0
1
2
3
4
0
∞
∞
∞
∞
Итерация 2. Двигаемся из помеченной вершины. Из этой вершины можно
попасть ввершины 1 и 3 . Отмечаем в таблице соответствующие длины
маршрута до этих вершин. Они формируются путем прибавления к значению
помеченной вершины соответстввующих длин маршрута. Значения путей для
остальных вершин остаются неизменными (Таблица 10-11).
112
Таблица 10. Итерация 2
0
1
2
3
4
0
∞
∞
∞
∞
0
2
∞
6
∞
Помечаем минимальное значение пути – вданном случае 2
Таблица 11. Итерация 2. Метка вершины
0
1
2
3
4
0
∞
∞
∞
∞
0
2
∞
6
∞
Итерация 3. Двигаясь из вершины 1 во все остальные отмечаем
соответвуюзие длины маршрута и помечаем минимальное значение пути. Путь из
вершины 1 в вершины 2 и 4 . Минимальное значение пути 6 в вершину 2
(Таблица 12).
Таблица 12. Итерация 3
0
1
2
3
4
0
∞
∞
∞
∞
0
2
∞
6
∞
0
2
6
6
10
Итерация 4. Из вершины 2 можно попасть в вершины 3 и 5 .
Пересчитывая длины маршрутов получаем значения 12 и 8. В таблицу вносятся
наиболее благоприятные (минимальные) значения. Помечаем вершину 3 со
значением 6 (Таблица 13).
113
Таблица 13. Итерация 4
0
1
2
3
4
0
∞
∞
∞
∞
0
2
∞
6
∞
0
2
6
6
10
0
2
6
6
8
Итерация 5. Продолжая движение уже из вершины 3 и пересчитывая
значение пути, удостоверяемся, что 8 – минимальный путь до вершины 4
(Таблица 14).
Таблица 14. Итерация 5
0
1
2
3
4
0
∞
∞
∞
∞
0
2
∞
6
∞
0
2
6
6
10
0
2
6
6
8
0
2
6
6
8
Осталось только восстановить путь в вершину 4 . На рисунке 41
представлена схема восстановления пути в искомую вершину.
Рисунок 41. Схема восстановление пути
114
Как видно из рисунка путь из вершины 0 в вершину 4 :
0 → 1 → 2 → 4 = 0 + 2 + 4 + 2 = 8
На рисунке ниже наглядно изображен найденный путь на графе (Рисунок
42).
Рисунок 42. Найденный маршрут из вершины 0 в вершину 4
Посмотрим результаты работы программного обеспечения с теми же
исходными данными (Рисунок 43).
115
Рисунок 43. Результаты работы ПО
Как видно из рисунка 13 результаты работы ПО полностью совпадают с
результатами подсчетов вручную.
3.2.2. Исследование более сложных задач на нахождение минимального
потока в сети
Подсчет времени выполнения программы позволяет оценить эффективность
разработанного ПО. Для полноты картины важно рассмотреть продолжительность
работы ПО при различных исходных данных. Результаты исследования наглядно
представлены на рисунке 44.
116
Время выполнения
программы
0.25
0.20
0.15
0.10
0.05
0.00
30
60
90 120 150 180 210 240 270 300 330 360 390 420 450 480 510
Размерность матрицы
Рисунок 44. Время выполнения алгоритма Дейкстры
В данном исследовании максимальное взятое количество вершин – 510.
Даже при таком большом значении время выполнение программы не превышает 3
секунд. Это позволяет сделать вывод о том, что разработанное программное
обеспечение значительно сокращает время выполнения алгоритма.
3.2.3. Решение прикладной задачи на нахождение минимального потока
Каждый день, сами того не осознавая мы сталкиваемся с задачей, как
получить большую выгоду, затратив при этом как можно меньше ресурсов. Ведь,
к сожалению, они у нас всегда ограничены. Речь идет о таких задачах как,
например:
- как добраться кратчайшим путем из одного пункта в другой
- как минимизировать затраты на перевозку груза до конкретного пункта
назначения и т.д.
117
Все эти задачи, так или иначе, связаны с нахождением минимального
потока. Рассмотрим одну из таких прикладных задач.
Постановка задачи. Человеку необходимо иметь в своем распоряжении
автомобиль, на протяжении нескольких лет до момента его выхода на пенсию.
Этот автомобиль может либо находиться у него в собственности, либо быть
взятым
напрокат.
Каждый
из
автомобилей
имеет
определенный
срок
эксплуатации и различную стоимость. Требуется найти совокупность наиболее
выгодных сделок за все время до выхода человека на пенсию.
Вершинами графа в данном случае могут быть моменты совершения сделок,
связанных либо с приобретением автомобиля, либо взятием его напрокат. Сам
факт совершения сделки будет отображаться дугой, которая соединяет вершину,
соотносящуюся с временем начала эксплуатации автомобиля, с вершиной,
обозначающей окончание эксплуатации. Длина каждой дуги будет представлять
собой стоимость той или иной сделки в тысячах рублей.
Наименьшая сумма затрат на совершение всех наиболее выгодных сделок
будет соответствовать минимальному потоку, пропущенному из вершиныисточника в вершину-сток, где источник – начальный момент эксплуатации авто,
а сток – момент ухода человека на пенсию.
Посмотрим результат решения задачи (Рис.45).
Рисунок 45. Вывод результатов в задаче о минимальном потоке
Из рисунка видно, что минимальные затраты на эксплуатацию автомобилей
при заданных условиях составляют 160 тысяч рублей.
118
3.3. Исследование задач о назначениях
Говоря о работе завода, крупного предприятия или компании, следует
помнить о больших объемах данных, которые приходится обрабатывать
менеджерам при распределении сотрудников на должности или назначении работ
производственным
машинам.
Поэтому
очень
важно
проанализировать
работоспособность разработанного программного обеспечения на конкретных
примеров с различным объемом исходных данных. Кроме того, необходимо
рассмотреть
как
задачи
открытого/закрытого
типа,
так
и
задачи
на
максимум/минимум.
3.3.1. Пошаговые примеры решения задач о назначении с помощью
Венгерского алгоритма
Рассмотрим ряд задач с их подробным решением, а затем приведем
результаты работы программы, для того, чтобы убедиться в эффективности
разработанного ПО.
Пример 1. Закрытая задача. Минимизация функции.
Число станков равно числу рабочих участков. Необходимо найти
оптимальное решение, которое минимизирует затраты электроэнергии.
Перед нахождением оптимального решения необходимо вычеркнуть
минимальный элемент из каждой строки и каждого столбца. Затем минимальным
количеством линий вычеркиваются все нули матрицы. Среди не вычеркнутых
элементов находится минимальный. Этот элемент вычитается из всех не
вычеркнутых элементов матрицы и прибавляется к элементам, находящимся на
пересечении двух прямых линий. Остальные элементы остаются неизменными.
Оптимальное решение – нули, принадлежащие только одной строке и одному
столбцу. Пошаговое решение примера приведено на рисунке 46.
119
Рисунок 46. Пошаговый пример закрытой задачи на минимум
Из рисунка 1 видно, что значение целевой функции:
 = 0,2 + 1,1 + 2,3 + 3,0 = 9 + 4 + 11 + 4 = 28
Сравним полученное решение с результатами работы ПО (Рис. 47).
Рисунок 47. Результат работы ПО. Пример 1
120
Сравнивая пошаговое решение и результаты работы программы, можем
убедиться, что они совпадают.
Пример 2. Открытая задача. Максимизация функции.
Рассмотрим случай, когда станков больше, чем рабочих участков. При этом
оптимальное решение – максимизация производительности.
Перед тем как приступить к нахождению оптимального решения,
необходимо преобразовать исходную матрицу. Для этого среди всех элементов
матрицы находится максимальный элемент. Новая матрица будет состоять из
разностей максимального элемента и элементов исходной матрицы. Так как число
исполнителей не совпадает с числом работ, необходимо так же добавить нулевой
столбец (Рис. 48). Далее задача решается идентично примеру 1.
Рисунок 48. Пошаговый пример открытой задачи на максимум
121
В данном случае целевая функция:
 = 0,3 + 1,0 + 2,2 + 3,1 = 0 + 15 + 16 + 15 = 46
Результаты работы ПО представлены на рисунке 49.
Рисунок 49. Результаты работы ПО. Пример 2
Как и в предыдущем примере по рисункам видно, что программное
обеспечение работает исправно.
3.3.2. Анализ эффективности разработанного программного обеспечения при
решении задач различных размерностей
Для оценки эффективности разработанного ПО был так же проведен
подсчет времени выполнения программы. Для анализа были взяты данные
различной величины. Рассматривалась эффективность программы как при
решении задач на максимум, так и на минимум. Результаты исследования
приведены на рисунках 50 и 51.
122
Время выполнения
программы
9.00
8.00
7.00
6.00
5.00
4.00
3.00
2.00
1.00
0.00
30
60
90
120
150
180
210
240
270
300
Размерность матрицы
Рисунок 50. Время выполнения задачи на минимум
Время выполнения
программы
9.00
8.00
7.00
6.00
5.00
4.00
3.00
2.00
1.00
0.00
30
60
90
120
150
180
210
240
270
300
Размерность матрицы
Рисунок 51. Время выполнения задачи на максимум
Безусловно,
сказывается
на
увеличение
времени,
количества
которое
исполнителей
затрачивается
на
и
назначений
подсчеты.
Однако,
разработанное программное обеспечение, позволяет значительно сократить время
обработки информации. Как видно из сводной таблицы, данное программное
123
обеспечение эффективно работает с большим объемом входных данных и может
быть использовано для решения задач прикладного характера.
3.3.3. Решение прикладной задачи о назначениях
Как правило, каноническая задача о назначениях связана с распределением
работ либо между исполнителями – людьми, либо исполнителями – машинами.
Однако, как оказалось ее применение может выходить далеко за рамки
привычного.
Рассмотрим такую задачу.
Постановка задачи. Агент по продаже недвижимости имеет для продажи
некоторое
количество
квартир
и
некоторое
количество
потенциальных
покупателей. Каждый покупатель проявляет интерес к нескольким домам, но в
силу соответствия или несоответствия критериям поиска своей «идеальной
квартиры» готов заплатить различную стоимость. Помимо этого, определенный
клиент может осуществлять или не осуществлять торг на каждой из квартир.
Агент, изучив каждого из клиентов, может достаточно точно определить, сколько
каждый из покупателей заплатит за каждый из представленных объектов
недвижимости.
Кроме того, с каждой сделки агент по продаже недвижимости получает
определенный процент комиссионных. Поэтому он, разумеется, заинтересован в
максимизации своей прибыли.
Требуется составить множество пар наиболее выгодных сделок и посчитать
прибыль агента.
В данной задаче вершинами графа будут представляться каждый клиент и
каждый объект недвижимости. Дугами графа – возможности приобретения
определенной квартиры, определенным покупателем. Вес дуги – денежное
вознаграждение (в тысячах рублей), которое принесет агенту данная сделка.
Таким образом, для данной задачи о назначениях мы найдем максимальное
паросочетание, которое и будет являться максимальной прибылью агента.
124
Решение задачи представлено на рисунке 52.
Рисунок 52. Вывод результатов в задаче о назначениях
На рисунке изображено максимальное паросочетание, которое приводит агента к
максимальной прибыли в 107 тысяч рублей.
125
ЗАКЛЮЧЕНИЕ
В данной работе рассматривается проблема разработки программного
обеспечения для моделирования комбинаторных задач на графах. Актуальность
работы определеяется тем, что при решении данных задач огромное значение
имеет время их выполнения. На данный момент есть достаточно много
программных реализаций данных алгоритмов, однако далеко не все они
эффективно справляются с рещением задач большой размерности.
В работе были представлены несколько задач, для каждой из которых
выбран наиболее эффективный алгоритм решения:
•
Задача о максимальном потоке – алгоритм Форда-Фалкерсона;
•
Задача о минимальном потоке – алгоритм Дейкстры;
•
Задача о назначении – Венгерский алгоритм.
Достигнута следующая цель: разработано программноеобеспечение для
моделирования комбинаторных задач на графах.
Были выполнены следующие задачи:
1. Исследована задача на актуальность, проведен анализ источников,
соответствующих тематике работы;
2. Расширены и систематизированы теоретические знания, касающиеся
математического аппарата теории графов;
3. Реализован
программный
код,
посредством
языка
программирования Python, для решения задач о нахождении максимального
потока, минимального потока и задачи о назначениях;
4. Разработан
дружественный
интерфейс
для
взаимодействия
пользователя и программного обеспечения;
5. Проведено исследование и анализ эффективности разработанного
программного обеспечения.
126
Программный код реализована современным высокоуровневом языке
общего назначения Python. Так же была использована утилита Graphviz для
отрисовки графов и PyQy4 для создания пользовательского интерфейса.
Данная работа имеет практическое и теоретическое значение, так как
теоретические данные, изложенные в работе, могут применяться для
дальнейшего исследования более сложных алгоритмов теории графов, а
разработанное
программное
обеспечение
может
использоваться
для
моделирования разнообразных процессов при различных входных данных.
Например, при оптимизации транспортных путей, сетей трубопроводов,
моделировании
различных
процессов
физики
и
химии,
составлении
расписания авиарейсов и перевозки грузов, обработке цифровых изображений
и для решения родственных задач теории графов.
Промежуточные результаты
исследования
были
опубликованы
в
следующих научных работах:
1. Разработка программного обеспечения для реализации алгоритма ФордаФалкерсона нахождения максимального потока в сети // Вестник
студенческих работ Орловского государственного университета (в рамках
«Недели науки-2015»). – Орел: ФГБОУ ВПО «ОГУ», 2015. - вып.7 – с. 2022.
2. Разработка программного обеспечения посредством языка Python для
исследования максимального потока в сети // Молодежный научный форум:
Технические и математические науки. Электронный сборник статей по
материалам
ХХХ
студенческой
международной
заочной
научно-
практической конференции. – Москва: Изд. «МЦНО». – 2016. – № 1 (30) – с.
22-26.
3. О решении прикладных задач путем моделирования на графах //
Современные проблемы физико-математических наук. Материалы II
127
международной научно-практической конференции, 24-27 ноября 2016 г. /
под общ. ред. Т.Н. Можаровой. — Орел: ОГУ, 2016. – с. 170-172.
4. Функционал
программного
обеспечения,
реализующего
алгоритм
нахождения максимального потока в различных сетях // Научнопрактический электронный журнал «Аллея науки» \ Отв. ред. Шелистов
Д.А. – Томск. – 2016. – выпуск №4 (4) – с. 761-765.
5. Функционал
программного
обеспечения,
реализующего
нахождение
кратчайшего пути в различных сетях с помощью алгоритма Дейкстры //
Научно-практический электронный журнал «Аллея науки» \ Отв. ред.
Шелистов Д.А. – Томск. – 2017. – выпуск №12 (2) – с. 395-398.
6. О разработке программного обеспечения для реализации алгоритмов
оптимизации на сетях и графах // Международный научный электронный
журнал «Синергия наук» \ Отв. ред. Сиденко В.П. – Санкт-Петербург: −
2017.− № 15 (сентябрь).− с. 582-587.
7. Аспекты разработки программного обеспечения для решения задачи о
назначениях с помощью Венгерского алгоритма // Наука среди нас: сетевое
научно-практическое издание №1 (5) / под ред. В.И. Вахрушева. –
Магнитогорск : ИП Вахрушев В.И., 26.01.2018. – 76-81.
8. Разработка
программного обеспечения
для
реализации
Венгерского
алгоритма для решения задачи о назначениях // Молодежный научный
форум: Технические и математические науки. Электронный сборник статей
по материалам LIII студенческой международной научно-практической
конференции. – Москва: Изд. «МЦНО». – 2018. – № 1 (53) – с. 78-82.
9. Решение прикладных задач о назначении с помощью программного
обеспечения, реализующего Венгерский алгоритм // Международный
научный электронный журнал «Синергия наук» \ Отв. ред. Сиденко В.П. –
Санкт-Петербург: − 2018.− № 19 (январь).− с. 1560-1566.
128
СПИСОК ИСТОЧНИКОВ
1. Дискретная математика : учебник для вузов / Белоусов А. И., Ткачев С. Б. ;
ред. Зарубин В. С., Крищенко А. П. - 5-е изд. - М. : Изд-во МГТУ им. Н. Э.
Баумана, 2015. - 743 с.
2. Нефедов В.Н., Осипова В.А. Курс дискретной математики — М.:
Издательство МАИ, 2008. — 264с.
3. Набебин А.А. Логика и пролог в дискретной математике. – М.: МЭИ, 2006.
– 452с.
4. Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М. : Айрис-пресс, 2007.
5. Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. 2-е
узд. / Под ред… В.С. Зарубина, А.П. Крищенко. – М.: Узд-во МГТУ им.
Н.Э. Баумана, 2002. – 436 с.
6. Python
2.7.3:
[Электронный
ресурс].
–
Режим
доступа:
https://www.python.org/. – Дата доступа: 01.05.2018.
7. Васильев
А.Н.
Python
на
примерах.
Практический
курс
по
программированию. – СПб.: Наука и Техника, 2016. – 432 с.
8. Graphviz
0.4.10:
[Электронный
ресурс].
–
Режим
доступа:
https://pypi.python.org/pypi/graphviz. – Дата доступа: 01.04.2018.
9. Хаггарти, Р. Дискретная математика для программистов / Р. Хаггарти; Пер.
с англ. С.А. Кулешов. – М.: Техносфера, 2012. – 400 c.
10.Дистель Р. Теория графов Пер. с англ. – Новосибирск: Издательство
института математики, 2002. – 336 с.
11.Окулов С.М. Дискретная математика. Теория и практика решения задач по
информатике: учебное пособие / С.М. Окулов. – 2 – е изд. – М. : БИНОМ.
Лаборатория знаний, 2012. – 422 с.
12.Акимов
О.Е.
Дискретная
математика.
Логика,
группы,
графы.М.:
Лаборатория базовых знаний, 2001. – 376 с.
13.Окулов С.М. Дискретная математика. Теория и практика. Решение задач по
информатике. М.: Бином, 2008. – 424 с.
129
14.Иванов
Б.Н.
Дискретная
математика.
Алгоритмы
и
программы.
Расширенный курс. – М: Известия, 2011. – 512 с.
15.Новиков Ф.А. Дискретная математика для программистов. Учебник для
вузов. 2-е изд. – СПб.: Питер, 2007. – 364 с.
16.Акимов
О.Е.
Дискретная
математика.
Логика,
группы,
графы.М.:
Лаборатория базовых знаний, 2001. – 376 с.
17.Агальцов, В.П. Математические методы в программировании: учебник. В.П.
Агальцов, И.В. Волдайская. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006 г. - 224 с.
18.Кофман А. Введение в прикладную комбинаторику. Под ред. Б.А.
Севастьянова – М.: «Наука», 1975 г. – 474 с.
19.Хаггарти, Р. Дискретная математика для программистов / Р. Хаггарти; Пер.
с англ. С.А. Кулешов. – М.: Техносфера, 2012. – 400 c.
20.Лутц М. Изучаем Python (4 – е издание). – Пер. с англ. – СПб.: Символ –
Плюс, 2011. – 1280 с.
21.Хахаев И. А. Практикум по алгоритмизации и программировании на Python:
/ И. А. Хахаев – М.: Альт Линукс, 2010. – 126с.
22.PyQt
4.4.4:
[Электронный
ресурс].
–
Режим
доступа:
http://doc.crossplatform.ru/python/pyqt/. – Дата доступа: 02.05.2018.
23.Прохоренок Н.А. Python 3 и PyQt. Разработка приложений. – СПб: БХВ –
Петербург, 2012. – 704 с.
130
ПРИЛОЖЕНИЕ
Приложение 1
Файл «maxflow.py».
#!/usr/bin/python
#coding: utf-8
import Queue
import graphviz as gv
import sys
import os
import time
start=time.time()
l = []
for line in open( 'matrix_C.txt' ):
l.append( [ int(x) for x in line.split() ] )
C = list( l )
n=len(C)
F=[[0]*n for i in range(n)]
CF=[[0]*n for i in range(n)]
Cut=[[0] for i in range(n)]
P=[[0] for i in range(n)]
for i in range(n):
for j in range(n):
CF[i][j]=C[i][j]-F[i][j]
s=0
t=n-1
u=0
def bfs(s,t):
Cut=[[0] for i in range(n)]
P=[[0] for i in range(n)]
q=Queue.LifoQueue()
q.put(s)
while q.empty()!=True:
u=q.get()
for i in range(1,n):
if CF[u][i]!=0 and Cut[i]!=1:
q.put(i)
Cut[i]=1
P[i]=u
return P
def maxflow(s,t):
k=0
flow=0
F=[[0]*n for i in range(n)]
for i in range(n):
for j in range(n):
CF[i][j]=C[i][j]
PP=bfs(s,t)
while PP[t]!=[0]:
131
u=t
cmin=1000000
while u!=s:
i=PP[u]
if CF[i][u]<cmin:
cmin=CF[i][u]
u=PP[u]
u=t
while u!=s:
i=PP[u]
F[i][u]+=cmin
CF[i][u]=C[i][u]-F[i][u]
u=PP[u]
flow=0
for i in range(n):
flow+=F[i][t]
k+=1
if k==13:
break
PP=bfs(s,t)
if flow==0:
file_maxflow=open('MaxFlow.txt','w')
file_maxflow.write("Error")
file_maxflow.close()
else:
file_F=open('matrix_F.txt', 'w')
for i in range(n):
for j in range(n):
file_F.write(str(F[i][j]) + " ")
file_F.write("\n")
file_F.close()
file_maxflow=open('MaxFlow.txt','w')
file_maxflow.write(str(flow))
file_maxflow.close()
digraph=gv.Digraph(format='png')
maxdigraph=gv.Digraph(format='png')
digraph.body.extend(['rankdir=LR'])
maxdigraph.body.extend(['rankdir=LR'])
for i in range(n):
digraph.node=(i)
maxdigraph.node=(i)
for i in range(n):
for j in range(n):
A=str(i)
B=str(j)
if C[i][j]!=0:
L='0('+str(C[i][j])+')'
digraph.edge(A,B, label=L)
if F[i][j]!=[0] and F[i][j]==C[i][j]:
L=str(F[i][j])+'('+str(C[i][j])+')'
maxdigraph.edge(A,B, color="red", label=L)
132
elif F[i][j]>0:
L=str(F[i][j])+'('+str(C[i][j])+')'
maxdigraph.edge(A,B, color="green",label=L)
else:
L='0('+str(C[i][j])+')'
maxdigraph.edge(A,B, label=L)
#print(digraph.source)
#print(maxdigraph.source)
digraph.render('PNG/digraph')
maxdigraph.render('PNG/maxdigraph')
return flow
maxf=maxflow(s,t)
finish=time.time()
print finish-start
Приложение 2
133
Файл «window_maxflow.py».
#!/usr/bin/python
# -*- coding: utf-8 -*#coding: utf-8
import sys
import os
from PyQt4.QtCore import *
from PyQt4.QtGui import *
from PyQt4 import *
a=QApplication(sys.argv)
window=QWidget()
window.move(20,10)
window.setWindowTitle("Maxflow")
toolbar=QToolBar(window)
size=QSize(40,40)
toolbar.setIconSize(size)
#toolbar=addToolBar('ToolBar')
#window.addToolBar(toolbar)
label_result=QLabel(u' Матрица максимального потока ')
label_maxflow=QLabel()
table=QTableWidget()
button_count_up = QPushButton("Count up")
def OpenDialog():
file_name = QFileDialog.getOpenFileName(window,'Open file', '/home')
l = []
for line in open(file_name):
l.append( [ int(x) for x in line.split() ] )
C = list( l )
print C
n=len(C)
table.setColumnCount(n)
table.setRowCount(n)
for i in range(n):
for j in range(n):
item=QTableWidgetItem(str(C[i][j]))
table.setItem(i,j,item)
table.resizeColumnsToContents()
table.resizeRowsToContents()
new_size_h=table.verticalHeader().width() +
table.horizontalHeader().length()+25
new_size_v=table.verticalHeader().length()+200
window.resize(new_size_h, new_size_v)
vbox.addWidget(table)
vbox.addWidget(button_count_up)
label_result.hide()
label_maxflow.hide()
134
table.show()
button_count_up.show()
openFile=QAction(QIcon('ICON/open_icon.png'), 'Open,Ctrl+O ', window)
openFile.setShortcut('Ctrl+O')
openFile.triggered.connect(OpenDialog)
toolbar.addAction(openFile)
def SaveAsDialog():
file_name=QFileDialog.getSaveFileName(window,'Save as
file','/home',filter="txt(*.txt)")
new_file=open(file_name, 'w')
for i in range(table.columnCount()):
for j in range(table.rowCount()):
item=str(table.item(i, j).text())
new_file.write(item + " ")
new_file.write("\n")
new_file.close()
save_asFile=QAction(QIcon('ICON/save_as_icon.png'), 'Save, Ctrl+S', window)
save_asFile.setShortcut('Ctrl+S')
save_asFile.triggered.connect(SaveAsDialog)
toolbar.addAction(save_asFile)
vbox=QVBoxLayout()
window.setLayout(vbox)
vbox.addWidget(toolbar)
label=QLabel(u"Введите количество вершин графа")
vbox.addWidget(label)
hbox=QHBoxLayout()
vbox.addLayout(hbox)
spinbox=QSpinBox(parent=window)
hbox.addWidget(spinbox)
button_ok=QPushButton("OK")
hbox.addWidget(button_ok)
def OK():
label_result.hide()
label_maxflow.hide()
n=spinbox.value()
table.setColumnCount(n)
table.setRowCount(n)
for i in range(n):
for j in range(n):
item=QTableWidgetItem("0")
table.setItem(i,j,item)
table.resizeColumnsToContents()
table.resizeRowsToContents()
135
new_size_h=table.verticalHeader().width() +
table.horizontalHeader().length()+25
new_size_v=table.verticalHeader().length()+200
window.resize(new_size_h, new_size_v)
vbox.addWidget(table)
vbox.addWidget(button_count_up)
table.show()
button_count_up.show()
def COUNT_UP():
new_file=open('matrix_C.txt', 'w')
for i in range(table.columnCount()):
for j in range(table.rowCount()):
item=str(table.item(i, j).text())
new_file.write(item + " ")
new_file.write("\n")
new_file.close()
os.system('python maxflow.py')
file_maxflow = open('MaxFlow.txt','r')
if file_maxflow.read()=="Error":
table.hide()
button_count_up.hide()
label_maxflow.setText(u' Error: Максимальный поток не найден.
Проверьте корректность исходных данных' )
vbox.addWidget(label_maxflow)
label_maxflow.show()
else:
vbox.addWidget(label_result)
label_result.show()
file_F = open('matrix_F.txt','r')
l = []
for line in (file_F):
l.append( [ int(x) for x in line.split() ] )
C = list( l )
print C
n=len(C)
table.setColumnCount(n)
table.setRowCount(n)
for i in range(n):
for j in range(n):
item=QTableWidgetItem(str(C[i][j]))
table.setItem(i,j,item)
table.resizeColumnsToContents()
table.resizeRowsToContents()
new_size_h=table.verticalHeader().width() +
table.horizontalHeader().length()+25
new_size_v=table.verticalHeader().length()+250
window.resize(new_size_h, new_size_v)
vbox.addWidget(table)
file_maxflow=open('MaxFlow.txt','r')
S=file_maxflow.read()
label_maxflow.setText(u'Максимальный поток: ' + S)
136
vbox.addWidget(label_maxflow)
label_maxflow.show()
os.system('shotwell PNG/maxdigraph.png')
QObject.connect(button_ok, SIGNAL("clicked()"), OK)
QObject.connect(button_count_up, SIGNAL("clicked()"), COUNT_UP)
toolbar.show()
window.show()
sys.exit(a.exec_())
Приложение 3
137
Файл «deikstra.py».
#!/usr/bin/python
#coding: utf-8
import sys
import os
import numpy as np
import Queue
import time
start=time.time()
file_maxflow=open('K.txt','r')
k=int(file_maxflow.read())
l = []
for line in open( 'matrix_C.txt' ):
l.append( [ int(x) for x in line.split() ] )
C = list( l )
SIZE=len(C)
D=[[0] for i in range(SIZE)]
V=[[0] for i in range(SIZE)]
temp=0
min_index=0
minimum=0
for i in range(SIZE):
D[i]=10000
V[i]=0
D[0]=0
pred=[[0] for i in range(SIZE)]
q=Queue.LifoQueue()
while True:
min_index=10000
minimum=10000
for i in range(SIZE):
if V[i]==0 and D[i]<minimum:
minimum=D[i]
min_index=i
if min_index !=10000:
for i in range(SIZE):
if C[min_index][i]>0:
temp=minimum+C[min_index][i]
if temp<D[i]:
D[i]=temp
pred[i]=min_index
V[min_index]=1
if not min_index<10000:
break
file_maxflow=open('MinFlow.txt','w')
file_maxflow.write(str(D[k]))
file_maxflow.close()
138
while k!=0:
q.put(k)
k=pred[k]
q.put(0)
file_F=open('MinPut.txt', 'w')
while q.empty()!=True:
file_F.write(str(q.get()) + " ")
file_F.close()
finish=time.time()
print finish-start
Приложение 4
139
Файл «window_deikstra.py».
#!/usr/bin/python
# -*- coding: utf-8 -*#coding: utf-8
import sys
import os
from PyQt4.QtCore import *
from PyQt4.QtGui import *
from PyQt4 import *
a=QApplication(sys.argv)
window=QWidget()
window.move(20,10)
window.setWindowTitle("Deikstra")
toolbar=QToolBar(window)
size=QSize(40,40)
toolbar.setIconSize(size)
#toolbar=addToolBar('ToolBar')
#window.addToolBar(toolbar)
table=QTableWidget()
label_potok=QLabel(u"Найти минимальный поток из вершины 0 в вершину")
spinbox_potok=QSpinBox(parent=window)
button_count_up = QPushButton("Count up")
spinbox_potok.hide()
def OpenDialog():
file_name = QFileDialog.getOpenFileName(window,'Open file',
'/home/deikstra')
l = []
for line in open(file_name):
l.append( [ int(x) for x in line.split() ] )
C = list( l )
print C
n=len(C)
table.setColumnCount(n)
table.setRowCount(n)
for i in range(n):
for j in range(n):
item=QTableWidgetItem(str(C[i][j]))
table.setItem(i,j,item)
table.resizeColumnsToContents()
table.resizeRowsToContents()
headerLabels=[]
for i in range(n):
headerLabels.append(str(i))
table.setHorizontalHeaderLabels(headerLabels)
table.setVerticalHeaderLabels(headerLabels)
140
new_size_h=table.verticalHeader().width() +
table.horizontalHeader().length()+25
new_size_v=table.verticalHeader().length()+200
window.resize(new_size_h, new_size_v)
vbox.addWidget(table)
hbox_potok=QHBoxLayout()
vbox.addLayout(hbox_potok)
hbox_potok.addWidget(label_potok)
hbox_potok.addWidget(spinbox_potok)
vbox.addWidget(button_count_up)
table.show()
button_count_up.show()
label_potok.show()
spinbox_potok.show()
openFile=QAction(QIcon('ICON/open_icon.png'), 'Open,Ctrl+O ', window)
openFile.setShortcut('Ctrl+O')
openFile.triggered.connect(OpenDialog)
toolbar.addAction(openFile)
def SaveAsDialog():
file_name=QFileDialog.getSaveFileName(window,'Save as
file','/home',filter="txt(*.txt)")
new_file=open(file_name, 'w')
for i in range(table.columnCount()):
for j in range(table.rowCount()):
item=str(table.item(i, j).text())
new_file.write(item + " ")
new_file.write("\n")
new_file.close()
save_asFile=QAction(QIcon('ICON/save_as_icon.png'), 'Save, Ctrl+S', window)
save_asFile.setShortcut('Ctrl+S')
save_asFile.triggered.connect(SaveAsDialog)
toolbar.addAction(save_asFile)
vbox=QVBoxLayout()
window.setLayout(vbox)
vbox.addWidget(toolbar)
label=QLabel(u"Введите количество вершин графа")
vbox.addWidget(label)
hbox=QHBoxLayout()
vbox.addLayout(hbox)
spinbox=QSpinBox(parent=window)
hbox.addWidget(spinbox)
button_ok=QPushButton("OK")
hbox.addWidget(button_ok)
141
def OK():
n=spinbox.value()
table.setColumnCount(n)
table.setRowCount(n)
for i in range(n):
for j in range(n):
item=QTableWidgetItem("0")
table.setItem(i,j,item)
table.resizeColumnsToContents()
table.resizeRowsToContents()
headerLabels=[]
for i in range(n):
headerLabels.append(str(i))
table.setHorizontalHeaderLabels(headerLabels)
table.setVerticalHeaderLabels(headerLabels)
new_size_h=table.verticalHeader().width() +
table.horizontalHeader().length()+25
new_size_v=table.verticalHeader().length()+200
window.resize(new_size_h, new_size_v)
vbox.addWidget(table)
vbox.addWidget(label_potok)
table.show()
button_count_up.show()
hbox_potok=QHBoxLayout()
vbox.addLayout(hbox_potok)
hbox_potok.addWidget(label_potok)
hbox_potok.addWidget(spinbox_potok)
vbox.addWidget(button_count_up)
table.show()
button_count_up.show()
label_potok.show()
spinbox_potok.show()
def COUNT_UP():
k=spinbox_potok.value()
file_maxflow=open('K.txt','w')
file_maxflow.write(str(k))
file_maxflow.close()
new_file=open('matrix_C.txt', 'w')
for i in range(table.columnCount()):
for j in range(table.rowCount()):
item=str(table.item(i, j).text())
new_file.write(item + " ")
new_file.write("\n")
new_file.close()
os.system('python deikstra.py')
os.system('python window_result_deikstra.py')
label_potok.show()
spinbox_potok.show()
142
QObject.connect(button_ok, SIGNAL("clicked()"), OK)
QObject.connect(button_count_up, SIGNAL("clicked()"), COUNT_UP)
toolbar.show()
window.show()
sys.exit(a.exec_())
Приложение 5
Файл «window_result_deikstra.py».
143
#!/usr/bin/python
# -*- coding: utf-8 -*#coding: utf-8
import sys
import os
from PyQt4.QtCore import *
from PyQt4.QtGui import *
from PyQt4 import *
a=QApplication(sys.argv)
window=QWidget()
window.move(50,50)
window.setWindowTitle("Result")
hbox=QHBoxLayout()
window.setLayout(hbox)
file_D = open('K.txt','r')
k = file_D.read()
file_D = open('MinFlow.txt','r')
D = file_D.read()
file_D = open('MinPut.txt','r')
l = []
for line in (file_D):
l=line
label_maxflow=QLabel()
label_maxflow.setText(u'Минимальный поток из вершины 0 в вершину ' + str(k)
+ ' = ' + D + u'\n Минимальный путь: ' + l)
label_maxflow.show()
#window.show()
sys.exit(a.exec_())
Приложение 6
144
Файл «n_min.py».
#!/usr/bin/python
#coding: utf-8
import numpy as np
import pylab as pl
import sympy as sp
import time
import matplotlib.pyplot as plt
start=time.time()
l = []
for line in open( 'matrix_C.txt' ):
l.append( [ int(x) for x in line.split() ] )
matrix = list( l )
height=len(matrix)
width=len(matrix[1])
if height > width:
for i in range(height):
matrix[i].append(0)
elif width > height:
d=[0 for k in range(width)]
matrix.append(d)
height=len(matrix)
width=len(matrix[1])
u=[0 for i in range(height)]
v=[0 for i in range(width)]
markIndices=[-1 for i in range(width)]
for i in range(height):
#print 'i= ', i
links=[-1 for k in range(width)]
mins=[100 for k in range(width)]
visited=[0 for k in range(width)]
markedI=i
#print 'markedI1= ', markedI
markedJ=-1
j=0
while markedI!=-1:
j=-1
for j1 in range(width):
#print 'CIKL 1'
#print 'j1= ', j1
if visited[j1]==0:
#print 'DA 1'
#print 'markedI= ', markedI
#print matrix[markedI][j1], ' - ', u[markedI], ' - ', v[j1]
if matrix[markedI][j1]-u[markedI]-v[j1]<mins[j1]:
#print 'DA 2'
mins[j1]=matrix[markedI][j1]-u[markedI]-v[j1]
#print 'mins= ', mins
145
links[j1]=markedJ
#print 'links= ', links
if j==-1 or mins[j1]<mins[j]:
#print 'DA 3'
j=j1
#print 'j= ',j
delta=mins[j]
#print 'delta= ', delta
for j1 in range(width):
#print 'CIKL 2'
#print 'j1= ', j1
if visited[j1]==1:
#print 'DA 4'
#print 'markIndices[j1]= ', markIndices[j1]
u[markIndices[j1]]+=delta
#print 'u= ', u
v[j1]-=delta
#print 'v= ', v
else:
#print 'NET'
mins[j1]-=delta
#print 'mins= ', mins
u[i]+=delta
#print 'u2= ', u
visited[j]=1
#print 'visited= ', visited
markedJ=j
#print 'markIndices ', markIndices
markedI=markIndices[j]
#print 'markedI= ', markedI
#print markIndices
#print 'l= ', links
while links[j]!=-1:
#print 'j=', j
markIndices[j]=markIndices[links[j]]
j=links[j]
markIndices[j]=i
#print markIndices
file_F=open('Naz.txt', 'w')
for j in range(width):
if markIndices[j]!=-1:
#print markIndices[j], ' -> ', j
file_F.write(str(markIndices[j]) + " " + str(j) + '\n')
file_F.close()
#MinFunk=0
#for i in range(height):
#MinFunk+=matrix[i][markIndices[i]]
#print MinFunk
#print
MinFunk=0
for j in range(width):
MinFunk+=matrix[markIndices[j]][j]
#print matrix[markIndices[j]][j]
146
#print
#print MinFunk
file_F=open('MinNaz.txt', 'w')
file_F.write(str(MinFunk))
file_F.close()
finish=time.time()
print finish-start
Приложение 7
147
Файл «n_max.py».
#!/usr/bin/python
#coding: utf-8
import numpy as np
import pylab as pl
import sympy as sp
import time
import matplotlib.pyplot as plt
start=time.time()
l = []
for line in open( 'matrix_C.txt' ):
l.append( [ int(x) for x in line.split() ] )
matrix_is = list( l )
matrix_is=[[10,20,12,5],[3,14,9,1],[13,8,6,9],[7,15,6,9]]
height=len(matrix_is)
width=len(matrix_is[1])
matrix=[[0]*width for k in range(height)]
max_el=max([e for elem in matrix_is for e in elem])
for i in range(height):
for j in range(width):
matrix[i][j]=max_el-matrix_is[i][j]
if height > width:
for i in range(height):
matrix_is[i].append(0)
matrix[i].append(0)
elif width > height:
d=[0 for k in range(width)]
matrix_is.append(d)
matrix.append(d)
height=len(matrix_is)
width=len(matrix_is[1])
u=[0 for i in range(height)]
v=[0 for i in range(width)]
markIndices=[-1 for i in range(width)]
for i in range(height):
#print 'i= ', i
links=[-1 for k in range(width)]
mins=[100 for k in range(width)]
visited=[0 for k in range(width)]
markedI=i
#print 'markedI1= ', markedI
markedJ=-1
j=0
while markedI!=-1:
j=-1
for j1 in range(width):
148
#print 'CIKL 1'
#print 'j1= ', j1
if visited[j1]==0:
#print 'DA 1'
#print 'markedI= ', markedI
#print matrix[markedI][j1], ' - ', u[markedI], ' - ', v[j1]
if matrix[markedI][j1]-u[markedI]-v[j1]<mins[j1]:
#print 'DA 2'
mins[j1]=matrix[markedI][j1]-u[markedI]-v[j1]
#print 'mins= ', mins
links[j1]=markedJ
#print 'links= ', links
if j==-1 or mins[j1]<mins[j]:
#print 'DA 3'
j=j1
#print 'j= ',j
delta=mins[j]
#print 'delta= ', delta
for j1 in range(width):
#print 'CIKL 2'
#print 'j1= ', j1
if visited[j1]==1:
#print 'DA 4'
#print 'markIndices[j1]= ', markIndices[j1]
u[markIndices[j1]]+=delta
#print 'u= ', u
v[j1]-=delta
#print 'v= ', v
else:
#print 'NET'
mins[j1]-=delta
#print 'mins= ', mins
u[i]+=delta
#print 'u2= ', u
visited[j]=1
#print 'visited= ', visited
markedJ=j
#print 'markIndices ', markIndices
markedI=markIndices[j]
#print 'markedI= ', markedI
#print markIndices
#print 'l= ', links
while links[j]!=-1:
#print 'j=', j
markIndices[j]=markIndices[links[j]]
j=links[j]
markIndices[j]=i
#print markIndices
file_F=open('Naz.txt', 'w')
for j in range(width):
if markIndices[j]!=-1:
#print markIndices[j], ' -> ', j
file_F.write(str(markIndices[j]) + " " + str(j) + '\n')
file_F.close()
149
#MaxFunk=0
#for i in range(height):
#MaxFunk+=matrix[i][markIndices[i]]
#print MaxFunk
#print
MaxFunk=0
for j in range(width):
MaxFunk+=matrix_is[markIndices[j]][j]
#print matrix_is[markIndices[j]][j]
#print
#print MaxFunk
file_F=open('MaxNaz.txt', 'w')
file_F.write(str(MaxFunk))
file_F.close()
finish=time.time()
print finish-start
Приложение 8
Файл «window_naz.py».
150
#!/usr/bin/python
# -*- coding: utf-8 -*#coding: utf-8
import sys
import os
from PyQt4.QtCore import *
from PyQt4.QtGui import *
from PyQt4 import *
a=QApplication(sys.argv)
window=QWidget()
window.move(20,10)
window.setWindowTitle("Naz")
toolbar=QToolBar(window)
size=QSize(40,40)
toolbar.setIconSize(size)
table=QTableWidget()
button_min = QPushButton("min")
button_max = QPushButton("max")
def OpenDialog():
file_name = QFileDialog.getOpenFileName(window,'Open file', '/home')
l = []
for line in open(file_name):
l.append( [ int(x) for x in line.split() ] )
C = list( l )
print C
height=len(C)
width=len(C[1])
table.setRowCount(height)
table.setColumnCount(width)
for i in range(height):
for j in range(width):
item=QTableWidgetItem(str(C[i][j]))
table.setItem(i,j,item)
table.resizeColumnsToContents()
table.resizeRowsToContents()
headerLabels=[]
for i in range(height):
headerLabels.append(str(i+1))
table.setHorizontalHeaderLabels(headerLabels)
for j in range(width):
headerLabels.append(str(j+1))
table.setVerticalHeaderLabels(headerLabels)
new_size_h=table.verticalHeader().width() +
table.horizontalHeader().length()+25
new_size_v=table.verticalHeader().length()+200
window.resize(new_size_h, new_size_v)
151
vbox.addWidget(table)
hbox_potok=QHBoxLayout()
vbox.addLayout(hbox_potok)
vbox.addWidget(button_min)
vbox.addWidget(button_max)
table.show()
button_min.show()
button_max.show()
openFile=QAction(QIcon('ICON/open_icon.png'), 'Open,Ctrl+O ', window)
openFile.setShortcut('Ctrl+O')
openFile.triggered.connect(OpenDialog)
toolbar.addAction(openFile)
def SaveAsDialog():
file_name=QFileDialog.getSaveFileName(window,'Save as
file','/home',filter="txt(*.txt)")
new_file=open(file_name, 'w')
for i in range(table.columnCount()):
for j in range(table.rowCount()):
item=str(table.item(i, j).text())
new_file.write(item + " ")
new_file.write("\n")
new_file.close()
save_asFile=QAction(QIcon('ICON/save_as_icon.png'), 'Save, Ctrl+S', window)
save_asFile.setShortcut('Ctrl+S')
save_asFile.triggered.connect(SaveAsDialog)
toolbar.addAction(save_asFile)
vbox=QVBoxLayout()
window.setLayout(vbox)
vbox.addWidget(toolbar)
label=QLabel(u"Введите количество назначений и исполнителей")
vbox.addWidget(label)
hbox=QHBoxLayout()
vbox.addLayout(hbox)
spinbox_naz=QSpinBox(parent=window)
hbox.addWidget(spinbox_naz)
spinbox_isp=QSpinBox(parent=window)
hbox.addWidget(spinbox_isp)
button_ok=QPushButton("OK")
hbox.addWidget(button_ok)
def OK():
height=spinbox_naz.value()
width=spinbox_isp.value()
152
table.setRowCount(height)
table.setColumnCount(width)
for i in range(height):
for j in range(width):
item=QTableWidgetItem("0")
table.setItem(i,j,item)
table.resizeColumnsToContents()
table.resizeRowsToContents()
headerLabels=[]
for i in range(height):
headerLabels.append(str(i+1))
table.setHorizontalHeaderLabels(headerLabels)
for j in range(width):
headerLabels.append(str(j+1))
table.setVerticalHeaderLabels(headerLabels)
new_size_h=table.verticalHeader().width() +
table.horizontalHeader().length()+25
new_size_v=table.verticalHeader().length()+200
window.resize(new_size_h, new_size_v)
vbox.addWidget(table)
table.show()
button_min.show()
button_max.show()
hbox_potok=QHBoxLayout()
vbox.addLayout(hbox_potok)
vbox.addWidget(button_min)
vbox.addWidget(button_max)
table.show()
button_min.show()
button_max.show()
def MIN():
#table.hide()
#button_min.hide()
#button_max.hide()
new_file=open('matrix_C.txt', 'w')
for i in range(table.rowCount()):
for j in range(table.columnCount()):
item=str(table.item(i,j).text())
new_file.write(item + " ")
new_file.write("\n")
new_file.close()
os.system('python n_min.py')
os.system('python window_result_naz_min.py')
#file_Naz = open('Naz.txt','r')
#Naz = file_Naz.read()
#file_Naz = open('MinNaz.txt','r')
#l = []
153
#for line in (file_Naz):
#l=line
#label_minflow=QLabel()
#label_minflow.setText(Naz + u'\n ' + l)
#vbox.addWidget(label_minflow)
#label_minflow.show()
def MAX():
#table.hide()
#button_min.hide()
#button_max.hide()
new_file=open('matrix_C.txt', 'w')
for i in range(table.rowCount()):
for j in range(table.columnCount()):
item=str(table.item(i,j).text())
new_file.write(item + " ")
new_file.write("\n")
new_file.close()
os.system('python n_max.py')
os.system('python window_result_naz_max.py')
#file_Naz = open('Naz.txt','r')
#Naz = file_Naz.read()
#file_Naz = open('MaxNaz.txt','r')
#l = []
#for line in (file_Naz):
#l=line
#label_maxflow=QLabel()
#label_maxflow.setText(Naz + u'\n ' + l)
#vbox.addWidget(label_maxflow)
#label_maxflow.show()
QObject.connect(button_ok, SIGNAL("clicked()"), OK)
QObject.connect(button_min, SIGNAL("clicked()"), MIN)
QObject.connect(button_max, SIGNAL("clicked()"), MAX)
toolbar.show()
window.show()
sys.exit(a.exec_())
Приложение 9
Файл «window_result_naz_min.py».
#!/usr/bin/python
154
# -*- coding: utf-8 -*#coding: utf-8
import sys
import os
from PyQt4.QtCore import *
from PyQt4.QtGui import *
from PyQt4 import *
a=QApplication(sys.argv)
window=QWidget()
window.move(50,50)
window.setWindowTitle("Result")
hbox=QHBoxLayout()
window.setLayout(hbox)
file_Naz = open('Naz.txt','r')
L=file_Naz.read()
file_Naz = open('MinNaz.txt','r')
Naz = file_Naz.read()
label_minflow=QLabel()
label_minflow.setText(u'Назначение -> Исполнитель\n'+ L + u'\n Минимальные
затраты\n ' + Naz)
hbox.addWidget(label_minflow)
label_minflow.show()
window.show()
sys.exit(a.exec_())
Приложение 10
Файл «window_result_naz_max.py».
155
#!/usr/bin/python
# -*- coding: utf-8 -*#coding: utf-8
import sys
import os
from PyQt4.QtCore import *
from PyQt4.QtGui import *
from PyQt4 import *
a=QApplication(sys.argv)
window=QWidget()
window.move(50,50)
window.setWindowTitle("Result")
hbox=QHBoxLayout()
window.setLayout(hbox)
file_Naz = open('Naz.txt','r')
L=file_Naz.read()
file_Naz = open('MaxNaz.txt','r')
Naz = file_Naz.read()
label_minflow=QLabel()
label_minflow.setText(u'Назначение -> Исполнитель\n'+ L + u'\n Максимальная
прибыль\n ' + Naz)
hbox.addWidget(label_minflow)
label_minflow.show()
window.show()
sys.exit(a.exec_())
Приложение 11
Файл «WINDOW.py».
156
#!/usr/bin/python
# -*- coding: utf-8 -*#coding: utf-8
import sys
import os
from PyQt4.QtCore import *
from PyQt4.QtGui import *
from PyQt4 import *
a=QApplication(sys.argv)
window=QWidget()
window.move(20,10)
window.setWindowTitle("Algoritm")
#button_MF= QPushButton("MaxFlow")
#button_D = QPushButton("Deikstra")
#button_N = QPushButton('Naznacheniya')
hbox=QHBoxLayout()
window.setLayout(hbox)
button_MF= QPushButton("MaxFlow")
button_D = QPushButton("Deikstra")
button_N = QPushButton('Naznacheniya')
hbox.addWidget(button_MF)
hbox.addWidget(button_D)
hbox.addWidget(button_N)
button_MF.show()
button_D.show()
button_N.show()
def MF():
os.system('python window_maxflow.py')
def D():
os.system('python window_deikstra.py')
def N():
os.system('python window_naz.py')
QObject.connect(button_MF, SIGNAL("clicked()"), MF)
QObject.connect(button_D, SIGNAL("clicked()"), D)
QObject.connect(button_N, SIGNAL("clicked()"), N)
window.show()
sys.exit(a.exec_())
Приложение 12
Файл «randomgraph.py».
157
#!/usr/bin/python
#coding: utf-8
import random
n=300
C=[[0]*n for i in range(n)]
for i in range(n):
for j in range (n):
w=random.choice(['0','1'])
if w=='0':
C[i][j]=0
else:
C[i][j]=random.randint(0,10)
if i==j or j==0 or i==n-1:
C[i][j]=0
istok=0
stok=0
k=0
i=0
for j in range(n):
istok+=C[i][j]
j=n-1
for i in range(n):
stok+=C[i][j]
if istok>stok:
k=istok-stok
j=n-1
for i in range(0,n):
if C[i][j]==0:
C[i][j]=k
break
elif stok>istok:
k=stok-istok
i=0
for j in range(1,n-1):
if C[i][j]==0:
C[i][j]=k
break
File=open('matrix_C.txt', 'w')
for i in range(n):
for j in range(n):
File.write(str(C[i][j]) + " ")
File.write("\n")
File.close()
1/--страниц
Пожаловаться на содержимое документа