Accelerate Your Code Late 2012: Решение нашей команды

Авторы: Николай Кузнецов, Кристина Дмитрашко. Декабрь, 2012

Официальная страница конкурса

Условие задачи

Постановка задачи

Итак, представьте себе, что вы живете в Берлине и должны поехать на софтверную конференцию в Сан-Франциско. Задача найти самый дешевый билет на прямой рейс нас не интересует как неспортивная, но возможны варианты. Допустим, у вас есть некий запас времени после конференции и возможность потратить несколько больше, чтобы по пути заехать в какое-нибудь интересное место. Например, вы выяснили, что маршрут Берлин – Сан-Франциско – Сан-Паоло – Берлин обойдется вам всего на 100 евро дороже, чем прямой. Это ли не повод задержаться на лишнюю недельку? Непрямой маршрут предполагает пересадки и, как следствие, возможность использования нескольких авиакомпаний; цена одного перелета зависит от того, каким перевозчиком вы полетите остальные. Если все поездки будут совершены на самолетах одной компании, это обойдется на 30 процентов дешевле. Кроме того, авиакомпании объединяются в "альянсы", чтобы предложить пассажирам более выгодные условия при использовании рейсов только этого "альянса" --- экономия составит 20 процентов.

Задача "Напряженно работаем"

Найти самые дешевые перелеты между двумя городами.

Задача "Изо всех сил отдыхаем"

Задавшись минимальной и максимальной продолжительностью отдыха (до или после рабочей поездки), а также списком интересующих аэропортов, предложить самый дешевый вариант перелета для каждого аэропорта.

Входные данные

Входные данные представлены двумя файлами, в первом даны описания авиарейсов, а во втором --- описания альянсов среди авиакомпаний. Описание каждого авиарейса состоит из нескольких полей: уникальный идентификатор рейса, аэропорт вылета, время вылета, аэропорт прилета, время прилета, базовая стоимость билета и авиакомпания-собственник. Описание каждого альянса представляет собой набор авиакомпаний. Каждая авиакомпания может быть в нескольких альянсах.

Параметры запуска программы также содержат входные данные: аэропорт, откуда вы вылетаете from, аэропорт, где проходит конференция to, ограничения на время перелета на конференцию (depTimeMin и depTimeMax) и обратно домой (arTimeMin и arTimeMax), максимальное время ожидания в аэропорту (maxLayoverTime), ограничения на время отпуска (vacationTimeMin и vacationTimeMax), список возможных городов для отпуска.

Решение задачи

 

Модель

Пусть v - это идентификатор любого авиарейса, тогда введем обозначения:

  • cityOut(v) - аэропорт вылета рейса v;
  • timeOut(v) - время вылета рейса v;
  • cityIn(v) - аэропорт прилета рейса v;
  • timeIn(v) --- время прилета рейса v.

Для описания системы авиарейсов используем понятия теории графов, то есть представим ее как ориентированный взвешенный граф, вершинами которой являются идентификаторы рейсов. Введем типы вершин: вершина v имеет тип 0, если timeIn(v) <= depTimeMax, имеет тип 1, если arTimeMin <= timeOut(v), и имеет тип -1 во всех остальных случаях.

От вершины v проведем ребро в вершину u, если существует возможность после рейса v продолжить путешествие на рейсе u. Более формально, ребро (v, u) принадлежит графу, если:

  • cityIn(v) = cityOut(u);
  • timeIn(v) < timeOut(u);
  • timeOut(u) - timeIn(v) <= maxLayoverTime.

Кроме того, добавим в этот граф ребра особого вида, которые будут означать пребывание на конференции. Ребро (v, u) добавим, если:

  • cityIn(v) = cityOut(u) = to;
  • typeOf(v) = 0, то есть timeIn(v) <= depTimeMax;
  • typeOf(u) = 1, то есть timeOut(u) => arTimeMax.

Тогда очевидно, что любое из путешествий на конференцию и обратно представляет собой последовательность вершин v1, v2, ..., vi, vi+1, vi+2, ..., vk, в которой вершины v1, v2, ..., vi имеют тип 0, а последовательность вершин vi+1, vi+2, ..., vk имеют тип 1, и для любыx двух последовательныx вершин vj и vj+1 ребро (vj, vj+1) существует в графе. Кроме того, cityOut(v1) = cityIn(vk) = from и cityIn(vi) = cityOut(vi + 1) = to

