Проблема рейса в один конец

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

Мне действительно задали этот вопрос в интервью. Концепция чрезвычайно проста: каждый билет представляет собой одноэлементный список, с концептуально двумя элементы, src и dst.

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

необходимо соблюдать осторожность, чтобы сохранить инвариант, что ключи хэш-таблицы являются точно первыми и последними элементами оставшихся списков.

в целом, O (N).

и да, я ответил, что на месте :)

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

Изменить 2 также представляет интерес то, что по сравнению с решениями, использующими 2 хэш-таблицы с N записями каждого это решение использует хеш-таблицу с максимум N / 2 записей (что происходит, если мы видим билеты в порядке, скажем, 1-й, 3-й, 5-й, и так далее). Так что это использует около половины памяти, а также, помимо того, что быстрее.

построить две хэш-таблицы (или пытается), один ключ на src и другой на dst. Выберите один билет наугад и посмотрите его dst в таблице src-hash. Повторите этот процесс для получения результата, пока не дойдете до конца (конечного пункта назначения). Теперь посмотрите его src в хэш-таблице с DST-ключом. Повторяйте процесс для получения результата, пока не попадете в начало.

построение хэш-таблиц занимает O(n) и построение списка занимает O (n), поэтому весь алгоритм O (n).

EDIT: вам нужно только построить одну хэш-таблицу, на самом деле. Допустим, вы создаете хэш-таблицу с src-ключом. Выберите один билет наугад и, как и раньше, постройте список, который ведет к конечному пункту назначения. Затем выберите другой случайный билет из билетов, которые еще не были добавлены в список. Следуйте по его назначению, пока не попадете в билет, с которого вы изначально начали. Повторяйте этот процесс, пока не будет создан весь список. Это все еще O(n) с тех пор в худшем случае вы выбираете билеты в обратном порядке.

Edit: получил имена таблиц поменялись местами в моем алгоритме.

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

EDIT: хотя, поскольку это билет на самолет, и вы знаете, что на самом деле сделали маршрут, который вы могли бы физически выполнить, Сортировать по дате и времени вылета в UTC.

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

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

во-первых, XOR все коды аэропорта вместе. Это должно быть равно начальному исходному аэропорту X или конечному аэропорту назначения. Поскольку мы знаем, что начальный аэропорт и конечный аэропорт уникальны, это значение не должно быть равно нулю. Поскольку это не ноль, в этом значении будет установлен хотя бы один бит. Этот бит соответствует биту, который установлен в одном из аэропортов и не установлен в другом; назовите его битом обозначения.

далее создать два ведра, каждый со значением XORed с первого шага. Теперь для каждого билета ведро каждого аэропорта в соответствии с тем, имеет ли он бит обозначения или нет, и xor код аэропорта со значением в ведре. Также следите за каждым ведром, сколько аэропортов источника и аэропортов назначения отправились в это ведро.

после обработки всех билетов, выберите один из ведер. Число аэропортов-источников, отправленных в этот сегмент, должно быть на один больше или меньше числа пунктов назначения аэропорты отправили в это ведро. Если число исходных аэропортов меньше числа аэропортов назначения, это означает, что исходный аэропорт источника (единственный уникальный исходный аэропорт) был отправлен в другой сегмент. Это означает, что значение в текущем сегменте является идентификатором для исходного исходного аэропорта! И наоборот, если число аэропортов назначения меньше, чем число аэропортов источника, конечный аэропорт назначения был отправлен в другой сегмент, поэтому текущий сегмент является идентификатор аэропорта конечного назначения!

struct ticket
{
    int src;
    int dst;
};

int get_airport_bucket_index(
    int airport_code, 
    int discriminating_bit)
{
    return (airport_code & discriminating_bit)==discriminating_bit ? 1 : 0;
}

void find_trip_endpoints(const ticket *tickets, size_t ticket_count, int *out_src, int *out_dst)
{
    int xor_residual= 0;

    for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
    {
        xor_residual^= current_ticket->src;
        xor_residual^= current_ticket->dst;
    }

    // now xor_residual will be equal to the starting airport xor ending airport
    // since starting airport!=ending airport, they have at least one bit that is not in common
    // 

    int discriminating_bit= xor_residual & (-xor_residual);

    assert(discriminating_bit!=0);

    int airport_codes[2]= { xor_residual, xor_residual };
    int src_count[2]= { 0, 0 };
    int dst_count[2]= { 0, 0 };

    for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
    {
        int src_index= get_airport_bucket_index(current_ticket->src, discriminating_bit);

        airport_codes[src_index]^= current_ticket->src;
        src_count[src_index]+= 1;

        int dst_index= get_airport_bucket_index(current_ticket->dst, discriminating_bit);
        airport_codes[dst_index]^= current_ticket->dst;
        dst_count[dst_index]+= 1;
    }

    assert((airport_codes[0]^airport_codes[1])==xor_residual);
    assert(abs(src_count[0]-dst_count[0])==1); // all airports with the bit set/unset will be accounted for as well as either the source or destination
    assert(abs(src_count[1]-dst_count[1])==1);
    assert((src_count[0]-dst_count[0])==-(src_count[1]-dst_count[1]));

    int src_index= src_count[0]-dst_count[0]<0 ? 0 : 1; 
    // if src < dst, that means we put more dst into the source bucket than dst, which means the initial source went into the other bucket, which means it should be equal to this bucket!

    assert(get_airport_bucket_index(airport_codes[src_index], discriminating_bit)!=src_index);

    *out_src= airport_codes[src_index];
    *out_dst= airport_codes[!src_index];

    return;
}

int main()
{
    ticket test0[]= { { 1, 2 } };
    ticket test1[]= { { 1, 2 }, { 2, 3 } };
    ticket test2[]= { { 1, 2 }, { 2, 3 }, { 3, 4 } };
    ticket test3[]= { { 2, 3 }, { 3, 4 }, { 1, 2 } };
    ticket test4[]= { { 2, 1 }, { 3, 2 }, { 4, 3 } };
    ticket test5[]= { { 1, 3 }, { 3, 5 }, { 5, 2 } };

    int initial_src, final_dst;

    find_trip_endpoints(test0, sizeof(test0)/sizeof(*test0), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==2);

    find_trip_endpoints(test1, sizeof(test1)/sizeof(*test1), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==3);

    find_trip_endpoints(test2, sizeof(test2)/sizeof(*test2), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==4);

    find_trip_endpoints(test3, sizeof(test3)/sizeof(*test3), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==4);

    find_trip_endpoints(test4, sizeof(test4)/sizeof(*test4), &initial_src, &final_dst);
    assert(initial_src==4);
    assert(final_dst==1);

    find_trip_endpoints(test5, sizeof(test5)/sizeof(*test5), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==2);

    return 0;
}

создать две структуры данных:

Route
{
  start
  end
  list of flights where flight[n].dest = flight[n+1].src
}

List of Routes

и затем:

foreach (flight in random set)
{
  added to route = false;
  foreach (route in list of routes)
  {
    if (flight.src = route.end)
    {
      if (!added_to_route)
      {
        add flight to end of route
        added to route = true
      }
      else
      {
        merge routes
        next flight
      }
    }
    if (flight.dest = route.start)
    {
      if (!added_to_route)
      {
        add flight to start of route
        added to route = true
      }
      else
      {
        merge routes
        next flight
      }
    }
  }
  if (!added to route)
  {
    create route
  }
}

поставить в два хэша: to_end = src - > des; to_beg = des - > src

выберите любой аэропорт в качестве отправной точки S.

while(to_end[S] != null)
   S = to_end[S];

s теперь ваш конечный пункт назначения. Повторите с другой картой, чтобы найти начальную точку.

без правильной проверки это чувствует O (N), если у вас есть достойная реализация хэш-таблицы.

хэш-таблица не будет работать для больших размеров (таких как миллиарды в исходный вопрос); кто работал с ними знает, что они хороши только для небольших наборов. Вместо этого вы можете использовать двоичное дерево поиска, которое даст вам сложность O(N log n).

самый простой способ - с двумя проходами: первый добавляет их все в дерево, индексируемое src. Второй ходит по дереву и собирает узлы в массив.

можем ли мы сделать лучше? Мы можем, если действительно хотим к: мы можем сделать это за один проход. Представьте каждый билет в виде узла в списке избранных. Изначально каждый узел имеет нулевые значения для далее указатель. Для каждого билета введите в индекс его src и dest. Если есть коллизия, это означает, что у нас уже есть соседний билет; соедините узлы и удалите совпадение из индекса. Когда вы закончите, вы сделаете только один проход, и у вас будет пустой индекс и связанный список всех билетов по порядку.

