Студопедия

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

КАТЕГОРИИ:

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






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

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

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




.

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