МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение
высшего профессионального образования
«Нижегородский государственный университет им. Н. И. Лобачевского»
Факультет вычислительной математики и кибернетики
Кафедра информатики и автоматизации
научных исследований
Методические указания по выполнению курсовых работ по курсу
«Управление информационными ресурсами»
специальность «
Прикладная информатика»
Учебно-методическое пособие
Рекомендовано методической комиссией факультета вычислительной математики и кибернентики для студентов ННГУ, обучающихся по направлению подготовки 080800 «Прикладная информатика» и специальности 080801 «Прикладная информатика»
Н.Новгород, 2010
Методические указания по выполнению курсовых работ по курсу «Управление информационными ресурсами» для студентов факультета ВМК специальности «Прикладная информатика./ Нижегородский государственный университет, 2010, 22 c.
В учебно-методическом пособии приведены известные задачи оптимизации на графах и некоторые методы их решения. При этом методы подобраны таким образом, чтобы процесс поиска решения легко отображался на самом графе или в виде дерева поиска решений. В рамках данного курса студенты учатся применять объектно-ориентированный подход в программировании для визуализации методов оптимизации, а также для создания обучающей программы. Методические указания содержат описание алгоритмов, используемых при выполнении курсовых работ, а также подробное описание требуемой функциональности демонстрационного и обучающего режимов программы.
Методическое пособие подготовлено к.т.н. Неймарк Е.А.
Рецензент д.т.н., проф. Турлапов В.Е.
Введение
Данная часть курса является продолжением изучения объектно-ориентированного подхода в программировании и основ алгоритмизации.
В методической разработке студентам предлагается ознакомиться с некоторыми методами поиска решений задач оптимизации. При этом рамках данного курса рассматриваются только те методы, в которых процесс поиска решения легко представим при помощи дерева.
В результате выполнения курсовой работы каждая задача должна иметь два режима выполнения: демонстрационный и обучающий. Демонстрационный режим пошагово отображает процесс построения решения задачи. Обучающий режим направлен на обучение пользователя решению задачи при помощи данного метода. Этот режим предполагает интерактивное участие пользователя, выбор параметров, а также выбор ребра или вершины для следующего шага алгоритма. Программа должна проверить правильность выбора и в случае неправильного выбора уведомить пользователя об этом.
Структура каждого параграфа состоит из постановки задачи, описания алгоритма решения задачи и указаний к выполнению демонстрационного и обучающего режимов.
Целью данной работы является обучение использованию объектно-ориентированного подхода в программировании, построению графического интерактивного интерфейса. Кроме того, важной частью работы является ознакомление с различными задачами на графах и методами их решения, а также перевод алгоритмов решения задачи в программную реализацию.
Общие методические указания к выполнению работы
В интерфейсе демонстрационной части программы необходимо наличие следующих блоков:
1. Панель с демонстрацией текущего решения (отображение графа)
2. Кнопка начала демонстрации и(или) кнопка пошагового выполнения алгоритма
3. Выделение цветом параметров, измененных на текущем шаге алгоритма (веса, вершины, ребра)
4. Области для ввода параметров задачи
Демонстрационная часть пошагово показывает процесс построения (нахождения) решения при помощи заданного алгоритма. Для правильного понимания процесса поиска решения необходимо отображение пометок (весов ребер и т.п.), на основании оценки которых делается следующий шаг алгоритма.
Обучающая часть программы позволяет пользователю понять принцип работы алгоритма и обучиться решению задачи при помощи заданного метода. Эта часть программы является интерактивной, то есть пользователь должен иметь возможность производить изменения, необходимые для поиска решения на текущем шаге: помечать вершины или ребра, изменять веса. В случае правильного действия пользователя, данное изменение должно приниматься и отображаться соответствующим образом на панели отображения решения задачи. Если действие пользователя не правильно, то пользователь должен получить сообщение о неправильном действии и желательно подсказку по какому принципу на текущем шаге выбирается вершина (ребро) или изменяются веса (метки вершин).
Все пометки, которые отображаются в процессе решения в демонстрационной части программы должны также отображаться в обучающем режиме.
1. Построение минимального остова графа
Постановка задачи
В рамках данного курса мы будем рассматривать только связные графы.
Рассмотрим граф G(
V,
E)
, V
– это множество вершин графа G
, E
– множество ребер. Остовом графа G(
V,
E)
, является дерево , . Минимальный остов это остов графа, имеющий минимальный суммарный вес входящих ребер.
Методы решения
Предлагаемые алгоритмы построения минимального остова относятся к жадным методам поиска решения.
- Алгоритм Краскала
Более подробно с данным подходом можно ознакомиться в работе [2].
Шаг 1. Граф Т
является вполне несвязным графом, содержащим n
вершин исходного графа G
(Т
– пустой граф).
Шаг 2. Упорядочиваем ребра графа G
в порядке неубывания весов.
Шаг 3. Начав с первого ребра в списке ребер, добавлять ребра в Т
таким образом, чтобы добавление ребра не приводило к появлению цикла.
Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в графе Т
не станет равным n-1
. Полученное дерево является минимальным остовом графа G(
V,
E)
.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Для каждого ребра отображать его вес. Добавляемое на текущем шаге в дерево ребро, выделять цветом. Отображать текущий вес остова.
Режим обучения:
Пользователь выбирает следующее добавляемое в остов ребро, если ребро выбрано правильно, что оно выделяется цветом, если не правильно, то пользователь предупреждается об этом.
- Алгоритм Прима
Более подробно с данным методом можно ознакомиться в работе [2].
Здесь и далее обозначает множество вершин, смежных с .
Шаг 1. Произвольно выбираем вершину , - множество вершин в строящемся остове .
Шаг 2. Для каждой вершины находим вершину такую, что и приписываем вершине пометку [], если такой вершины нет, то есть , приписываем вершине метку [0,].
Шаг 3. Выбрать такую вершину , для которой . Добавляем ее в дерево {.
Если |, то остановиться, полученное дерево – минимальный остов.
Шаг 4. Для всех , для которых обновить метки.
Если , то , . Вернуться к шагу 3.
Иначе вернуться к шагу 3.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Для каждой вершины отображать пометку []. Добавляемое в остов на текущем шаге ребро , выделять цветом. Отображать текущий вес остова.
Режим обучения:
Пользователь выбирает следующее добавляемое в остов ребро, если ребро выбрано правильно, то оно выделяется цветом, если не правильно, то пользователь предупреждается об этом. Пометки пересчитываются программой.
2. Задача о ранце
Постановка задачи
Задача о ранце является одной из классических комбинаторных задач оптимизации, в рамках данного курса мы будем рассматривать только одномерную задачу о ранце. Содержательная постановка одномерной задачи: дан набор из n
предметов, каждый из которых имеет цену ci
и вес wi
(i
=1,2…n
), в ранец, имеющий грузоподъемность Wmax
, нужно загрузить предметы таким образом, чтобы суммарная ценность предметов в рюкзаке была максимальной. Математическая формулировка задачи представлена в (1), также эта задача называется задачей о 0-1 ранце или целочисленной задачей о ранце (иногда также задачей о рюкзаке).
|
|
(
|
|
|
Задача о ранце относится к классу NP-трудных задач, следовательно не имеет алгоритма, находящего оптимальное решение задачи за время, полиномиально зависящее от числа входных параметров, то есть в данном случае от числа предметов в наборе – n
.
Методы решения
- Метод ветвей и границ
Основной идеей данного метода является ограничение полного перебора за счет разбиения множества решений на подмножества, получения оценок содержащихся в подмножестве решений и отбрасывании непереспективных подмножеств. Более подробно этот метод можно посмотреть в работах [4, 5, 6].
Применительно к задаче о ранце, дихотомическое разбиение на подмножества осуществляется по принципу присутствия/отсутствия текущего предмета в ранце. Соответственно, все множество решений делится на решения, содержащие текущий предмет и не содержащие его. Оценка решений, содержащихся в подмножестве и приведение вида задачи, производится на основании теоремы Данцига [6].
Теорема (правило) Данцига:
Пусть переменные х
j
пронумерованы так, что , где . Тогда оптимальное решение имеет вид:
|
|
(
|
где s
определяется из условия:
|
|
(
|
Приведение задачи осуществляется согласно правилу Данцига, то есть переменные х
j
перенумеровываются так, что , где .
В качестве вершины ветвления выбирается предмет с номером s
.
Верхняя оценка подмножества получается при добавлении в решение дробной части предмета с номером s
.
|
|
(
|
Нижняя оценка – при подсчете цен только целых предметов
|
|
(
|
Шаг 1. Приводим задачу согласно правилу Данцига.
Шаг 2. Выбираем вершину ветвления согласно условию (3).
Шаг 3. Получаем верхнюю и нижнюю оценки задачи на текущем шаге по формулам (4) и (5). Исключаем из дальнейшего рассмотрения ветви, для которых полученная верхняя оценка меньше или равна нижней оценке для некоторой другой ветви.
Ветвление также не проводится если верхняя и нижняя оценка в одном направлении совпали – это значит, что по данному направлению достигнут максимум целочисленной задачи.
Шаг 4. Производим процедуру ветвления: для одной ветви устанавливаем , для другой . Для каждого направления повторяем шаги 2-4.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Отображать приведенную задачу. Помечать вершины ветвления соответствующим номером переменной. Для каждой вершины ветвления отображать верхнюю и нижнюю оценки. Помечать ребра ветвления цифрами или цветом (например, если переменная добавляется в решение , то ребро имеет пометку 1, нет – 0). Тупиковые вершины помечать цветом. Отображать оптимальное решение.
Режим обучения:
Пользователь выбирает вершину ветвления (номер переменной), если вершина выбрана правильно, то для идущих из нее ветвей вычисляются верхняя и нижняя оценки, если не правильно, то пользователь предупреждается об этом. Пользователь также производит отбрасывание неперспективных направлений ветвления, если отбрасывание произведено не правильно или пользователь продолжает ветвление в неперспективном направлении, то он предупреждается об этом. Пользователь выбирает ветку с оптимальным решением.
- Метод динамического программирования
Метод динамического программирования близок к методу ветвей и границ в том смысле, что также ограничивает перебор решений. Для задачи о ранце процесс поиска решения при помощи динамического программирования является псевдополиномиальным.
Основная идея этого метода состоит в составлении рекуррентных соотношений согласно принципу оптимальности Беллмана: завершающая часть оптимального решения также должна быть оптимальной. Более подробно этот метод можно посмотреть в работах [3, 4, 5, 6].
Рекуррентное соотношение для задачи о ранце выглядит следующим образом:
| , |
(
|
При граничных условиях:
|
|
(7) |
Значение, полученное в результате вычисления соотношения (6), является оптимальным решением исходной задачи.
Часто процедура поиска решения при помощи динамического программирования записывается в табличном виде, однако в данной работе будем использовать для отображения процесса дерево.
Алгоритм состоит в последовательном вычислении соотношений (6).
Указания по отображению процесса поиска решения:
Режим демонстрации:
Отображать задачу. Вершины ветвления (кроме начальной) помечать соответствующим номером добавляемой в решение переменной . Помечать ребра значениями [, ] или 0, если достигнуты граничные условия. Ветви с наибольшей ценностью помечать цветом. Отображать оптимальное решение.
Режим обучения:
Пользователь помечает вершины ветвления, программа проставляет метки на ребрах. Если вершина выбрана не правильно, то пользователь предупреждается об этом. Пользователь выбирает ветку с оптимальным решением.
3. Задача коммивояжера
Постановка задачи
Еще одной классической комбинаторной задачей оптимизации является задача коммивояжера.
|
|
(
|
| (
|
|
|
|
Задача формулируется так: в полном взвешенном графе с n
вершинами необходимо найти гамильтонов цикл с минимальным суммарным весом входящих ребер. Вес ребра (
i,
j)
, соединяющего вершины с номерами i
и j
обозначается как ‑ это расстояние между вершинами : . Математическая формулировка задачи представлена в формулах (8) и (9), причем условие (9) является условием отсутствия повторений в решении, то есть наличием единственного цикла.
Задача коммивояжера является NP-трудной задачей.
Поскольку решение исходной задачи является циклом, то окончательное решение не может быть представлено в виде дерева. Поэтому в рамках данного курса при поиске решения исходной задачи ребро из конечной вершины в начальную не будет отображаться, но будет учитываться при получении окончательного веса решения.
Методы решения
Метод ближайшего соседа и метод ближайшего города относятся к жадным методам поиска решения. Эти методы предназначены для работы на графах, в которых выполняется неравенство треугольника (в частности для евклидовой задачи коммивояжера), только в этом случае гарантируется ε‑оптимальность получаемого решения. [5].
- Метод ближайшего соседа
Более подробно данный метод и оценку получаемого решения можно посмотреть в работе
[
5].
Шаг 1. Произвольно выбираем вершину убираем ее из исходного множества вершин , - множество вершин в строящемся гамильтоновом цикле, - множество ребер в гамильтоновом цикле.
Шаг 2. Находим вершину такую, что . Добавляем ребро в гамильтонов цикл , обозначаем , .
Шаг 3. Повторяем Шаг 2 до тех пор пока .
Указания по отображению процесса поиска решения:
Режим демонстрации:
Для каждой вершины из текущего множества отображать расстояние . Добавляемое в цикл на текущем шаге ребро , выделять цветом. Отображать текущую длину пути.
Режим обучения:
Пользователь выбирает следующее добавляемое в цикл ребро, если ребро выбрано правильно, что оно выделяется цветом, если не правильно, то пользователь предупреждается об этом.
- Метод ближайшего города
Более подробно данный метод и оценку получаемого решения можно посмотреть в работе [5].
Шаг 1. S=1, произвольно выбираем вершину убираем ее из исходного множества вершин , - множество вершин в строящемся гамильтоновом цикле, - множество ребер в гамильтоновом цикле.
Шаг 2. Для каждой вершины находим вершину такую, что и приписываем вершине пометку [].
Шаг 3. Выбрать такую вершину , для которой . Добавляем в д
Шаг 4. Повторяем шаги 2 и 3 тех пор пока .
Указания по отображению процесса поиска решения:
Режим демонстрации:
Для каждой вершины из текущего множества отображать пометку []. Добавляемое в цикл на текущем шаге ребро , выделять цветом. Отображать текущую длину цикла.
Режим обучения:
Пользователь выбирает следующее добавляемое в цикл ребро, если ребро выбрано правильно, что оно выделяется цветом, если не правильно, то пользователь предупреждается об этом.
- Решение задачи коммивояжера на основе построения минимального остова
Более подробно с данным методом можно ознакомиться в работе [2].
Шаг 1. Выбираем шаг штрафования F.
Шаг 2. По матрице весов , построить минимальный остов (алгоритмы см. выше).
Шаг 3. Если степень вершины , то полученный остов является гамильтоновым путем, выход.
Штрафуем все вершины, имеющие степени больше двух: . переход на Шаг 2.
Замечание:
для упрощения работы алгоритма можно изначально выбрать начальную и конечную вершину гамильтонова пути, для этого ко всем элементам матрицы , , в соответствующих строках и столбцах прибавляется достаточно большое число, скажем .
Указания по отображению процесса поиска решения:
Режим демонстрации:
На каждом шаге: отображать полученный остов (сам процесс построения не отображать), выделять цветом штрафуемые вершины, отображать веса ребер.
Режим обучения:
На начальном этапе пользователь задает значение штрафа. В построенном остове пользователь отмечает вершины, которые необходимо штрафовать. Если вершина выбрана правильно, то она выделяется цветом и соответственно изменяются веса смежных ребер. Если вершина выбрана не правильно, то пользователь предупреждается об этом.
- Метод на основе построения эйлерова цикла в минимальном остове
Более подробно с данным методом можно ознакомиться в работах [1, 3].
Шаг 1. Построить минимальный остов.
Шаг 2. Строим кратчайшее эйлерово дерево путем удвоения каждого ребра остова.
Шаг 3. s=1, выбрать произвольную вершину , добавить вершину в цикл , пометить вершину как пройденную поместить в стек: .
Шаг 4. Если s=n, выход.
Иначе, выбираем смежную с вершину , для которой , исключаем ребро из эйлерова дерева, , , , поместить в стек .
Если все смежные вершины посещены, то достаем вершину из стека , , переходим на Шаг 4.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Отобразить полученный остов (сам процесс построения не отображать). На каждом шаге: выделять цветом добавляемое в цикл ребро, отображать содержимое стека и текущую длину строящегося цикла.
Режим обучения:
Пользователь выбирает добавляемые в цикл вершины. Если вершина выбрана правильно, то добавляемое ребро выделяется цветом, иначе пользователь предупреждается о неправильном выборе.
- Метод ветвей и границ
Применение данного метода к задаче коммивояжера, будет отличаться принципом, по которому осуществляется ветвление, и методами получения верхней и нижней оценок. В данном случае будет рассмотрено не дихотомическое ветвление, а полный перебор добавляемых вершин. В качестве начальной вершины ветвления можно выбрать произвольную (например, первую).
Нижняя оценка может быть получена следующим образом:
|
|
(10) |
Верхняя – как решение задачи методом ближайшего соседа (алгоритм см. выше).
Шаг 1. Производим ветвление от вершины таким образом, чтобы не производить циклов.
Шаг 2. Для каждой ветки, соответствующей добавлению в маршрут ребра ( вычисляем верхнюю и нижнюю оценку. .
Шаг 3. Если в существует направление , нижняя оценка в котором больше верхней в направлении : , то направление можно исключить из дальнейшего рассмотрения.
Шаг 4. Повторяем шаги 1-3 до полного построения маршрута.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Отображать матрицу переходов. Вершины ветвления помечать соответствующим номером добавляемой в решение переменной . Для каждой вершины ветвления отображать верхнюю и нижнюю оценки (эти оценки можно расставлять не у вершины, а у ребра) . Отбрасываемые ветви помечать цветом.
Режим обучения:
Пользователь помечает вершины ветвления и отбрасывает неперспективные ветки. Если ветвление идет в не правильном направлении, то пользователь предупреждается об этом. Пользователь выбирает ветку с оптимальным решением.
- Метод динамического программирования
Обозначим через - длину пути, проходящего по всем вершинам множества , с началом в вершине с номером i
и концом в вершине с номером 1. Рекуррентное соотношение для задачи коммивояжера выглядит следующим образом:
| , |
(
|
При граничных условиях:
|
|
(12) |
Значение, полученное в результате вычисления соотношения (11), является оптимальным решением исходной задачи.
Алгоритм состоит в последовательном вычислении соотношений (11), процесс поиска решения отображается в виде дерева.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Отображать задачу. Вершины ветвления помечать соответствующим номером добавляемой в решение переменной . Помечать ребра значениями или , если достигнуты граничные условия. Ветви с наименьшей суммарной длиной помечать цветом.
Режим обучения:
Пользователь помечает вершины ветвления и расставляет расстояния на ребрах. Если метки расставляются не правильно или выбрана не правильная вершина ветвления, то пользователь предупреждается об этом. Пользователь выбирает ветку с оптимальным решением.
4. Задача построения максимального потока
Постановка задачи
Дана сеть G(
V,
E)
с источником s
и стоком t
. Каждое ребро имеет заданную пропускную способность . В этой сети необходимо найти максимальное значение потока, проходящего из источника s
в сток t
. Задаче о максимальном потоке соответствует задаче о минимальном разрезе. В задаче о минимальном разрезе необходимо найти такой разрез графа G(
V,
E)
: , имеющий минимальное значение суммы пропускных способностей дуг соединяющих и . Величина максимального потока равна величине минимального разреза (теорему, доказывающую это утверждение, можно найти в работе [2]).
Методы решения
Метод Форда-Фалкерсона (иногда он называется методом меток) является первым из предложенных методов поиска максимального потока и базисным для многих алгоритмов, предложенных позднее. Более подробно с данным методом можно ознакомиться в работах [2, 3].
- Алгоритм Форда-Фалкерсона
Из источника осуществляется поиск до тех пор, пока не будет достигнут сток. По найденному пути осуществляется насыщение потока, величина потока из вершины в вершину обозначается как . В ходе алгоритма каждой вершине присваивается метка, состоящая из двух частей: смежная вершина, с указанием направления потока, и поток через вершину. При этом если поток идет из вершины в вершину , то метка имеет вид [], иначе [].
Шаг 1. Присвоить вершине метку [0, ]. Обозначим текущую вершину .
Шаг 2. Берем произвольную помеченную вершину , рассматриваем все не помеченные смежные с вершины .
Если , , метка [+].
Иначе, если , , метка [].
Шаг 3. Повторяем шаг 2 пока не будут выполнены следующие условия:
Если помечена вершина , то переходим на Шаг 4.
Если вершина не помечена и меток больше нельзя расставить, то выход.
Шаг 4. Пользуясь метками, производим насыщение ребер, начиная с вершины .
Если пометка вершины имеет вид [+], то .
Если пометка вершины имеет вид [], то .
Переходим в вершину : .
Повторяем шаг 4 пока не достигнем источника: .
Шаг 5. Переходим на шаг 1.
Замечание:
полученные на последней итерации пометки позволяют определить минимальный разрез. В него входят ребра, соединяющие помеченные и непомеченные вершины.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Для каждой вершины отображаются метки [], для ребер отображается пропускная способность и проходящий поток . Насыщенные ребра выделяются цветом.
Режим обучения:
Пользователь выделяет текущую вершину и расставляет метки в смежных с ней вершинах. Если текущая вершина выбрана не правильно или в смежных вершинах нельзя расставить метки, пользователь информируется об этом. После достижения стока, пользователь выбирает ребра, по которым должно происходить насыщение, если ребро выбрано не правильно, то пользователь предупреждается об этом.
5. Задача построения кратчайшего пути от помеченной вершины
Постановка задачи
Задача о нахождении кратчайшего пути между двумя произвольными вершинами формулируется следующим образом: дан взвешенный граф G(V, E, С)
, необходимо найти путь из вершины s
в вершину t
такой, чтобы суммарный вес входящих в него ребер был минимальным. Очевидно, что данная задача имеет смысл только в графах, не имеющих контуров с отрицательным весом, иначе проходя по этому контуру сколь угодно большое число раз, можно сколь угодно уменьшать длину пути.
Методы решения
- Алгоритм Форда-Беллмана
Данный алгоритм применим к графам, которые могут иметь отрицательные веса ребер, но не имеют контуров с отрицательным весом. Алгоритм состоит в последовательном построении кратчайших путей из 1, 2 .. k
ребер , где k
- номер шага алгоритма. На каждом шаге вершинам присваиваются пометки вида [l
,
k
], где l
– длина кратчайшего пути, состоящего из не более, чем k
ребер, от вершины s
. Если в графе нет отрицательных контуров, то кратчайший путь из s
в вершину t
не может содержать более чем n
-1
ребро. Более подробно с данным алгоритмом можно ознакомиться в работах [1, 2].
Шаг 1. , расставляем пометки:
.
Шаг 2. Обновляем пометки для вершин смежных с вершинами, входящими в : , .
Шаг 3. Если и , следовательно в графе есть контур отрицательного веса. Выход.
Если и , то кратчайшие пути найдены. Выход.
и перейти к шагу 4.
Шаг 4. Обновляем множество : , . Перейти к шагу 2.
Замечание
: данный алгоритм используется также при решении задачи поиска всех кратчайших путей от помеченной вершины, с числом ребер не больше . Для этого алгоритм останавливается на итерации, полученные на этом шаге пометки являются длинами искомых кратчайших путей.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Вершина-источник s
и вершина-сток t
задаются интерактивно. Отображать пометки вершин, выделять цветом ребра, входящие в кратчайшие пути. На каждом шаге: выделять цветом изменяемые пометки, добавляемые ребра.
Режим обучения:
На первом этапе пользователь задает начальную вершину . Пользователь выбирает вершины, пометки в которых должны быть изменены. Если выбор правильный, то пометка изменяется, вершина и соответствующий кратчайший путь выделяются цветом. Если выбор не правильный, то пользователь предупреждается об этом.
- Алгоритм Дейкстры
Алгоритм Дейкстры рассчитан на случай, когда веса всех ребер неотрицательные: . В процессе поиска решения вершинам присваиваются пометки, которые могут быть двух видов: (#) временные, (*) – постоянные.
Также с данным алгоритмом можно ознакомиться в работах [2, 3].
Шаг 1. Вершине s
присваиваем пометку [0, *], всем вершинам присваиваем пометку [0, #]. Помечаем вершину s
как текущую p =
s.
Шаг 2. и имеющих временные пометки, изменить пометку на [, #], где .
Шаг 3. Для такой, что из всех , имеющих временную пометку, изменить пометку на постоянную , p =
.
Шаг 4. Если p=t, остановиться. Иначе переход на Шаг 2.
Замечание
: если необходимо найти все кратчайшие пути от вершины s
, то условием останова является наличие у всех вершин графа постоянных пометок.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Вершина-источник s
и вершина-сток t
задаются интерактивно. Для каждой вершины графа отображать пометку [, #(*)]. На каждом шаге: изменять значения пометок, выделять цветом пометку, измененную на постоянную на последнем шаге, выделять изменяемые на текущем шаге временные пометки. Кратчайшие пути и вершины с постоянными пометками выделять цветом.
Режим обучения:
В данном режиме пользователь выбирает вершины, временная пометка которых должна быть изменена, изменяет наименьшую временную пометку на постоянную. Если выбор правильный, то пометка изменяется, вершина и соответствующий кратчайший путь выделяются цветом. Если выбор не правильный, то пользователь предупреждается об этом.
6. Задача о максиминном пути
Постановка задачи
Задача о максимином пути относится к так называемым задачам поиска узких мест. В данном случае дан взвешенный граф G(V, E, С)
, веса ребер интерпретируются как пропускная способность. Необходимо найти путь из вершины s
в вершину t
, обладающий наибольшей пропускной способностью, то есть вес наименьшего ребра, входящего в путь, должен быть максимальным. [1]
Пусть имеется некоторый путь в графе G
из вершины s
в вершину t
, состоящий k
из ребер, тогда пропускная способность пути будет вычисляться как . Решением исходной задачи будет .
Методы решения
- Алгоритм Дейкстры
Метод решения данной задачи основан на модификации исходного алгоритма Дейкстры, где сумма заменяется минимумом, а минимум меняется на максимум.
Шаг 1. Вершине s
присваиваем пометку [0, *], всем вершинам присваиваем пометку [∞, #]. Помечаем вершину s
как текущую p =
s.
Шаг 2. и имеющих временные пометки, изменить пометку на [, #], где .
Шаг 3. Для такой, что из всех , имеющих временную пометку, изменить пометку на постоянную , p =
.
Шаг 4. Если p=t, остановиться. Иначе переход на Шаг 2.
Указания по отображению процесса поиска решения:
Режим демонстрации:
Для каждой вершины графа отображать пометку [, #(*)]. На каждом шаге: изменять значения пометок, выделять цветом пометку, измененную на постоянную на последнем шаге, выделять изменяемые на текущем шаге временные пометки. Максиминные пути и вершины с постоянными пометками выделять цветом.
Режим обучения:
В данном режиме пользователь выбирает вершины, временная пометка которых должна быть изменена, изменяет наибольшую временную пометку на постоянную. Если выбор правильный, то пометка изменяется, вершина и соответствующий максиминный путь выделяются цветом. Если выбор не правильный, то пользователь предупреждается об этом.
Список использованной литературы
1. Асанов М.О., Баранов В.А., Расин В.В. Дискретная математика: Графы, Матроиды, Алгоритмы
. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001, 288 с.
2. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978.
3. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985
4. Прилуцкий М.Х. Математические основы информатики. Методическое пособие для студентов очно-заочного отделения факультета ВМК специальности "Прикладная информатика".
5. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М., Мир, 1980.
6. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. Учебное пособие. – М.: Физматлит, 2002.
Оглавление
Введение. 3
Общие методические указания к выполнению работы.. 3
1. Построение минимального остова графа. 4
- Алгоритм Краскала. 4
- Алгоритм Прима. 5
2. Задача о ранце. 6
- Метод ветвей и границ. 6
- Метод динамического программирования. 8
3. Задача коммивояжера. 9
- Метод ближайшего соседа. 10
- Метод ближайшего города. 11
- Решение задачи коммивояжера на основе построения минимального остова 11
- Метод на основе построения эйлерова цикла в минимальном остове. 12
- Метод ветвей и границ. 13
- Метод динамического программирования. 14
4. Задача построения максимального потока. 14
- Алгоритм Форда-Фалкерсона. 15
5. Задача построения кратчайшего пути от помеченной вершины.. 16
- Алгоритм Форда-Беллмана. 17
- Алгоритм Дейкстры.. 18
6. Задача о максиминном пути. 19
- Алгоритм Дейкстры.. 19
Список использованной литературы.. 21