этот метод значительно быстрее: это только один проход, а не два; и магазин значительно меньше (худший случай: n/2 ; лучший случай: 1; типичный случай: sqrt(n)), достаточно, чтобы вы могли фактически использовать хэш вместо двоичного дерева поиска.

каждый аэропорт-это node. Каждый билет-это edge. Составить матрицу смежности для представления графа. Это можно сделать в виде битового поля для сжатия краев. Вашей отправной точкой будет узел, который не имеет пути в него (это столбец будет пустым). Как только вы знаете это, вы просто следуете по пути, который существует.

поочередно вы можете построить структуру, индексируемую аэропортом. Для каждого билета вы смотрите вверх это src и dst. Если не нашли, то вам нужно чтобы добавить новые аэропорты в свой список. Когда каждый из них найден, вы устанавливаете указатель выхода аэропорта отправления, чтобы указать на пункт назначения, и указатель прибытия пункта назначения, чтобы указать на аэропорт отправления. Когда у вас нет билетов, вы должны пройти весь список, чтобы определить, у кого нет пути.

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

это простой случай матрицы конечного автомата с одним путем. Извините за псевдокод в стиле C#, но было проще выразить идею с помощью объектов.

во-первых, построить матрицу шлагбаум. Прочитайте мое описание того, что такое матрица магистрали (не беспокойтесь о ответе FSM, просто объяснение матрицы магистрали) в Каковы некоторые стратегии для тестирования больших государственных машин?.

тем не менее, ограничения, которые вы описываете сделать дело в простом однопутном состоянии машины. Это самый простой конечный автомат с полным покрытием.

для простого случая 5 аэропортов,
vert nodes=src / точки входа,
узлы horiz=DST / точки выхода.

   A1 A2 A3 A4 A5
A1        x
A2  x
A3           x
A4              x
A5     x

чтобы получить путь машины, вы бы отсортировать матрицу в

   A1 A2 A3 A4 A5
A2  x
A1        x
A3           x
A4              x
A5     x

или сортировать в a диагональная квадратная матрица-собственный вектор упорядоченных пар.

   A1 A2 A3 A4 A5
A2  x
A5     x
A1        x
A3           x
A4              x

где заказанные пары-это список билетов:

a2:a1, a5:a2, a1:a3, a3:a4, a4: a5.

или в более формальной нотации,

<a2,a1>, <a5,a2>, <a1,a3>, <a3,a4>, <a4,a5>.

Хммм .. заказывали пары да? Нюхая намек на рекурсию в Lisp?

<a2,<a1,<a3,<a4,a5>>>>

есть два режима работы машины,

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

я предполагаю, что ваш вопрос о реконструкции поездку. Итак, вы выбираете один билет за другим случайным образом из этой кучи билетов.

мы предполагаем, что куча билетов имеет неопределенный размер.

     tak mnx cda 
bom    0
daj       0
phi           0

где значение 0 означает неупорядоченные билеты. Давайте определим неупорядоченный билет как билет, где его dst не совпадает с src другого билета.

следующий следующий билет обнаруживает, что MNX(dst) = kul (src) соответствует.

     tak mnx cda kul
bom    0
daj       1
phi           0
mnx               0

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

<bom,tak>, <daj,<mnx,kul>>

и матрица уменьшено,

     tak cda kul
bom    0
daj          L1
phi       0

здесь

L1 = <daj,<mnx,kul>>

который является подсписком основного списка.

продолжайте выбирать следующие случайные билеты.

     tak cda kul svn xml phi
bom    0
daj          L1
phi       0
olm               0
jdk                   0
klm                       0

матч или нет.dst к новому.src
или существует.src для новых.ДСТ:

     tak cda kul svn xml
bom    0
daj          L1
olm               0
jdk                   0
klm      L2


<bom,tak>, <daj,<mnx,kul>>, <<klm,phi>, cda>

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

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

как вы видите, возможно, это лучше всего сделать с Lisp.

однако, как упражнение связанных списков и карт ...

создать следующие структуры:

class Ticket:MapEntry<src, Vector<dst> >{
  src, dst
  Vector<dst> dstVec; // sublist of mergers

