Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Глава 21. Кратчайшие пути. о 21.89.Предположите, что работы в упражнении 21.87 имеют также ограничения, со­стоящие в том, что работа 1 должна начаться перед окончанием работы 6







339


о 21.89. Предположите, что работы в упражнении 21.87 имеют также ограничения, со­стоящие в том, что работа 1 должна начаться перед окончанием работы 6, а работа 2 должна начаться перед окончанием работы 4. Сформулируйте задачу поиска кратчай­ших путей, к которой сводится эта задача, воспользовавшись рассуждениями, приве­денными при доказательстве свойства 21.16.

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

> 21.91. Объясните, почему методика доказательства свойства 21.16 не распространяет­ся на доказательство того, что задача кратчайших путей сводится к задаче планирова­ния работ с конечными сроками.

21.92. Модернизируйте программу 21.8, чтобы на работы можно было ссылаться с ис­
пользованием символических имен вместо целых чисел (см. программу 17.10).

21.93. Разработайте интерфейс АТД, который дает возможность клиентам ставить и
решать задачи разностных ограничений.

21.94. Разработайте класс, который реализует интерфейс из упражнения 21.93, осно­
вывая решение задачи разностных ограничений на сведении к задаче поиска кратчай­
ших путей в ациклических сетях.

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

о 21.96. Ваше решение задачи кратчайших путей в ациклических сетях из упражнения 21.95 предполагает существование реализации, которая решает задачу разностных ог­раничений. Что случится, если вы воспользуетесь реализацией из упражнения 21.94, которая предполагает существование реализации для задачи кратчайших путей в ацик­лических сетях?

о 21.97. Докажите эквивалентность любых двух NP-трудных задач (т.е., выберите две за­дачи и докажите, что они сводятся друг к другу).

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

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

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

21.101. Разработайте интерфейс АТД, который дает клиентам возможность ставить и ре­шать задачи календарного планирования работ. Напишите класс, который реализует полученный интерфейс, основав решение задачи календарного планирования работ на сведении к задаче поиска кратчайших путей в ациклических сетях (как в программе 21.8).



Часть 5. Алгоритмы на графах


о 21.102. Добавьте в класс из упражнения 21.101 функцию (вместе с реализацией), которая печатает наиболее длинный путь в календарном графике. (Такой путь обычно называется критическим пу­тем.)

21.103. Напишите клиент для интерфейса из уп­ражнения 21.101, который осуществляет вывод в PostScript-программу для изображения календар­ного графика в стиле рис. 21.24 (см. раздел 4.3).

о 21.104. Разработайте модель для генерации задач календарного планирования работ. Воспользуйтесь полученной моделью для тестирования результатов выполнения упражнений 21.101 и 21.103 на прием­лемом множестве размерностей задач.

РИСУНОК 21.25. ДИАГРАММА PERT Диаграмма PERT — это сетевое представление задачи календарного планирования работ, где работы изображаются ребрами. Сеть в верхней части рисунка есть пред­ставление задачи планирования работ из рис. 21.22, при этом работы от 0 до 9 представлены, соответ­ственно, ребрами 0-1, 1-2, 2-3, 4-3, 5-3, 0-3, 5-4, 1-4, 4-2 и 1-5. Крити­ческим путем в этом календарном графике является наиболее длинный путь в данной сети.

21.105. Напишите класс, который реализует интер­фейс из упражнения 21.101, основав решение за­дачи календарного планирования работ на сведе­нии к задаче разностных ограничений.

о 21.106. Диаграмма PERT (Project Evaluation and Review Technique - сетевое планирование и уп­равление) — это сеть, которая представляет зада­чу календарного планирования работ, с ребрами в качестве работ (см. рис. 21.25). Напишите класс, реализующий интерфейс календарного планирова­ния работ из упражнения 21.101, который осно­вывается на диаграммах PERT.

21.107. Сколько вершин будет в диаграмме PERT
для задачи планирования работ с К работами и Е
ограничениями?

21.108. Напишите программы для преобразования
между представлением календарного планирова-

ния работ, основанном на ребрах (диаграммы PERT) (см. упражнение 21.106), и пред­ставлением, основанном на вершинах (см. рис. 21.22).


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал