Глава 21. Кратчайшие пути. различные таблицы). Найдите в таблицах все возможности для совершения арбитраж­ных операций и попытайтесь вскрыть их характерные особенности

различные таблицы). Найдите в таблицах все возможности для совершения арбитраж­ных операций и попытайтесь вскрыть их характерные особенности. Например, сохра­няются ли отклонения на протяжении нескольких дней, или же они быстро восстанав­ливаются сразу после возникновения?

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

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. Является ли алгоритм Флойда оптимальным для полных сетей (сети с V² реб­рами)? Обоснуйте ответ.

21.125. Покажите в стиле рис. 21.30-21.32 вычисление по алгоритму Беллмана-Фор­да всех кратчайших путей сети, определенной в упражнении 21.1, с отрицательными весами на ребрах 5-1 и 4-2.

о 21.126. Разработайте класс, основанный на алгоритме Беллмана-Форда, который обес­печивает клиентов возможностью проверить существование в сети отрицательных цик­лов, используя метод старта из источника в каждой сильно связной компоненте.