Разбор алгоритмической задачи про курьера

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

Сразу надо отметить, что ничего не говорится о том, что курьер должен пройти минимальное расстояние. Но если на текущей улице осталась один непосещенный дом, то можно остановиться прямо рядом с ним.
Пример исходного списка с адресами доставок такой (сначала идет дом, потом название улицы):

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

You can leave a response, or trackback from your own site.

Leave a Reply