Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 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).