Итак, задача "Напряженно работаем" состоит в том, что необходимо найти минимальное по стоимости путешествие с учетом условий depTimeMin <= timeOut(v1), timeIn(vk) <= arTimeMax.

Пусть в текущей задаче "Изо всех сил отдыхаем" мы хотим провести отпуск в городе w. Тогда существует два возможных решения: в первом из них наш путь будет from -> w -> to -> from, а во втором - from -> to -> w -> from.

Первый путь формально соответствует условию: существует такое 1 <= j < i, что:

  • cityIn(vj) = cityOut(vj+1) = w;
  • depTimeMin - vacationTimeMax <= timeOut(v1);
  • timeIn(vj) <= depTimeMin - vacationTimeMin;
  • depTimeMin <= timeOut(vj+1);
  • остальные выше описанные условия остаются в силе.

А второй путь соответствует условию: существует такое i < j < k, что:

  • cityIn(vj) = cityOut(vj+1) = w;
  • timeIn(vj) <= arTimeMax;
  • arTimeMax + vacationTimeMin <= timeOut(vj+1);
  • timeIn(vk) <= arTimeMax + vacationTimeMax;
  • остальные выше описанные условия остаются в силе.

Необходимо найти минимальные по стоимости путешествие в каждом из случаев и выбрать среди них.

Алгоритм

Для начала опишем правила вычисления скидки на рейсы. Согласно правилам, коэффициент для текущего рейса зависит только от авиакомпании-собственника предыдущего, текущего и следующего рейса. Точнее costCoeff(vi) = min(coeff(vi-1, vi), coeff(vi, vi+1)), где coeff(vi, vj) равно:

  • 0.7, если рейсы vi и vj принадлежат одной компании;
  • 0.8, если рейсы vi и vj принадлежат одному альянсу;
  • 1.0, в остальных случаях.

Таким образом для поиска наименьшего по стоимости путешествия необходимо хранить два последних рейса в пути, и отдельно перебирать следующий рейс. Однако если в исходном графе количество вершин равно n, то в подобным образом трансформированном графе количество вершин сильно возрастает, и даже может достичь величины O(n2). Очевидно, что такой способ не годится.

Трансформируем граф другим образом: каждая из вершин разделим на три, то есть вершинами нового графа являются пары (v, discount), где discount принимает значения: 0 (предыдущий рейс перед v принадлежит той же компании, что и v), 1 (предыдущий рейс принадлежит компании из одного альянса с компанией-собственником рейса v), 2 (в остальных случаях). Таким образом, если в исходном графе количество вершин равно n, то в преобразованном графе количество вершин составляет 3 * n, что приемлимо, но перебирать следующий рейс все равно необходимо.

Сначала опишем решение задачи «Напряженно работаем». Ответом на эту задачу будет являться наименьший по стоимости путь из любой вершины (vs, 2) при условиях depTimeMin <= timeOut(vs) и typeOf(vs)=0 (назовем такие вершины стартовыми) до вершины (vt, discount) (discount - любое целое число от 0 до 2) при условиях timeIn(vt) <= arTimeMax, typeOf(vt)=1. Такой путь несложно найти любым алгоритмом поиска кратчайших путей в графах. Если говорить точнее, то для нахождения такого пути необходимо запустить выбранный алгоритм сразу из всех стартовых вершин, то есть построить матрицу D1, где D1[v][discount] означает минимальную стоимость пути от любой из стартовых до (v, discount).

Каждое решение задачи «Изо всех сил отдыхаем» немного сложнее. Сначала попробуем найти решение вида from -> w -> to -> from, где w - текущий город для отпуска. Для этого необходимо решить две подзадачи:

  • запустим алгоритм SSSP из всех стартовых вершин вида (vs, 2) при условиях depTimeMin - vacationTimeMax <= timeOut(vs) и typeOf(vs)=0, таким образом подсчитав матрицу D2;
  • вторая подзадача будет чуть другая: запустим алгоритм SSSP по обратным ребрам из всех стартовых вершин вида (vs, 2) при условиях timeOut(vs) <= arTimeMax и typeOf(vs)=1, таким образом подсчитав матрицу D3.

Для ответа на задачу переберем пару вершин v и u, означающие, как мы прилетели в город w и как улетели соответственно. То есть формально:

  • cityIn(v) = cityOut(u) = w;
  • timeIn(v) <= depTimeMin - vacationTimeMin;
  • depTimeMin <= timeOut(u);

Возможным ответом будет минимальное значение суммы D2[v][discountv] + D3[u][discountu] + sale(v, discountv, u, discountu), где sale(v, discountv, u, discountu) означает пересчитанное значение стоимостей v и u с учетом взаимной скидки. Решение вида from -> to -> w -> from находится аналогично, если предподсчитать еще две матрицы, причем, можно заметить что одна из них будет в точности совпадать с D1, и поэтому достаточно предподсчитать четыре матрицы вместо пяти.

А кроме того, несложно заметить, что все эти матрицы не зависят от положения города w, а это значит, что их достаточно найти один раз, еще до того, как будем искать ответы на задачи.

Итого, используя любой алгоритм SSSP, нам необходимо подсчитать четыре матрицы, и используя их, мы можем найти все ответы.

Теперь немного о выбранном алгоритме SSSP. Одним из подобных является алгоритм Дейкстры, который решает задачу SSSP за O(log(n) * (n + m)), где n - количество вершин в графе, m - количество ребер. Однако в данном случае он неприменим, так как в графе могут появиться ребра отрицательного веса, это может случиться при пересчете стоимости рейса с учетом следующего рейса и правила скидок.

Однако заметим очень и очень важный факт про граф: он ацикличен. То есть если вы сели на рейс v, то выйдя из самолета, вы никогда не сможете снова его использовать, так как его время вылета заведомо прошло. Как известно, задача SSSP на ациклическом графе может быть решена за O(n+m) с помощью динамического программирования. В нашем случае это значит, что мы будем рассматривать вершины в порядке возрастания timeOut(v), и каждый раз пытаться уменьшать значения в матрице по исходящим ребрам из текущей вершины.

Таким образом, все четыре необходимые матрицы можно найти за время O(n + m), используя не более O(n) памяти. Очевидно, что асимптотически лучшего алгоритма придумать не получится.

Использование многопоточности в алгоритме

В нашем решении многопоточность используется только для подсчета матриц D1, D2, D3 и D4, таким образом из числа доступных потоков мы используем не более четырех. Существуют алгоритмы и методы параллелизации алгоритма Дейкстры и подобных, и мы их рассматривали, а некоторые даже реализовывали, но на предоставленных входных данных реализация оказалась неэффективна, и мы решили не использовать подобные алгоритмы.

Также можно было реализовать параллелизацию задач «Изо всех сил отдыхаем», но так как наш алгоритм и так мгновенно отвечает на запросы, то это также было признано неэффективным.

Оптимизации

Пожалуй, одна из самых главных оптимизаций --- это отсечение заведомо не подходящих рейсов во время подсчета матриц, поиска ответов на задачи и т.д. Так как граф рейсов естественный и не содержит хитрых случаев, то подобная оптимизация очень сильно сокращает время работы решения.

Но самой долгой операцией является чтение входных данных. В решении необходимо отказаться от использования библиотек iostream, fstream и подобных, а использовать ввод-вывод из библиотеки stdio. Кроме того мы использовали технологию «memory-mapped-file», которая увеличивает скорость чтения данных из файла.

Вторым «узким местов» в чтении помимо iostream являются функции преобразования времени, их также необходимо заменить на другие, в данном случае на самостоятельно написанные. Сравним скорости чтения данных:

  • с использованием fstream --- ~70 секунд;
  • с использованием stdio --- ~30 cекунд;
  • с использованием stdio и собственными функциями преобразования времени --- ~1 секунда.

Данные были подсчитаны для входных данных суммарным размером около 40 мегабайт, число рейсов --- порядка 250-300 тысяч. Нельзя не отметить значительной роли инструмента Intel Parallel Amplifier из набора Intel Parallel Studio в разработке нашего решения. Именно с помощью этого продукта мы находили «узкие места» в нашей программе, оптимизировали их и в итоге снизили общее время работы программы на 30-40 процентов. Хотим заметить, что без использовании подобных инструментов разработки почти невозможно сильно уменьшить время работы, так как программист будет вынужден работать вслепую и только догадываться о реальных проблемах в разрабатываемой программе.

 

Einzelheiten zur Compiler-Optimierung finden Sie in unserem Optimierungshinweis.