28 ноября, 2020 
rius 
В этой заметке я разберу решение задачи о доставщике покупок. В качестве задания он получает список адресов. Для простоты считаем, что дома на этих улицах (и четные и нечетные) расположены подряд на одной стороне улицы. В качестве параметра вводится макс. расстояние, на которое курьер может отойти пешком от машины. Требуется выдать курьеру план остановок (адреса этих остановок) — такой, чтоб их количество было минимальным.
Сразу надо отметить, что ничего не говорится о том, что курьер должен пройти минимальное расстояние. Но если на текущей улице осталась один непосещенный дом, то можно остановиться прямо рядом с ним.
Пример исходного списка с адресами доставок такой (сначала идет дом, потом название улицы):
48 Rodney st 45 Rodney st 54 Rodney st 60 Rodney st 51 Rodney st 53 Rodney st 52 Rodney st 54 Rodney st 56 Guy st 51 Rodney st 1030 Guy st 1026 Guy st 1027 Guy st 1032 Guy st |
Можно полагаться на то, что одна и та же улица всегда будет обозначаться одинаково.
Сразу понятно, что если улица хотя бы раз упоминается в списке, то на ней придется сделать остановку.
Что касается введенного радиуса (максимального пешего расстояния курьера), то он работает так. Допустим, радиус равен 3 и курьер остановился у дома № 50. Это означает, что курьер потенциально сможет доставить товары в дома 48, 49, 50, 51, 52 (если они есть в его списке доставок). Т.е. проверяется попадание в окружность радиуса (r-1).
Первым делом надо распределить все адреса по улицам, а для каждой улицы упорядочить список по возрастанию (или убыванию) номеров домов. Это делается с помощью stream api:
// for each street compose a set of unique addresses, ordered by house number Map<string, set<addressitem="">> map = addressItemList .stream() .collect(Collectors.groupingBy(AddressItem::getStreet, Collectors.toCollection(()-> new TreeSet<>(new AddressItemComparator())))); </string,> |
Далее действия для каждой улицы. Если на этой улицы единственный непосещеный адрес, то останавливается прямо у этого дома. Помечаем адрес, как посещенный. Если есть несколько непосещенных адресов, то берем адрес с минимальным номером и останавливаемся на максимальном отдалении от него (в сторону увеличения адресов) — таком, при котором по условиям курьер еще может дойти до него с учетом максимального пешего расстояния. Помечаем все достижимые для этой остановки дома, как посещенные. Если на улице есть еще непосещенные адреса, то повторяем действия. Если непосещенных адресов нет, переключаемся на следующую улицу. Это все делается в методе PathSearcher.process().
Исходники тут (не забудьте поменять название пакета на своё): https://github.com/dk2k/java_experiments/tree/master/algo_delivery_stops
Posted in 
Tags: