Главная » Просмотр файлов » Алгоритмы - построение и анализ

Алгоритмы - построение и анализ (1021735), страница 146

Файл №1021735 Алгоритмы - построение и анализ (Алгоритмы - построение и анализ) 146 страницаАлгоритмы - построение и анализ (1021735) страница 1462017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 146)

25.1 Задача о кратчайших путях и умножение матриц В этом разделе представлен алгоритм динамического программирования, предназначенный для решения задачи о поиске кратчайших путей между всеми парами вершин в ориентированном графе С = (1г, Е). В каждом основном цикле динамического программирования будет вызываться операция, очень напоминающая матричное умножение, поэтому такой алгоритм будет напоминать многократное умножение матриц. Начнем с того„что разработаем для решения задачи о кратчайших путях между всеми парами вершин алгоритм со временем работы 9 (1 "4), после чего улучшим этот показатель до величины 9 (Ъ'з 1я Ъ"). Перед тем как продолжить, кратко напомним описанные в главе 15 этапы разработки алгоритма динамического программирования.

1. Описание структуры оптимального решения. 2. Рекурсивное определение значения оптимального решения. 3. Вычисление значения, соответствующего оптимальному решению, пользуясь методом восходящего анализа. (Четвертый этап, т.е. составление оптимального решения на основе полученной информации, рассматривается в упражнениях.) Структура кратчайшего пути Начнем с того, что охарактеризуем структуру оптимального решения. Для задачи о кратчайших путях между всеми парами вершин графа С = (К Е) доказано (лемма 24.1), что все частичные пути кратчайшего пути — тоже кратчайшие пути. Предположим, что граф представлен матрицей смежности И' = (ии). Рассмотрим кратчайший путь р из вершины 1 в вершину з и предположим, что этот путь содержит не более гп ребер. Если циклы с отрицательным весом отсутствуют, то пз конечно.

Если з = з, то вес пути р равен О, а ребра в нем отсутствуют. Если же вершины г и з различаются, то пуп р раскладывается на1- Й -+ у, где путь . р' р' содержит не более гп — 1 ребер. Согласно лемме 24.1, р' — кратчайший путь из вершины 1 в вершину к, поэтому выполняется равенство б (г, з) = б(1, 1с) + юь . Часть ЧЕ Алгоритмы для работы с графами 712 Рекурсивное решение задачи о кратчайших путях между всеми парами вершин Пусть теперь 1, — минимальный вес любого пути из вершины г в вершину (т) )', содержащий не более т ребер. Если т = О, то кратчайший пугь из вершины ( в вершину ) существует тогда и только тогда, когда ( = )'. Таким образом, (о) (О если ( = ), (оо если г ~ у.

Для т > 1 величина 1," вычисляется как минимум двух величин. Первая— (т) (вес кратчайшего нуги из вершины ( в вершину з, состоящего не более чем (тл — 1) из т — 1 ребер), а вторая — минимальный вес произвольного пути из вершины ( в вершину ), который состоит не более чем из т ребер. Этот минимальный вес получается в результате рассмотрения всех возможных предшественников /~ вершины з'. Таким образом, мы можем рекурсивно определить 1(" ) = ппп 1( ), гшп Ы~ ) + юь 1 = гшп (1(ра )+юя 1. (25.2) Последнее равенство следует из того, что ю = О для всех у. Чему равен фактический вес каждого из кратчайших путей б ((, ))? Если граф не содержит циклов с отрицательным весом, то для каждой пары вершин ( и ~, для которых справедливо неравенство б (з, )) < оо, существует кратчайший путь из вершины ( в вершину ), который является простым и, следовательно, содержит не более и — 1 ребер.

Путь из вершины г в вершину у, содержащий более и — 1 ребер, не может иметь меньший вес, чем кратчайший путь из вершины ( в вершину )1 Поэтому фактический вес каждого из кратчайших путей определяется равенствами б (, ) 1(~-О 1(?) 1( + ) (25.3) Вычисление весов кратчайших путей в восходящем порядке Используя в качестве входной матрицу И' = (юя), вычислим ряд матриц Ь(1),Ь(з),...,Ь(" 1), где для т = 1,2,...,и — 1 имеем Ь("') = ~1" ~. Конечная (о ). матрица Ь(" 1) содержит фактический вес каждого из кратчайших путей. Заметим, что для всех вершин г, у Е У выполняется равенство 1; = ючп так что ь(') = и'.

Глава 25. Кратчайшие пути между всеми парами вершин 713 Сердцем алгоритма является приведенная ниже процедура, которая на основе заданных матриц Ь("' ~) и И~ вычисляет и возвращает матрицу Ь( ). Другими словами, она расширяет вычисленные на текущий момент кратчайшие пути, добавляя в них еще по одному ребру. Ехтнм0 ЬнОктеБт РАтнз(Ь, И~) 1 п ~ — гоша[А] 2 Пусть 1.' = (1'; ) — матрица размера и х п 3 1огг -1Гоп 4 йо аког 7' -1 Фо и 5 йо 1'; ~- оо 6 $огй -1 Гоп 7 до 1'; — ппп(115, Ць + шьу) 8 геФнгв Ь' В этой процедуре вычисляется матрица Ь' = (1', ), которая н возвращается процедурой по завершении. Вычисления осуществляются на основе уравнения (25.2) для всех пар индексов г и 7; при этом в качестве Ь( 1) используется матрица Т, а в качестве Ь( ) — матрица Ь'. (В псевдокоде верхние индексы не используются, чтобы входные и выходные матрицы процедуры не зависели от гп.) Из-за наличия трех вложенных циклов 1ог время работы алгоритма равно 0 (пз).

Теперь становится понятной связь с умножением матриц. Предположим, требуется вычислить матричное произведение С = А В, где А и  — матрицы размером и х и. Тогда для 1,7' = 1, 2,..., п мы вычисляем (25.4) Заметим, что если в уравнении (25.2) выполнить подстановки ппп — > +, + то мы получим уравнение (25.4). Таким образом, если в процедуре Ехтннп Бнонтвзт Рлтнз произвести соответствующие изменения и заменить значение со (исходное значение для операции вычисления минимума) значением О (исходное значение для вычисления суммы), получим процедуру для непосредственного перемножения матриц со временем выполнения 9 (пз): Часть Ч1.

Алгоритмы для работы с графами 714 МАтшх Мыьт!Рьу(А, В) 1 п — гасов[А] 2 Пусть С вЂ” матрица и х п 3 1ог ( - 1 Со и 4 с)о Гогу 1 Сои 5 босу -О 6 1'ог к — 1 Со и 7 с)о с; — су + агя Ь|. 8 гесцгп С Возвращаясь к задаче о кратчайших путях между всеми парами вершин, вычислим веса кратчайших путей путем поэтапного расширения путей ребро за ребром. Обозначая через А В матричное "произведение", которое возвращается процедурой Ехтенп Яноктезт РАтнз(А, В), вычислим последовательность и — 1 матриц: В(е) Иг Ь() И Ь(г) И ,(1) у (г) В(з) Иг, Игг Из ~( -Н ~(ь-г) . Иг Иг Как было показано ранее, матрица г,(" 1) = Иг" 1 содержит веса кратчайших путей.

В приведенной ниже процедуре эта последовательность вычисляется в те- чение времени О (п4): ЯЬО% А1.Ь РА!КЕ БНОКТЕЗТ РАТНЗ(И") 1 и — гасов(Иг) 2 В(1) — Иг 3 согт -2 Со и — 1 4 Йо Ь(~) < — Ехтен0 БнОктезт РАтнз(ь(~ ), Иг) 5 геСпгп с,(" 1) На рис. 25.1 приведен граф и матрицы В("'), вычисленные процедурой ЯьО1в' Аьь РА1кз Бноктезт РАтнз. Можно легко убедиться в том, что величина с.(з) = Ь(4) . И' равна г (4), а следовательно, для всех т > 4 выполняется равенство Ь("') = ~(4) Улучшение времени работы Следует сказать, что наша цель состоит не в том, чтобы вычислить все матрицы Ь("'): нам нужна только матрица Ь(" ').

Напомним, что если циклы с отрицательным весом отсутствуют, из уравнения (25.3) вытекает равенство г".( ) = Ь(" 1) Глава 25. Кратчайшие пути между всеми парами вершин 715 О 3 8 оо — 4 О 3 8 2 — 4 3 О -4 1 7 оо 4 О 5 11 оо О со 1 7 оо 4 О оо оо г12)— 2 оо — 5 ОО ОО СО 2 — 1 — 5 Π— 2 8 ОО 1 6 О О оо 6 О О 3 — 3 2 — 4 О 1 -3 2 -4 3 Π— 4 1 — 1 7 4 О 5 11 3 Π— 4 1 — 1 7 4 О 5 3 51з) г (4) 2 — 1 — 5 Π— 2 8 5 1 6 О 2 — 1 — 5 Π— 2 8 5 1 6 О Рис. 25.1. Ориентированный граф и последовательность матриц Ь) ), вы- численных в процедуре Яьо))) Аьь Рл)кз Бноктазт Рктнз для всех целых гп > и — 1.

Матричное умножение, определенное процедурой Ехтныг) 8ноктнвт РАтнв, как и обычное матричное умножение, является ассоциативным (упражнение 25.1-4). Таким образом, матрицу Ь)" 1) можно получить путем вычисления ~18 (и — 1)~1 матричных умножений в последовательности: Иг И', )Иг2, Иг2 И,4 Иг4 Т Рнв( -))1) ~+,21)в( -))1 Иг2Пв( -))1-) Игзг)в( -))1-) гзпвм-))1) В силу неравенства 2ВЯ)" )И > гв — 1 последнее произведение в'~ ) равно Т (гг-1) В приведенной ниже процедуре данная последовательность матриц вычисляется методом многократного возведения о квадрат (гереа1ег) зг)папой): Г (1) Т (2) Т (4) г (в) И'2 И 4 Игв Часть Ч1.

Алгоритмы для работы с графами 716 Рлзтек А1.е Рл!кз ЯнОктезт Рлтнэ(Иг) 1 и - гоша[И'] 2 Ь11) - Иг 3 т — 1 4 зуЬ11е т < и — 1 5 11о Ь1з 1 Ехтенп Яноктезт Рлтнз(Ь(™), Ь(™)) б ги ~- 2т 7 гензгп Ь<"') В каждой итерации цикла згЫ!е в строках 4-6, начиная с т = 1, вычисляется г матрица Ь1з ) = (Ьг )) . В конце каждой итерации значение т удваивается. В последней итерации матрица Ьг" 1) вычисляется путем фактического вычисления матрицы Ьгз ) для некоторого значения и — 1 < 2ги < 2и — 2.

Согласно уравнению (25.3), Ь1з ) = Ь1" 1). Далее выполняется проверка в строке 4, значение т удваивается, после чего выполняется условие ги > и — 1, так что условие цикла оказывается невыполненным, и процедура возвращает последнюю вычисленную матрицу. Время работы процедуры Рлзтек А1л, Рл1кз Яноктезт Рлтнл равно 9 (из1би), поскольку вычисление каждого из [1к1и — 1)] матричных произведений требует 6 (из) времени. Заметим, что этот код довольно компактен.

Он не содержит сложных структур данных, поэтому константа, скрытая в 6-обозначении, невелика. Упражнения 25.1-1. Выполните процедуру Яьоцг Аы. Рл1кз Бноктезт Рлтнз над взвешенным ориентированным графом, показанным на рис. 25.2, и запишите промежуточные матрицы, которые получаются в каждой итерации цикла. Затем проделайте то же самое для процедуры Рлзтек Аы. Рл1кз Бноктезт Рлтнз.

Характеристики

Тип файла
DJVU-файл
Размер
18,3 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6552
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее