Pull to refresh

Comments 21

Работа проделана интересная и, определённо, имеет полное право на жизнь.
Но, из всех предложенных алгоритмом тестовых вариантов лично я бы выбрал второй вариант, с «полу-часовой» пересадкой.

  1. Подходящих нам рейсов из ГабенБурга в ЛосПаганос всего 2 — на 20:30 (основной) и 21:00 (добавочный). Есть шанс, что большинство пассажиров поедет на первом автобусе — на втором будет комфортнее.

  2. Мы уже ехали 2 часа — надо размяться, сходить в туалет (а там зачастую очереди), перекусить (там тоже очереди) — поэтому пересадка длительностью 40 минут будет оптимальнее, чем пересадка в 10 минут.

  3. В пути бывают разные непредвиденные ситуации, и автобус из СанКомарика элементарно может опоздать на рейс в 20:30 в ГабенБурге.

  4. Прибытие в 5:20 нам не добавляет существенных преимуществ над прибытием в 5:55 — т.к. городской транспорт полноценно начинает ходить с 6 утра — те же самые 30 минут ожидания, что мы провели на пересадке. Либо вызывать такси.

  5. Бонусом: поездка чуточку дешевле.

Первый элемент и будет самым оптимальным рейсом

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

Я согласен с комментарием о временном окне на пересадку. Важно учитывать не только возможные опоздания, но и наличие альтернативных вариантов в случае задержки автобуса. А ещё размеры автостанции для пересадки тоже важны. Куда приходят рейсы, которые стыковало наше расписание? Может, это одна остановка или соседние «терминалы», а может, надо идти минимум 10 минут. 

Нужно оценить, что делать, если рейс для пересадки отменён или по какой-то причине вы на него опоздали. Например, если следующий подходящий рейс будет только через 12 или 24 часа, стоит ли рисковать и экономить 15 минут? 

А есть ещё проходящие автобусы. Существуют города где >1 автостанция. Существуют, кроме автобусов, железные дороги. И воще самое интересное в этой задаче - парсить сайты разных перевозчиков.

Походу кто-то начал ходить по собеседованиям ;)

Походу кто-то начал ходить по собеседованиям ;)

Ездить же на автобусе, а не ходить

Ездить же на автобусе

в другой город с пересадкой ;)

Это и есть настоящий олдскульный подход

Статья в целом простая, но сильно отличается от большинства современных публикаций на Хабре.

Был ли использован ретро-стиль намеренно?

Я решил положить этому конец и распетлять задачу при помощи ЭВМ.

В итоге мы имеем консольную утилиту и вывод таблиц с использованием псевдографики. При этом не используются большие языковые модели (LLM). Нет обмена сообщениями в формате JSON (или SOAP 😁 , или XML, или gRPC). Не надо задавать входные параметры "простым" YAML- файлом на пару экранов. Не разрабатывается RESTful-сервис. Не создается Docker-контейнер. И не запускается Telegram-бот. Даже веб-сайт для расчёта расписания не публикуется. 

А ещё Стиль текста немного академичен. Вы точно не нашли это на старом харде в своих черновиках за 1997 год? 😁😁😁

В любом случае Олдскул-респект! 😃

Илон из 1997 тоже поддерживает Вас. 😁
Илон из 1997 тоже поддерживает Вас. 😁
Просто отходил ненадолго сделать пару затяжек
Просто отходил ненадолго сделать пару затяжек

А куда дели Илона из 2002?

Вернули

Видим минусы по ветке комментариев...

Маск из 2020 искренне не понимает кому может не нравиться Маск из 2002.  Но в целом ему на это наплевать
Маск из 2020 искренне не понимает кому может не нравиться Маск из 2002. Но в целом ему на это наплевать

А нужна ли тут, с точки зрения алгоритмов, вообще сортировка? Поиск минимума это линейнное время. О(n).

Количество автобусных рейсов не миллионы. Можно и сортировку по сталински задействовать ;)

Если вам хочется тоже воспользоваться этой простой утилитой или протестировать её, то бинарь можно скачать тут.

А бинарь только по Виндовс?

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

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

А ещё - при решении подобной задачи стабильная сортировка не нужна. Её надобность (и кстати, достаточно сомнительная) в данной конкретной статье определяется как раз отсутствием критерия оптимальности.

Отсортировать по функции оптимальности и выбрать первый элемент в массиве.

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

Это и быстрее и писать проще. И не надо вообще вводить определение стабильных сортировок (кстати, а зачем вам именно стабильная сортировка?)

Можно получать 2 минимальных элемента так же просто. В общем случае можно получить k минимальных элелементов с использованием кучи или quick_select, но тут уже будет код сложнее наивной сортировки.

Далее, задача проанализирована слабо и решена не оптимльно. Можно было бы воспользоваться свойствами вашего критерия оптимальности и ограничений задачи. Вот у вас ровно одна пересадка разрешена. Тогда надо разбить все рейсы на start->x и x->end. Все остальные просто игнорировать. Потом надо разбить их в группы по х и там внутри группы отсортировать.

Потом можно для каждого города-пересадки методом двух указателей перебирать рейсы туда и оттуда - вам же среди всех рейсов оттуда надо брать ближайший ко времени прибытия туда, вы же сначала минимизируете время пересадки. И вот уже вместо O(N^2 log N) (или O(N^2), если выкинуть сортировку) у вас решение за O(N log N).

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

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

кстати, а зачем вам именно стабильная сортировка?

Критерий оптимальности такой:
—Сначала сортируем по цене. Приоритет дешевым билетам.
—Затем сортирует по длительности пересадки. При одинаковой цене предпочтение отдаем тому набору билетов, где пересадка короче.

Вот и получается, что надо последовательно сделать две сортировки: по цене и по длительности пересадки ожидания.

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

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

Просто у вас сравнение будет составное, лекикографическое: (a1,a2) < (b1, b2) тогда и только тогда, когда a1 < b1 или a1==b1 и a2 < b2. Т.е. при сравнении двух вариантов сравниваете цену, если она совпала - сравниваете длительность пересадки.

По сравнению с несколькими последовательными сортировками тут будет меньше сравнений, меньше перемещений данных, меньше кода и все будет концептуально проще.

Смущает, что сначала выбирается минимальная цена, а потом длительность пересадки. Если экономия в 1 руб увеличит время на пересадку на 20 минут, не все согласятся с таким подходом.

Оптимально задать: 1) минимальное время на пересадку, чтобы убрать риск не успеть;

2) Стоимость часа ожидания: сколько вы хотите минимально сэкономить, если ожидание удлинится на час сверху минимального времени?

Sign up to leave a comment.

Articles