Это простой случай матрицы конечного автомата.
Извините за псевдокод в стиле C #, но было проще выразить идею с помощью объектов.
Сначала построим матрицу магистрали.
Прочитайте мое описание того, что такое матрица магистрали (не беспокойтесь с ответом FSM, просто объяснение матрицы магистрали) на Какие существуют стратегии для тестирования больших конечных автоматов? .
Однако описанные вами ограничения делают случай простым конечным автоматом. Это самый простой конечный автомат из всех возможных.
Для простого случая 5 аэропортов,
вершинные узлы = src / точки входа,
узлы горизонта = 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
Или рассортировать по диагональной квадратной матрице - собственному вектору упорядоченных пар.
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>.
Хммм .. заказал пары, а? Чувствуете ли вы намек на рекурсию в Лиспе?
<a2,<a1,<a3,<a4,a5>>>>
Есть два режима работы машины,
- планирование поездки - вы не знаете, как
Есть много аэропортов, и вы
нужен общий план поездки для
не указано количество аэропортов
- реконструкция поездки - у вас есть все
билеты на прошлую поездку
но они все один большой стек
ваш бардачок / багажная сумка.
Полагаю, ваш вопрос касается реконструкции поездки. Таким образом, вы выбираете один билет за другим случайным образом из этой стопки билетов.
Мы предполагаем, что стопка билетов имеет неопределенный размер.
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
Сопоставить либо existing.dst с новым.src
или existing.src для new.dst:
tak cda kul svn xml
bom 0
daj L1
olm 0
jdk 0
klm L2
<bom,tak>, <daj,<mnx,kul>>, <<klm,phi>, cda>
Вышеуказанное топологическое упражнение предназначено только для визуального понимания. Ниже приведено алгоритмическое решение.
Идея состоит в том, чтобы объединить упорядоченные пары в подсписки, чтобы уменьшить нагрузку на хеш-структуры, которые мы будем использовать для размещения билетов. Постепенно будет появляться все больше и больше псевдо-билетов (сформированных из объединенных совпадающих билетов), каждый из которых будет содержать растущий список заказанных мест назначения. Наконец, останется один-единственный псевдо-билет, содержащий полный маршрутный вектор в своем подсписке.
Как видите, возможно, это лучше всего сделать с Лиспом.
Однако, как упражнение связанных списков и карт ...
Создайте следующие структуры:
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;
}
Проверка существующего источника:
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.