Comments 21
Работа проделана интересная и, определённо, имеет полное право на жизнь.
Но, из всех предложенных алгоритмом тестовых вариантов лично я бы выбрал второй вариант, с «полу-часовой» пересадкой.
Подходящих нам рейсов из ГабенБурга в ЛосПаганос всего 2 — на 20:30 (основной) и 21:00 (добавочный). Есть шанс, что большинство пассажиров поедет на первом автобусе — на втором будет комфортнее.
Мы уже ехали 2 часа — надо размяться, сходить в туалет (а там зачастую очереди), перекусить (там тоже очереди) — поэтому пересадка длительностью 40 минут будет оптимальнее, чем пересадка в 10 минут.
В пути бывают разные непредвиденные ситуации, и автобус из СанКомарика элементарно может опоздать на рейс в 20:30 в ГабенБурге.
Прибытие в 5:20 нам не добавляет существенных преимуществ над прибытием в 5:55 — т.к. городской транспорт полноценно начинает ходить с 6 утра — те же самые 30 минут ожидания, что мы провели на пересадке. Либо вызывать такси.
Бонусом: поездка чуточку дешевле.
Первый элемент и будет самым оптимальным рейсом
Лучше оставить разницу хотя бы в пять, а лучше 10 минут: если ваш автобус хоть немного опоздает (а это весьма вероятно), то можно только помахать ручкой следующему.
Я согласен с комментарием о временном окне на пересадку. Важно учитывать не только возможные опоздания, но и наличие альтернативных вариантов в случае задержки автобуса. А ещё размеры автостанции для пересадки тоже важны. Куда приходят рейсы, которые стыковало наше расписание? Может, это одна остановка или соседние «терминалы», а может, надо идти минимум 10 минут.
Нужно оценить, что делать, если рейс для пересадки отменён или по какой-то причине вы на него опоздали. Например, если следующий подходящий рейс будет только через 12 или 24 часа, стоит ли рисковать и экономить 15 минут?
А есть ещё проходящие автобусы. Существуют города где >1 автостанция. Существуют, кроме автобусов, железные дороги. И воще самое интересное в этой задаче - парсить сайты разных перевозчиков.
Походу кто-то начал ходить по собеседованиям ;)
Статья в целом простая, но сильно отличается от большинства современных публикаций на Хабре.
Был ли использован ретро-стиль намеренно?
Я решил положить этому конец и распетлять задачу при помощи ЭВМ.
В итоге мы имеем консольную утилиту и вывод таблиц с использованием псевдографики. При этом не используются большие языковые модели (LLM). Нет обмена сообщениями в формате JSON (или SOAP 😁 , или XML, или gRPC). Не надо задавать входные параметры "простым" YAML- файлом на пару экранов. Не разрабатывается RESTful-сервис. Не создается Docker-контейнер. И не запускается Telegram-бот. Даже веб-сайт для расчёта расписания не публикуется.
А ещё Стиль текста немного академичен. Вы точно не нашли это на старом харде в своих черновиках за 1997 год? 😁😁😁
В любом случае Олдскул-респект! 😃
А нужна ли тут, с точки зрения алгоритмов, вообще сортировка? Поиск минимума это линейнное время. О(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) Стоимость часа ожидания: сколько вы хотите минимально сэкономить, если ожидание удлинится на час сверху минимального времени?
Задача о Выборе Билетов