Разработка алгоритма

В этом разделе рассматривается эффективный алгоритм, позволяющий решать произвольные экземпляры задачи планирования авиаперелетов на основании потока в сети. Вы увидите, что потоковые методы чрезвычайно естественно адап- тируются к этой задаче.

Решение основано на следующей идее: единицы потока соответствуют самоле- там. Для каждого рейса создается ребро, а верхняя и нижняя границы пропускной способности, равные 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

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Разработка Плана
  13. 2.7. Разработка анкеты
  14. 6. Разработка перспектив
  15. Разработка и принятие Основного закона
  16. Состояние научной разработки проблемы.
  17. Правило разработки веера версий