Индивидуальные задания

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

2. Предположим, что после выполнения упражнения 1 вы обнаружи­ваете, что при расчетах считали отсутствующей дугу (4,2) длины 1. Можно ли при этом воспользоваться уже полученными результата­ми или необходимо вновь в полном объеме провести вы­числения по алгоритму Дей­кстры?

   Рис. 3.6

3. Используя алгоритм Флойда, найдите кратчайшие пути между всеми вершинами графа, изображенного на рис. 3.6.

3. Используя алгоритм Данцига, найдите кратчайшие пути между всеми парами вершин графа, изображенного на рис. 3.6. Сравните полу­ченные результаты с результатами выполнения предыду­щего упражнения.

5. Используя обобщенный алгоритм Флойда, найдите первые три крат­чайшие пути между всеми парами вершин на графе, изображенном на рис. 3.6. Выполните то же самое, используя обобщенный алгоритм Данцига.

5. Предположим, что перед вами стоит задача найти кратчайшие мар­шруты полетов между всевозможными парами аэропортов Европы. При этом необходимо учесть, что из-за отсутствия возможности получения въезд­ной визы аэропорты некоторых стран могут быть закрыты для тех или иных пассажиров. Выберите наиболее эффективный способ решения данной за­дачи.

6. Влияет ли выбор нумерации вершин графа на эффективность алго­ритма Флойда, алгоритма Данцига, алгоритма двойного поиска? Если влияет, то почему?

7. В графе, изображенном на рис. 3.6, найдите три первые кратчай­шие пути между вершиной 1 и всеми остальными вершинами.

8. Покажите, что некоторая неоптимальная строка оценок может ос­таться неизменной в одной простой итерации алгоритма двойного поиска, однако уже в следующей простой итерации такая строка оценок обязатель­но изменится.

10. Предположим, что обобщенный алгоритм Флойда был использо­ван для получения длин трех наилучших путей между всеми парами вершин в задаче поиска узких мест. Как полученные результаты могут быть исполь­зованы для поиска самих путей?

11. Какие значения следует присваивать компонентам вектора при решении задачи о путях с усилениями?

12. Пусть скорости перекачки нефти между различными емкостями нефтеперерабатывающего завода задаются следующей таблицей:

Найдите два наилучших способа перекачки нефти из емкости А в ем­кость Г.

13. Предположим, что после выполнения всех вычислений по алго­ритму двойного поиска вы обнаруживаете, что одна из длин дуг была задана неверно. При каких условиях часть полученных результатов может быть оставлена без изменений?

14. Фармацевтический фирма планирует разработать в течение две­надцати месяцев новый препарат, который мог бы конкурировать с препа­ратом, недавно выпущенным главными конкурентами данной фирмы.

Разработка нового препарата осуществляется в четыре этапа, которые могут быть пройдены в медленном, нормальном или быстром темпе. Различ­ные темпы прохождения этапов соответствуют различным уровням затрат времени и средств, которые задаются следующей таблицей (в таблице первая цифра — длительность в месяцах, вторая цифра — затраты в тыс. долл.):

Найдите наилучший для фирмы способ разработки за двенадцать месяцев нового препарата при условии, что затраты фирмы не превысят 25 тыс. долл. Найдите второй наилучший способ достижения той же цели.

13. Управляющий гостиницей должен забронировать номера для ново­брачных на следующий месяц. Он получил определенное количество заявок на бронирование с различными датами приезда и отъезда. Каждое возмож­ное бронирование номеров дает гостинице определенный доход, зависящий от того, кем являются клиенты (студенты, служащие, персонал авиакомпа­ний и т. д.). Каким образом в данном случае использовать алгоритм Дейкст­ры для выработки расписания бронирования номеров, приносящего гости­нице максимальный доход? (Указание. Представьте каждую заявку на бро­нирование номера дугой, соединяющей вершины, соответствующие датам приезда и отъезда; в соответствующем графе будут отсутствовать контуры, и потому к нему может быть применен алгоритм Дейкстры.)

Список использованных источников

1 Майника, Э. Алгоритмы оптимизации на сетях и графах : пер. с англ. / Э. Майни­ка. - М.: Мир, 1981. - 323 с.

25