Методические указания к лабораторной работе 14 для студентов по специальности 1-53 01 02 «Автоматизированные системы обработки информации»


НазваниеМетодические указания к лабораторной работе 14 для студентов по специальности 1-53 01 02 «Автоматизированные системы обработки информации»
страница1/4
Дата публикации01.04.2014
Размер0.53 Mb.
ТипМетодические указания
referatdb.ru > Информатика > Методические указания
  1   2   3   4


ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ»

Кафедра "Автоматизированные системы управления"

МАТЕМАТИЧЕСКИЕ МОДЕЛИ ИНФОРМАЦИОННЫХ ПРОЦЕССОВ И УПРАВЛЕНИЯ

Методические указания

к лабораторной работе 14 для студентов по специальности 1-53 01 02

« Автоматизированные системы обработки информации»

Могилев 2011

УДК 621.01

ББК 36.4

И87
Рекомендовано к опубликованию

учебно-методическим управлением

ГУВПО «Белорусско-Российский университет»
Одобрено кафедрой «Автоматизированные системы управления»

«11» мая 2010 г. протокол №8

Составитель канд. техн. наук, доц. А.И. Якимов
Рецензент канд. техн. наук, доц. Г.С. Леневский
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике.

Учебное издание

^ МАТЕМАТИЧЕСКИЕ МОДЕЛИ ИНФОРМАЦИОННЫХ ПРОЦЕССОВ И УПРАВЛЕНИЯ


Ответственный за выпуск

С.К. Крутолевич

Технический редактор

А.Т. Червинская

Компьютерная верстка

Н.П. Полевничая


Подписано в печать . Формат 60х84/16. Бумага офсетная. Гарнитура Таймс.

Печать трафаретная. Усл.печ.л. . Уч.-изд.л. . Тираж 65 экз. Заказ №
Издатель и полиграфическое исполнение

Государственное учреждение высшего профессионального образования

«Белорусско-Российский университет»

ЛИ № 02330/375 от 29.06.2004 г.

212030, г. Могилев, пр. Мира, 43





© ГУВПО «Белорусско-Российский университет», 2010


Лабораторная работа 14

^ Решение задач оптимизации на графах
Цель работы: Изучить способы решения задач оптимизации на графах.
Порядок выполнения работы.

  1. Изучить теоретические сведения.

  2. Получить задание у преподавателя.

  3. Исследовать способы решения задач оптимизации на графах.

  4. Сделать выводы по результатам исследований.

  5. Оформить отчет.


Требования к отчету.

  1. Цель работы.

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

  3. Результаты исследования решения задач оптимизации на графах.

  4. Выводы.


Теоретические сведения.
Алгоритмы поиска путей

1.1 Алгоритм поиска кратчайшего пути

Каждой дуге (х,у) исходного графа G поставим в соответствие число а(х,у). Если в графе G отсутствует некоторая дуга (x, y), положим a(x, y)=. Будем называть число а(х, у) длиной дуги (х, у), хотя а(х, у) можно также интерпретировать как соответствующие затраты или соответствующий весовой коэффициент. Определим длину пути как сумму длин отдельных дуг, составляющих этот путь.

Для любых двух вершин s и t графа G могут существовать несколько путей, соединяющих вершину s с вершиной t. В данном разделе будет рассмотрен алгоритм, который определяет такой путь, ведущий из вершины s в вершину t, который имеет минимально возможную длину. Этот путь называется кратчайшим путем между вершинами с и t.
Пример 1. Предположим, что вы хотите проехать из Бостона в Лос-Анджелес, используя магистральные шоссейные дороги, соединяющие различные штаты. Как выбрать кратчайший маршрут?

Постройте граф, вершины которого соответствуют точкам соединения рассматриваемых дорог. Пусть каждая дуга графа соответствует шоссейной дороге, соединяющей пункты, представленные соответствующими вершинами. Пусть длина дуги определяется длиной (в километрах) соответствующего участка дороги. Теперь задача поиска оптимального маршрута движения между Бостоном и Лос-Анджелесом может быть сведена к задаче отыскания в построенном графе кратчайшего пути между вершинами, соответствующими Бостону, откуда вы начинаете путешествие, и Лос-Анджелесу, где ваше путешествие заканчивается.

Пример 2. Пассажир обращается за услугами к некоторой авиакомпании. Он желает попасть воздушным путем из Спрингфилда (шт. Иллинойс) в столицу Турции Анкару, проведя в воздухе как можно меньше времени, поскольку полет на самолете вызывает у него чувство страха. Какой маршрут в данном случае должна предложить авиакомпания пассажиру?

