Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 21. Кратчайшие пути. различные таблицы). Найдите в таблицах все возможности для совершения арбитражных операций и попытайтесь вскрыть их характерные особенности
различные таблицы). Найдите в таблицах все возможности для совершения арбитражных операций и попытайтесь вскрыть их характерные особенности. Например, сохраняются ли отклонения на протяжении нескольких дней, или же они быстро восстанавливаются сразу после возникновения? 21.114. Разработайте модель для генерации случайных задач арбитражных операций. 21.115. Разработайте модель для генерации случайных задач календарного планиро 21.116. Измените интерфейс и реализацию из упражнения 21.101, чтобы дать клиен о 21.117. Объясните, почему следующее рассуждение ошибочно: задача поиска кратчайших путей сводится к задаче разностных ограничений построением, используемым в доказательстве свойства 21.15, а задача разностных ограничений тривиально сводится к линейному программированию, следовательно, принимая во внимание свойство 21.17, линейное программирование является NP-трудным. 21.118. Сводится ли задача поиска кратчайших путей в сетях без отрицательных циклов к задаче планирования работ с конечными сроками? (Эквивалентны ли эти две задачи?) Обоснуйте ответ. о 21.119. Найдите цикл с наименьшим весом (лучшую возможность для совершения арбитражных операций) в примере, показанном на рис. 21.27. о 21.120. Докажите, что задача поиска цикла наименьшего веса в сети, которая может иметь ребра с отрицательными весами, является NP-трудной. > 21.121. Покажите, что алгоритм Дейкстры работает правильно для сети, в которой ребра, исходящие из источника, являются единственными ребрами с отрицательными весами. о 21.122. Разработайте класс, основанный на алгоритме Флойда, который обеспечивает клиентов возможностью проверить существование в сети отрицательных циклов. 21.123. Воспользовавшись алгоритм Флойда, покажите в стиле рис. 21.29 вычисления всех кратчайших путей для сети, определяемой в упражнении 21.1, с отрицательными весами ребер 5-1 и 4-2. • 21.124. Является ли алгоритм Флойда оптимальным для полных сетей (сети с V2 ребрами)? Обоснуйте ответ. 21.125. Покажите в стиле рис. 21.30-21.32 вычисление по алгоритму Беллмана-Форда всех кратчайших путей сети, определенной в упражнении 21.1, с отрицательными весами на ребрах 5-1 и 4-2. о 21.126. Разработайте класс, основанный на алгоритме Беллмана-Форда, который обеспечивает клиентов возможностью проверить существование в сети отрицательных циклов, используя метод старта из источника в каждой сильно связной компоненте.
|