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

А -> А
В -> Б
Б -> В

а получено это, потому что ранее мы запомнили предыдующую поездку:
А
Д
Б
В

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

Это задача с собеседования?

(1) нет, потребовалось прикрутить в ТиС порядок поездок.

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

А если есть две предыдущие поездки
1. А Д Б В
2. А Д В Б
Что делать?
Или клиент новый и в предыдущих поездках не фигурировал, куда его девать?

(3) Но свои мысли на этот счет есть?

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

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

Лучше, наверно, вести обновляемую и дополняемую единую карту упорядоченности.

Не уверен, что прав, но попробую.
На основании предыдущих перевозок определим ориентированный граф, в котором вершинами будут пункты доставки (контрагенты) + сама контора. Дуги могут идти между контрагентами и от конторы к контрагентам. Вес дуги - частота соответствующего развоза.
Если есть список контрагентов, то, дополнив его конторой получаем из этого графа подграф. Задача состоит с том, чтобы в этом подграфе выбрать цикл максимального веса.
Эта задача очень похожа на задачу коммивояжера. В теории это NP-трудная задача, но можно попробовать "жадный" алгоритм: выбирать следующим вершину максимального веса.
(7) Единая карта может оказаться не всегда "правильной": пример построить несложно, но лень.

(8) прошу прощения, но ИМХО это не совсем задача коммивояжера - в ней нет расстояний (только порядок) и стоит задача на основании известного порядка составить текущий вариант последовательности с учетом транзитивности. Если я не прав - прошу прощения.

(8) Зато она не такая громоздкая.

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

(11) известный порядок - это предыдущие отсортированные развозы (сначала вручную). Значит только коммивояжер?

(11) При сборе статистики будет более 10-ти точек.

(12) Подозреваю, что задача в постановке (8) эквивалента коммивояжеру (т.е. сводятся друг к другу).
(13) Речь о числе точек в развозе. Я плохо себе представляю машину, которая идет более чем по 10 адресам.

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

(12) опираться на уже извесный порядок не совсем разумно. Например: контрагенты А и В находстся в одном здании, но никогда не были в одной отправке вместе, но при этом часто встречались пути контора -> А -> С и контора -> С -> В.
Опираясь на историю программа выдаст путь А-С-В, что в корне неверно.

(15) Речь не о содержательном смысле задачи, а о ее математической постановке.

(14) В исторических данных может быть связь через отсутствующих в текущем списке контрагентов.

(18) Значит в подграфе этих связей не будет (как я понял ехать-то к ним нельзя).

(17) ну так как определиться с параметрами "оптимальности" маршрута? Для "матаматики" и нужен критерий оптимальности.

(19) Тогда получается совсем оторванная от реальности ерунда.

Хочу обратить внимание уважаемых специалистов, что все Ваши замечания о неполном решении задачи (при неполных входных данных) - верны, но лучше получить 3/4 решенной задачи, чем не решать её совсем. Неправильные (или неполные) результаты будут вручную откорректированы задним числом. Почему так: часть грузов поставляется своим автопарком и для них проблема "в каком порядке везти" - не существует, большая часть маршрутов привычна. Но регулярно приходится часть грузов развозить внешними водителями (по обьявлению), которые нужные нам адреса не знают и в случае неупорядоченного маршрута - ездят как попало, требуя почасовую оплату. Вот для них пригодится хоть какая сортировка.

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

(23)+ Вроде как и API есть для поиска кратчайшего пути (с учетом пробок).

(23) нифига не задача коммивояжера (особенно в чистом виде)

потому что нету заранее точек доставки )) с расстояниями ))

есть только последовательности старые, причем не факт что верные

а если например всегда из А ездили в В и потом в Г, и из Г ездили в Б, но это Б находится рядом с А и что?

Вместо А Б В Г будем ехать А В Г Б ?

Хоть задача и связана с маршрутами, но речь идёт о сортировке по образцу, а не оптимизации маршрута. Частное решение: комивояжер для статистики связей между ближайшими узлами.

(25) как это нет точек с расстояниями? или это не поездка клиентам последовательно?

(0) вообщем уходите от этих пар и последовательностей к маршрутам, по адресам...

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

(27) а так нету не сказано в (0) про расстояния

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

(29) тут расстояние = 1/частота

(30) +1

Можно искать в исторических данных расстановку, максимально покрывающую текущий набор конрагентов, потом так же уточнять детали для оставшихся. Да много чего ещё можно.

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

(34) ? не понял
у вас нет адресов контрагентов? и нет карты?

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

Да порядок цифр узнать можно?
Т.е. сколько у Вас всего контрагентов и из них постоянных которые хотя бы раз в неделю-две?

(34) Там факторов, кроме расстояния, вагон с тележкой. Лучше не заморачиваться.

(37)+ и сколько в среднем одна поездка контрагентов охватывает?

(38) да пробки это такая вещь не одного коммивояжёра сгубила ))

да почему бы не заюзать нечто вроде http://api.yandex.ru/maps/doc/jsapi/2.0/ref/reference/route.xml

(35) адреса есть, но они к карте не привязаны. В неделю на доставке от 100 до 200 клиентов, четверть из них - от 2 до 10 раз (тоже в неделю - разные адреса).

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

Насчет api яндекса - ему на вход нужны координаты, которых у меня нет.

(42) 200 клиентов привязать адреса это 3-4 часа работы...
получаются адреса для яндекса

их в прогу засунуть

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

(43)+ http://api.yandex.ru/maps/tools/getlonglat/
http://api.yandex.ru/maps/features/?p=geocode