  //constructor
  Ticket(src,dst){
    this.src=src;
    this.dst=dst;
    this.dstVec.append(dst);
  }
}

class TicketHash<x>{
  x -> TicketMapEntry;

  void add(Ticket t){
    super.put(t.x, t);
  }
}

так что эффективно,

TicketHash<src>{
  src -> TicketMapEntry;

  void add(Ticket t){
    super.put(t.src, t);
  }
}

TicketHash<dst>{
  dst -> TicketMapEntry;

  void add(Ticket t){
    super.put(t.dst, t);
  }
}    

TicketHash<dst> mapbyDst = hash of map entries(dst->Ticket), key=dst
TicketHash<src> mapbySrc = hash of map entries(src->Ticket), key=src

когда билет случайно выбран из кучи,

void pickTicket(Ticket t){
  // does t.dst exist in mapbyDst?
  // i.e. attempt to match src of next ticket to dst of an existent ticket.
  Ticket zt = dstExists(t);

  // check if the merged ticket also matches the other end.
  if(zt!=null)
    t = zt;

  // attempt to match dst of next ticket to src of an existent ticket.
  if (srcExists(t)!=null) return;

  // otherwise if unmatched either way, add the new ticket
  else {
    // Add t.dst to list of existing dst
    mapbyDst.add(t); 
    mapbySrc.add(t);
  }
}

проверьте наличие DST:

Ticket dstExists(Ticket t){
  // find existing ticket whose dst matches t.src
  Ticket zt = mapbyDst.getEntry(t.src);

  if (zt==null) return false; //no match

  // an ordered pair is matched...

  //Merge new ticket into existent ticket
  //retain existent ticket and discard new ticket.
  Ticket xt = mapbySrc.getEntry(t.src);

  //append sublist of new ticket to sublist of existent ticket
  xt.srcVec.join(t.srcVec); // join the two linked lists.

  // remove the matched dst ticket from mapbyDst
  mapbyDst.remove(zt);
  // replace it with the merged ticket from mapbySrc
  mapbyDst.add(zt);

  return zt;
}

Ticket srcExists(Ticket t){
  // find existing ticket whose dst matches t.src
  Ticket zt = mapbySrc.getEntry(t.dst);

  if (zt==null) return false; //no match

  // an ordered pair is matched...

  //Merge new ticket into existent ticket
  //retain existent ticket and discard new ticket.
  Ticket xt = mapbyDst.getEntry(t.dst);

  //append sublist of new ticket to sublist of existent ticket
  xt.srcVec.join(t.srcVec); // join the two linked lists.

  // remove the matched dst ticket from mapbyDst
  mapbySrc.remove(zt);
  // replace it with the merged ticket from mapbySrc
  mapbySrc.add(zt);

  return zt;
}

проверьте наличие src:

Ticket srcExists(Ticket t){
  // find existing ticket whose src matches t.dst
  Ticket zt = mapbySrc.getEntry(t.dst);

  if (zt == null) return null;

  // if an ordered pair is matched

  // remove the dst from mapbyDst
  mapbySrc.remove(zt);

  //Merge new ticket into existent ticket
  //reinsert existent ticket and discard new ticket.
  mapbySrc.getEntry(zt);

  //append sublist of new ticket to sublist of existent ticket
  zt.srcVec.append(t.srcVec);
  return zt;
}

у меня есть ощущение, что выше есть довольно много опечаток, но концепция должна быть правильной. Любая найденная опечатка, кто-то может помочь исправить ее, plsss.

самый простой способ - с хэш-таблицами, но это не имеет лучшей наихудшей сложности (O (n²))

вместо:

1. создать кучу узлов, содержащих (src, dst)O (n)
2. добавить узлы в список и Сортировать по src O (N log n)
3. для каждого (пункт назначения) узел, найдите в списке соответствующий (источник) узел о(n записей n)
4. найти начальный узел (например, с помощью топологической сортировки или обозначение узлов на Шаге 3) O (n)

в целом:O (N log n)

(для обоих алгоритмов мы предполагаем, что длина строк пренебрежимо мала, т. е. сравнение-O (1))

нет необходимости в хэшах или что-то подобное. Реальный размер ввода здесь не обязательно количество билетов (скажем n), но общий "размер" (скажем N) билетов, общее количество char нужно было их закодировать.

если у нас есть алфавит k символы (здесь k примерно 42) мы можем использовать методы bucketsort для сортировки массива n строки общего размера N что кодируется с алфавитом k символы O (n + N + k) времени. Следующие работы, если n (тривиально) и k (ж N миллиарды, не так ли)

1. в заказе билеты даются, извлечь все коды аэропорта из билетов и хранить их в struct который имеет код в виде строки и индекс билета в виде числа.
2. Bucketsort этот массив structs согласно к их коду
3. запустите корыто, что отсортированного массива и присвоить порядковый номер (начиная с 0) к каждому вновь встреченному коду авиакомпании. Для всех элементов с одинаковым кодом (они последовательны) перейдите к билету (мы сохранили номер с кодом) и измените код (выберите правильный,src или dst) билета на порядковый номер.
4. во время этого прогона через массив мы можем идентифицировать исходный источник src0.
5. теперь все билеты имеют src и dst переписываются как порядковые номера, и билеты могут быть интерпретированы как один список, начиная с src0.
6. сделайте рейтинг списка (= топлогическая сортировка с отслеживанием расстояния от src0) на билеты.

Если вы предполагаете объединяемую структуру списка, которая может хранить все (возможно, на диске):

1. создать 2 пустые хэш-таблицы S и D
2. возьмите первый элемент
3. посмотрите его src В D
4. если найдено, удалите связанный узел из D и свяжите его с текущим узлом
5. если не найдено, вставьте узел в S с ключом на src
6. повторите с 3 в другую сторону src des, S D
7. повторите от 2 со следующим узел.

O(n) времени. Что касается пространства, то парадокс дней рождения (или что-то нравится) будет держать ваш набор данных намного меньше, чем полный набор. В случае неудачи, когда он все еще доходит до большого (худший случай -O(n)), вы можете исключить случайные запуски из хэш-таблицы и вставить их в конец очереди обработки. Ваша скорость может пойти в банк, но до тех пор, пока вы можете далеко превзойти threashold для ожидающих столкновений (~O(sqrt(n))) следует ожидать ваш набор данных (таблицы и входная очередь вместе взятые) регулярно сжимаются.

Мне кажется, что здесь основан подход на основе графов.

каждый аэропорт-это узел, каждый билет-это ребро. Давайте сделаем каждый край неориентированным на данный момент.

на первом этапе вы строите график: для каждого билета вы ищете источник и пункт назначения и строите ребро между ними.

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

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

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

сложность этого алгоритма будет зависеть от времени, которое требуется для поиска конкретного узла. Если вы можете достичь O (1), то время должно быть линейным. У вас есть N билетов, поэтому вам потребуется O(N) шагов для построения графика, а затем O(N) для поиска и O(N) для восстановления пути. Все Еще O (N). Матрица смежности даст вам это.

Если вы не можете сэкономить место, вы можете сделать хэш для узлов, который даст вам O(1) под оптимальным хэшированием и всем этим дерьмом.

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

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

конечно, как только вы найдете источник, он также становится тривиальным вопросом проиндексировать и пройти весь маршрут, но с этого момента все это потребует, по крайней мере о(n) дополнительной памяти в любом случае (если конечно вы можете отсортировать данные в месте, которое, кстати, позволяет решить исходную задачу за o(n журнал N) время и O(1) дополнительной памяти)

давайте на мгновение забудем о структурах данных и графиках.

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

---

но давайте пока оставим это предположение.

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

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

---

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

src: A
dst: B

на самом деле это пара постановок:

A->AB
B->AB

, из которых вы можете сохранить только один.

Теперь вы должны генерировать каждое возможное предложение, но вы можете использовать каждое производственное правило один раз. Самое длинное предложение, которое использует каждое его производство только один раз, является правильным решением.

предпосылки

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

например, если ваша полная поездка a-b-c-d-e-f-g, подтрибунное может быть b-c-d, т. е. подключенный подпространство вашего путешествия.

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

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

строительство subtrips