Чтобы решить этот вопрос, необходимо построить некоторый граф. Вершины этого графа представляют аэропорты, через которые может проходить маршрут полета от Спрингфилда до Анкары, а дуги соответствуют полетам между определенными аэропортами. Длиной каждой дуги следует считать время соответствующего полета. Теперь авиакомпании необходимо ознакомиться с последующим материалом данного раздела. После изучения этого материала станет понятно, как найти в построенном графе кратчайший путь, соединяющий вершины, соответствующие Спрингфилду и Анкаре.

Пример 3. Предположим, что вам необходимо иметь в своем распоряжении автомобиль на протяжении ближайших пяти лет до выхода на пенсию. В настоящий момент имеется большой выбор автомобилей, которые вы можете либо купить, либо взять напрокат. Автомобили имеют различные сроки эксплуатации и разную стоимость. Каким образом вы должны сделать выбор в такой ситуации?

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

Пример 4. Представим себе следующую ситуацию. Коммивояжер планирует поездку из Бостона в Лос-Анджелес. Цель поездки — посещение одного из основных клиентов. Коммивояжер собирается воспользоваться той же системой магистральных шоссейных дорог, которая фигурировала в примере 1. Помимо основной цели поездки коммивояжер планирует посещение и других пунктов, расположенных на пути из Бостона в Лос-Анджелес, где размещаются другие его клиенты. При этом коммивояжер приблизительно знает, какую сумму комиссионных он заработает после возможной встречи с каждым из клиентов. Какой маршрут поездки из Бостона в Лос-Анджелес следует выбрать коммивояжеру?

В рассматриваемом случае длиной каждой дуги в графе, представляющем рассматриваемую систему магистральных шоссейных дорог, следует считать ожидаемую «чистую стоимость» проезда (транспортные затраты за вычетом ожидаемой суммы комиссионных) по определенному участку данной системы дорог. Теперь можно сказать, что коммивояжер должен ехать по маршруту, соответствующему кратчайшему пути в построенном графе между вершинами «Бостон» и «Лос-Анджелес».

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

Пример 5. Мелкий вкладчик решает вопрос о целесообразном размещении своего капитала в следующем году. Он располагает некоторым набором вариантов возможного размещения (может доложить деньги на сберегательную книжку, вложить средства в депозитный сертификат, облигации и т.п.). Для упрощения предположим, что вклады могут производиться или изыматься в начале каждого месяца. Поставим в соответствие началу каждого месяца вершину графа. В этом графе каждому вкладу поставлена в соответствие дуга (х, у) в том случае, если вклад был сделан в месяце х, а срок его истекает в месяце у. Заметим, что указанный граф не содержит контуров. Пусть длина каждой дуги равна взятому с обратным знаком доходу от соответствующего вклада. Наилучшая стратегия вложений капитала соответствует кратчайшему пути (в данном случае пути, имеющему максимальное отрицательное значение длины), соединяющему вершину начала и конца рассматриваемого года. Данный пример почти полностью аналогичен примеру 3, за исключением того, что в нем значения длин дуг графа являются не положительными, а отрицательными числами.

Описываемый в данном разделе алгоритм позволяет находить в графе кратчайший путь между двумя выделенными вершинами s и t при положительных длинах дуг. Этот алгоритм, предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи.

Главная идея, лежащая в основе алгоритма Дейкстры, предельно проста. Предположим, что нам известны т вершин, ближайших к вершине s (близость любой вершины x к вершине s определяется длиной кратчайшего пути, ведущего из s в х). Пусть также известны сами кратчайшие пути, соединяющие вершину s с выделенными т вершинами ( кратчайшим путем из s в х считается нулевой путь, не содержащий дуг. Длина этого пути, естественно, принимается равной нулю ). Покажем теперь, как может быть определена (m + 1)-я ближайшая к s вершина.

Окрасим вершину sиm ближайших к ней вершин. Построим для каждой неокрашенной вершины у пути, непосредственно соединяющие с помощью дуг (х, у) каждую окрашенную вершину х с у. Выберем из этих путей кратчайший и будем считать его условно кратчайшим путем из вершины s в вершину у.

Какая же из неокрашенных вершин является (m+1)-й ближайшей к s вершиной? Та, для которой условно кратчайший путь имеет наименьшую длину. Это обусловливается тем, что кратчайший путь из вершины s в (т+1)-ю ближайшую вершину при положительном значении длин всех дуг должен содержать в качестве промежуточных лишь окрашенные вершины, т.е. вершины, входящие в число т вершин, ближайших к вершине s.

Итак, если известны т ближайших к s вершин, то (т+ 1)-я ближайшая к s вершина может быть найдена так, как это описано выше. Начиная с т=0, описанная процедура может повторяться до тех пор, пока не будет получен кратчайший путь, ведущий из вершины s к вершине t.

Имея в виду приведенные соображения, мы можем теперь формально описать алгоритм Дейкстры.
Алгоритм ^ Дейкстры поиска кратчайшего пути

