Разработка алгоритма
Решение основано на следующей идее: единицы потока соответствуют самоле- там. Для каждого рейса создается ребро, а верхняя и нижняя границы пропускной способности, равные 1, требуют, чтобы по ребру передавалась ровно одна единица потока. Другими словами, каждый рейс должен обслуживаться одним из самоле- тов. Если (и., v) — ребро, представляющее рейс i, а (u, v ) — ребро, представляющее рейс j, и рейс j доступен из рейса i, то из v. в и. ведет ребро с пропускной способно- стью 1; при этом единица потока может переместиться по (и,, v), а затем перейти прямо к (и., v). Такая конструкция ребер изображена на рис. 7.17, b.
Мы расширяем эту идею на поток в сети, включая в граф источник и сток; теперь можно рассмотреть всю конструкцию в подробностях.
Множество узлов базового графа G определяется следующим образом:♦ Для каждого рейса i граф содержит два узла иi и vi.
♦ G также содержит отдельный узел-источник 5 и узел-сток t.
Множество ребер G определяется следующим образом:
♦ Для всех i существует ребро (иi, vi) с нижней границей 1 и пропускной способ- ностью 1. (Каждый рейс в списке должен обслуживаться.)
♦ Для всех i и j, для которых рейс j доступен от рейса i, существует ребро (vi, иj) c нижней границей 0 и пропускной способностью 1. (Один самолет может вы- полнять рейсы i и j.)
♦ Для всех i существует ребро (5, и) с нижней границей 0 и пропускной способ- ностью 1. (Любой самолет может начать день с полета i.)
♦ Для всех j существует ребро (vj, t) с нижней границей 0 и пропускной способно- стью 1. (Любой самолет может завершить день полетом j.)
♦ Существует ребро (5, t) с нижней границей 0 и пропускной способностью к. (Если имеются дополнительные самолеты, не обязательно использовать их в полетах.)
Наконец, узел 5 имеет уровень потребления -к, а узел t — уровень потребления к. У всех остальных узлов уровень потребления равен 0.
Наш алгоритм основан на построении сети G и поиска в ней действительной циркуляции. Докажем правильность этого алгоритма.
Еще по теме Разработка алгоритма:
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
- Разработка Плана
- 2.7. Разработка анкеты
- 6. Разработка перспектив
- Разработка и принятие Основного закона
- Состояние научной разработки проблемы.
- Правило разработки веера версий