Формулировка задачи

Ситуацию можно смоделировать на очень общем уровне, абстрагируясь от кон- кретных правил о времени технического обслуживания и промежуточных сег- ментов: мы просто говорим, что рейс j доступен из рейса i, если самолет, ис- пользовавшийся для рейса i, также может использоваться для полета j.
Итак, по приведенным выше правилам (a) и (b) для каждой пары ij можно легко опреде- лить, доступен ли рейс j из рейса i. (Конечно, правила доступности могут быть намного более сложными. Например, время технического обслуживания в слу- чае (a) может зависеть от аэропорта, или случай (b) может потребовать, чтобы вставленный сегмент обеспечивал необходимую прибыль.) Здесь важно то, что наше определение позволяет обработать любой набор правил: входные данные задачи включают не только множество сегментов, но и спецификацию пар (i, j), для которых более поздний рейс j достижим из более раннего рейса i. Такие пары могут образовать произвольный ациклический граф.

В этой задаче требуется определить, возможно ли организовать все m рейсов из исходного списка с использованием не более к самолетов. Для этого необходимо найти способ эффективного повторного использования самолетов в разных рейсах. Например, вернемся к экземпляру на рис. 7.17 и предположим, что самолетный парк состоит из к = 2 самолетов. Если использовать один самолет для рейсов (1), (3) и (6), как предполагалось выше, другой самолет не сможет обслужить все остальные полеты (2), (4) и (5) (ему не хватит времени на техническое обслужи- вание в Сан-Франциско между рейсами (4) и (5)). Однако обслужить все шесть рейсов с двумя самолетами все же возможно, если воспользоваться другим реше- нием: один самолет обслуживает рейсы (1), (3) и (5) (с включением промежуточ- ного рейса LAX-SFO), а другой обслуживает рейсы (2), (4) и (6) (с включением промежуточных рейсов PIT-PHL и SFO-LAS).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Формулировка задачи:

  1. Глава 3. ФОРМУЛИРОВКА ВОПРОСОВ И КАЧЕСТВО АНКЕТЫ
  2. 4.3. «Эффект имени» при формулировке вопросов
  3. Требование формулировки "по Уставу"
  4. 3.1. Основные правила формулировки вопросов1
  5. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  6. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  7. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  8. ЗАДАЧА
  9. ЗАДАЧА: РЕШЕНИЕ
  10. Основные задачи.
  11. в) Задачи
  12. в) Задачи
  13. ПСИХОАНАЛИЗ: ЗАДАЧА
  14. Задачи и упражнения
  15. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  16. Основные задачи
  17. § 3. СТРУКТУРА РЕШЕНИЯ ПЕДАГОГИЧЕСКИХ ЗАДАЧ