теперь возьмите билеты только один за другим. Мы предполагаем, что билет от x до y (в лице (x,y)). Проверить, ли x это конец какой-то подтрибунки s(поскольку каждый город посещается только один раз, это не может быть конца еще одной подтрибунки уже). Если x это начало, просто добавьте текущий билет (x,y) в конце подтрибунного s. Если подтрибунное место не заканчивается на x, проверьте, есть ли подтрибунное t начиная с y. Если да, то добавьте (x,y) в начале t. Если и нет такого подтрибунного t, просто создайте новый подтрип, содержащий только (x,y).

работа с подтрипсами должна быть выполнена с использованием некоторых специальных "трюков".

• создание нового подтрибунного s содержащих (x,y) должны добавить x в хэш-таблицу для "subtrip beginning cities" и добавить y в хэш-таблицу для "городов с окончанием субтрипа".
• добавление нового билета (x,y) в начале подтрибунного s=(y,...), следует удалить y из хеш-таблицы начала городов и вместо этого добавить x к хэш-таблице начинающих городов.
• добавление нового билета (x,y) в конце subtrip s=(...,x), следует удалить x из хэш-таблицы конечных городов и вместо этого добавить y к хэш-таблице конечных городов.

С этой структурой подтрибы, соответствующие городу, могут быть выполнены в амортизированном O (1).

после того, как это будет сделано для всех билетов, у нас есть некоторые подтрибунные. Обратите внимание на то, что у нас есть самое большее (n-1)/2 = O(n) такие подтяжки после процедуры.

сцепление подтрибунных

теперь мы просто рассмотрим подтрибы один за другим. Если у нас есть подтрибунное s=(x,...,y), мы просто смотрим в нашей хэш-таблице конечных городов, если есть подтрибунное t=(...,x) заканчивая x. Если да, то мы объединяем t и s к новой подтрибунке. Если нет, то мы знаем, что s это наша первая подтрибунка; тогда мы смотрим, есть ли еще одна подтрибунка u=(y,...) начиная с y. Если да, то мы объединяем s и u. Мы делаем это до тех пор, пока не останется только одна подтрибунка (эта подтрибунка-тогда весь наш оригинал поездка.)

я надеюсь, что я не пропустил somtehing, но этот алгоритм должен работать в:

• построение всех подтрипов (не более O(n)) можно сделать в O(n), если мы реализуем добавление билетов в подтрибунное помещение в O(1). Это не должно быть проблемой, если у нас есть какая-то хорошая структура указателя или что-то в этом роде (реализация подтрипов в виде связанных списков). Также изменение двух значений в хэш-таблице является (амортизированным)O(1). Таким образом, эта фаза потребляет O(n) время.
• конкатенация подтрибуров до тех пор, пока не останется только один, также может быть выполнена в O(n). Слишком видеть это, нам просто нужно посмотреть, что делается на втором этапе: Hashtable lookups, которые нужно амортизировать O(1) и субтрип конкатенации, которые могут быть сделаны в O(1) С конкатенацией указателя или что-то в этом роде.

таким образом, весь алгоритм занимает время O(n), который может быть оптимальное O-связаны, так как по крайней мере каждый билет может нужно смотреть.

Я написал небольшую программу python, использует две хэш-таблицы один для подсчета, а другой для сопоставления src с dst. Сложность зависит от реализации словаря. если словарь имеет O (1) , то сложность равна O(n), если словарь имеет O( lg(n)), как в карте STL, то сложность равна O( n lg(n))

import random
# actual journey: a-> b -> c -> ... g -> h
journey = [('a','b'), ('b','c'), ('c','d'), ('d','e'), ('e','f'), ('f','g'), ('g','h')]
#shuffle the journey.
random.shuffle(journey)
print("shffled journey : ", journey )
# Hashmap to get the count of each place
map_count = {}
# Hashmap to find the route, contains src to dst mapping
map_route = {}

# fill the hashtable
for j in journey:
    source = j[0]; dest = j[1]
    map_route[source] = dest
    i = map_count.get(source, 0)
    map_count[ source ] = i+1
    i = map_count.get(dest, 0)
    map_count[ dest ] = i+1

start = ''
# find the start point: the map entry with count = 1 and 
# key exists in map_route.
for (key,val) in map_count.items():
    if map_count[key] == 1 and map_route.has_key(key):
        start = key
        break

print("journey started at : %s" % start)
route = [] # the route
n = len(journey)  # number of cities.
while n:
    route.append( (start, map_route[start]) )
    start = map_route[start]
    n -= 1

print(" Route : " , route )