Accelerate Your Code 2012 - алгоритм.

draft

Конкурс подходит к концу, и сейчас уже можно безбоязненно рассказывать о своих идеях решения, чем мы (команда из Санкт-Петербургского Академического университета - Евгений Краско и Сергей Лазарев) и займемся. Простите нас за рисунки в пэйнте; надеюсь, на ясность изложения их наличие не повлияет. 

Предложенная на конкурсе Intel Accelerate Your Code задача была похожа на задачу нахождения кратчайшего пути во взвешенном графе. Однако, нельзя было считать полёты рёбрами, а города - вершинами. Существенным было то, что, во-первых, полёты совершались в фиксированное время и, попав в какой-то город, можно было улететь из него лишь некоторыми рейсами, а именно вылетающими не позже чем через определенное заранее известное время от момента прибытия (время пересадки). Во-вторых, стоимости полётов зависели от предыдущих совершённых полетов (и даже от последующих).

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

Итак, вершинами в графе будут полёты. Если быть точнее, каждый полёт будут представлен пятью вершинами. Каждая из пяти вершин для данного полёта будет иметь "тип". Тип ответственен за то, чтобы запомнить информацию о текущей последовательности полётов, которая влияет на получаемую скидку. Типы бывают следующими: первый полёт в последовательности полётов от одной авиакомпании (1); последующие полёты в такой последовательности (2); первый полёт в последовательности полётов от авиакомпаний, находящихся в альянсе (3); последующие полёты в такой последовательности (4); произвольный полёт (не имеющий скидки) (5). 

Рёбрами в графе будут соединены вершины, обладающие следующим свойством: можно лететь рейсом, представляющим первую вершину, после чего - рейсом, представляющим вторую вершину. Здесь учитывается и то, что мы не можем ждать в аэропорту слишком долго: у нас есть ограничение на время пересадки. Для корректного соединения нам понадобится информация о типах вершин. Допустим, два рейса таковы, что мы можем лететь ими последовательно, и они организованы одной авиакомпанией. Тогда нам нужно соединить вершину с типом 1 от первого рейса с вершиной типа 2 от второго рейса; вершину с типом 2 от первого рейса с вершиной типа 2 для второго рейса, и так далее. Перебрав все корректные комбинации, мы получим рёбра, соединяющие данные пятёрки вершин. Весом ребра назначим стоимость рейса, соответствующего вершине, в которую это ребро ведёт, умноженную на коэффициент скидки, определяемый из типа такой вершины. Добавив к полученному графу фиктивные вершины, соединенные с рейсами-кандидатами на отправление из дома и прибытие в город назначения, мы получим решение одной из подзадач: в данном графе мы можем искать кратчайшие пути между городами, и эти пути будут учитывать скидки на всех участвующих в них рейсах.

Однако, надо уметь не только искать кратчайшие пути между городами, но и посещать по дороге определенный город. Вначале решим подобную задачу для абстрактного графа G. Пусть нам нужно найти путь от вершины А до вершины В, проходящий через вершину С. Для этого можно использовать такой приём: скопируем граф G, получив графы G и G' (мы будем называть их "слоями"). Теперь соединим вершину C из первого слоя с соответствующей ей вершиной С' из второго слоя, а путь будем искать между вершинами А и В'. Понятно, что нет никакого другого способа перейти из первого слоя, откуда мы начали, во второй, куда нам надо попасть, кроме как как через вершину С. Аналогично можно поступить и в нашей задаче: соединим все вершины из первого слоя, отвечающие полётам, прибывающим на конференцию, с вершинами из второго слоя, отправляющимся из неё. В задаче Play Hard нам понадобится и третий слой, он будет учитывать прохождение нашего пути через место отдыха. Придется создать по два графа на каждый из городов, в которых можно отдыхать. В первом графе можно лететь сначала на отдых, потом на конференцию, во втором - наоборот.

Путь в получившемся трёхслойном графе можно искать, например, алгоритмом Дейкстры, после чего восстанавливать правильный ответ. 

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

如需更全面地了解编译器优化,请参阅优化注意事项