Шаг 1. Перед началом выполнения алгоритма все вершины и дуги не окрашены. Каждой вершине в ходе выполнения алгоритма присваивается число d(x), равное длине кратчайшего пути из s в х, включающего только окрашенные вершины.

Положить и для всех х, отличных от s. Окрасить вершину s и положить — последняя из окрашенных вершин).

Шаг 2. Для каждой неокрашенной вершины х следующим образом пересчитать величину d(x):

(1)

Если для всех неокрашенных вершин х, закончить процедуру алгоритма: в исходном графе отсутствуют пути из вершины s в неокрашенные вершины. В противном случае окрасить ту из вершин х, для которой величина d(x) является наименьшей. Кроме того, окрасить дугу, ведущую в выбранную на данном шаге вершину х (для этой дуги достигался минимум в соответствии с выражением (1)). Положить ��.

Шаг 3. Если , закончить процедуру; кратчайший путь из вершины s в вершину t найден (это единственный путь из s в t, составленный из окрашенных дуг). В противном случае перейти к шагу 2.

Отметим, что каждый раз, когда окрашивается некоторая вершина (не считая вершины s), окрашивается и некоторая дуга, заходящая в данную вершину. Таким образом, на любом этапе алгоритма в каждую вершину заходит не более чем одна окрашенная дуга. Кроме того, окрашенные дуги не могут образовать в исходном графе цикл, так как в алгоритме не может окрашиваться дуга, концевые вершины которой уже окрашены. Следовательно, можно сделать вывод о том, что окрашенные дуги образуют в исходном графе ориентированное дерево с корнем в вершине s. Это дерево называется ориентированным деревом кратчайших путей. Единственный путь от вершины s до любой вершины х, принадлежащей дереву кратчайших путей, является кратчайшим путем между указанными вершинами.

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

Поскольку на всех этапах алгоритма Дейкстры окрашенные дуги образуют в исходном графе ориентированное дерево, алгоритм можно рассматривать как процедуру наращивания ориентированного дерева с корнем в вершине s. Когда в этой процедуре наращивания достигается вершина t, процедура может быть остановлена.

Если бы мы хотели определить кратчайшие пути из вершины s во все вершины исходного графа, то процедуру наращивания дерева следовало бы продолжить до тех пор, пока все вершины графа не были бы включены в ориентированное дерево кратчайших путей. При этом для исходного графа было бы получено покрывающее ориентированное дерево (при условии, что в этом графе содержится хотя бы одно такое дерево). Итак, для того, чтобы описанный выше алгоритм позволял получать дерево кратчайших путей от вершины s до всех остальных вершин, его третий шаг должен быть скорректирован следующим образом: если все вершины оказываются окрашенными, закончить процедуру (для любой вершины х имеется единственный путь из s в х, состоящий из окрашенных дуг, и этот путь является кратчайшим путем между соответствующими вершинами); в противном случае перейти к шагу 2.

Пример 6. Применим алгоритм Дейкстры к графу, изображенному на рис. 3.1, для нахождения в нем кратчайшего пути между вершинами s и t.

Рис. 3.1.

Перед первым выполнением шага 2 алгоритма окрашена только вершина s. Кроме того, и для всех вершин х, не совпадающих с s.

Шаг 2.











Поскольку величина является минимальной из величин d(a), d(b), d(d), d(i) и d(t), то вершина c окрашивается. Так же окрашивается и дуга (s, с), которая и определяет величину d(c). Текущее дерево кратчайших путей состоит из дуги s, с (рис. 3.2, а).

Шаг 3, Поскольку вершина t остается неокрашенной, осуществляется переход к шагу 2.

Шаг 2.


  1   2   3   4

Похожие рефераты:

Методические указания к лабораторной работе 10 для студентов по специальности...
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике
Методические указания к лабораторной работе 12 для студентов по специальности...
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике
Методические указания к лабораторной работе 8 для студентов по специальности...
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике
Методические указания к лабораторной работе 1 для студентов по специальности...
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике
Методические указания к лабораторной работе 7 для студентов по специальности...
Изложены последовательность выполнения и варианты заданий для лабораторной работы по нечеткой логике
Методические указания и задания контрольной работе №1 для студентов...
Компьютерные информационные технологии. Методические указания и задания к контрольной работе для студентов заочной формы обучения...
Методические указания по выполнению курсового проекта для студентов...
Методические указания по выполнению курсового проекта для студентов специальности 1-53 01 02 «Автоматизированные системы обработки...
Методические указания к самостоятельной работе студентов специальности...
Изложены последовательность выполнения и варианты заданий для самостоятельной работы по дисциплине «Математические модели информационных...
Методические указания к лабораторным работам для студентов специальности...
В методических указаниях изложены этапы проектирования систем обработки информации с использованием case-средств. Предназначены для...
Методические указания по выполнению лабораторных и контрольных работ...
Содержат задания к контрольной работе, методические указания по выполнению контрольной и лабораторных работ

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза