Индивидуальные задания
Используйте алгоритм Дейкстры для поиска кратчайших путей, ведущих из вершины 1 в каждую другую вершину, на графе, изображенном на рис. 3.6.
Предположим, что после выполнения упражнения 1 вы обнаруживаете, что при расчетах считали отсутствующей дугу (4,2) длины 1. Можно ли при этом воспользоваться уже полученными результатами или необходимо вновь в полном объеме провести вычисления по алгоритму Дейкстры?
Рис. 3.6
Используя алгоритм Флойда, найдите кратчайшие пути между всеми вершинами графа, изображенного на рис. 3.6.
Используя алгоритм Данцига, найдите кратчайшие пути между всеми парами вершин графа, изображенного на рис. 3.6. Сравните полученные результаты с результатами выполнения предыдущего упражнения.
Используя обобщенный алгоритм Флойда, найдите первые три кратчайшие пути между всеми парами вершин на графе, изображенном на рис. 3.6. Выполните то же самое, используя обобщенный алгоритм Данцига.
Предположим, что перед вами стоит задача найти кратчайшие маршруты полетов между всевозможными парами аэропортов Европы. При этом необходимо учесть, что из-за отсутствия возможности получения въездной визы аэропорты некоторых стран могут быть закрыты для тех или иных пассажиров. Выберите наиболее эффективный способ решения данной задачи.
Влияет ли выбор нумерации вершин графа на эффективность алгоритма Флойда, алгоритма Данцига, алгоритма двойного поиска? Если влияет, то почему?
В графе, изображенном на рис. 3.6, найдите три первые кратчайшие пути между вершиной 1 и всеми остальными вершинами.
Покажите, что некоторая неоптимальная строка оценок может остаться неизменной в одной простой итерации алгоритма двойного поиска, однако уже в следующей простой итерации такая строка оценок обязательно изменится.
Предположим, что обобщенный алгоритм Флойда был использован для получения длин трех наилучших путей между всеми парами вершин в задаче поиска узких мест. Как полученные результаты могут быть использованы для поиска самих путей?
Какие значения следует присваивать компонентам вектора при решении задачи о путях с усилениями?
Пусть скорости перекачки нефти между различными емкостями нефтеперерабатывающего завода задаются следующей таблицей:
Емкость | А | Б | В | Г |
А | 0,00 | 0,13 | 0,14 | 0,15 |
Б | 0,08 | 0,00 | 0,13 | 0,08 |
В | 0,17 | 0,12 | 0,00 | 0,18 |
Г | 0,10 | 0,06 | 0,13 | 0,00 |
Найдите два наилучших способа перекачки нефти из емкости А в емкость Г.
Предположим, что после выполнения всех вычислений по алгоритму двойного поиска вы обнаруживаете, что одна из длин дуг была задана неверно. При каких условиях часть полученных результатов может быть оставлена без изменений?
Фармацевтический фирма планирует разработать в течение двенадцати месяцев новый препарат, который мог бы конкурировать с препаратом, недавно выпущенным главными конкурентами данной фирмы.
Разработка нового препарата осуществляется в четыре этапа, которые могут быть пройдены в медленном, нормальном или быстром темпе. Различные темпы прохождения этапов соответствуют различным уровням затрат времени и средств, которые задаются следующей таблицей (в таблице первая цифра — длительность в месяцах, вторая цифра — затраты в тыс. долл.):
Этап | Теоретические исследования | Лабораторные эксперементы | Одобрение правительства | Сбыт | |||
Темп | |||||||
|
| ||||||
Медленный |
| 5, 5 | 3, 6 | 6, 1 | 5, 8 | ||
Нормальный |
| 4, 7 | 2, 8 | 4, 1 | 4,10 | ||
Быстрый |
| 2, 10 | 1, 12 | 2, 3 | 3, 15 |
Найдите наилучший для фирмы способ разработки за двенадцать месяцев нового препарата при условии, что затраты фирмы не превысят 25 тыс. долл. Найдите второй наилучший способ достижения той же цели.
Управляющий гостиницей должен забронировать номера для новобрачных на следующий месяц. Он получил определенное количество заявок на бронирование с различными датами приезда и отъезда. Каждое возможное бронирование номеров дает гостинице определенный доход, зависящий от того, кем являются клиенты (студенты, служащие, персонал авиакомпаний и т. д.). Каким образом в данном случае использовать алгоритм Дейкстры для выработки расписания бронирования номеров, приносящего гостинице максимальный доход? (Указание. Представьте каждую заявку на бронирование номера дугой, соединяющей вершины, соответствующие датам приезда и отъезда; в соответствующем графе будут отсутствовать контуры, и потому к нему может быть применен алгоритм Дейкстры.)
Вариант | Задание1 |
1 | 8 |
2 | 4 |
3 | 11 |
4 | 13 |
5 | 9 |
6 | 2 |
7 | 14 |
8 | 5 |
9 | 15 |
10 | 3 |
11 | 10 |
12 | 6 |
13 | 12 |
14 | 1 |
15 | 7 |
Список использованных источников
1 Майника, Э. Алгоритмы оптимизации на сетях и графах : пер. с англ. / Э. Майника. - М.: Мир, 1981. - 323 с.