aabzel вчера в 00:21

Задача о Выборе Билетов

Простой

6 мин

1.5K

Занимательные задачкиАлгоритмы*Математика*

Туториал

Пролог

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

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

Постановка задачи

Надо доехать из города A в город C. При этом надо совершить пересадку в городе B. На сайтах есть множество билетов в направлении A->B и B->C. Надо выбрать два билета так чтобы:

1--минимальное время пересадки

2--минимизировать стоимость поездки

3--минимизировать общее время в пути

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

Терминология

Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.

Название алгоритма	Название алгоритма	AVERAGE Performance
insertion sort	Сортировка вставками	¼ n²
bubble sort	Сортировка пузырьком	½ n²
mergesort	Сортировка слиянием	n log₂ n

распарсить - произвести синтаксический разбор строки. То есть из строки распознать структуру данных и заполнить её бинарное представление в компьютерной программе.

Теоретическая часть

Есть два множества

1--множество возможных рейсов A->B. Пусть будет D вариантов.

2--множество возможных рейсов B->C. Пусть будет E вариантов.

Фаза 1 Сколько способов выбрать два билета?

Сколько способов выбрать два билета? Сначала выбираем первый билет, потом второй. По правилу произведения получается всего F=D*E возможных комплектов.

Фаза 2 Удалить пересекающиеся билеты

Из множества пар билетов надо удалить те, которые пересекаются, как временные интервалы. Очевидно, что так мы не доберёмся до города C.

Фаза 3 Вычислить метрики

Для каждой пары вычислим время ожидания и для каждой пары вычислить общую стоимость поездки. Для каждой пары вычислить полное время поездки.

Фаза 4 Определить функцию оптимальности

Определить функцию оптимальности. Скорее всего это будет функция от стоимости, времени ожидания и общего времени поездки. Скорее всего будут какие-то коэффициенты определяющие приоритетность того или иного критерия оптимальности.

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

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

Фаза 5 Стабильная сортировка и выбор

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

Практическая часть

Вот нам дали *.csv файл со списком возможных рейсов.

Stage Number, Departure Time,     Departure date,        Arrival time,       Arrival date,      from,    to,     cost,   seller
1,       03:00 ,             14.6 ,                 4:30 ,             14.6,     San-Komarik,   Grabenberg,   1450,blablacar 
1,   18:00 ,  14.6 ,    20:20 ,   14.6 ,    San-Komarik,   Grabenberg,   780,     blablacar
1,   11:10 ,  14.6 ,    13:30 ,   14.6 ,    San-Komarik,   Grabenberg,   780,    blablacar
2,   21:00 ,  14.6,     5:55 ,    15.6 ,    Grabenberg,   Los-Paganos,    3210,    blablacar
2,   21:00 ,  14.6,     5:55 ,    15.6 ,    Grabenberg,   Los-Paganos,   3636,     unitiki
2,   20:30 ,  14.6,     5:20 ,    15.6 ,    Grabenberg ,   Los-Paganos,   3273,     unitiki

Прежде всего надо его распарсить и посчитать сколько всего рейсов.

+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
| Sta |  cost  |     dep     |    Arvl     |      dep       |      Arvl      | Duration |   seller   |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
|   1 |   1450 | San-Komarik |  Grabenberg |  3:00:00,14Jun |  4:30:30,14Jun |     1.51 |  blablacar |
|   1 |    780 | San-Komarik |  Grabenberg | 18:00:00,14Jun | 20:20:20,14Jun |     2.34 |  blablacar |
|   1 |    780 | San-Komarik |  Grabenberg | 11:10:10,14Jun | 13:30:30,14Jun |     2.34 |  blablacar |
|   2 |   3210 |  Grabenberg | Los-Paganos | 21:00:00,14Jun |  5:55:55,15Jun |     8.93 |  blablacar |
|   2 |   3636 |  Grabenberg | Los-Paganos | 21:00:00,14Jun |  5:55:55,15Jun |     8.93 |    unitiki |
|   2 |   3273 |  Grabenberg | Los-Paganos | 20:30:30,14Jun |  5:20:20,15Jun |     8.83 |    unitiki |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+

На втором этапе следует выделить массив рейсов первой поездки и второй поездки

0.413,74 I,[TicketSetOpt] Round:1
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
| Sta |  cost  |     dep     |    Arvl     |      dep       |      Arvl      | Duration |   seller   |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
|   1 |   1450 | San-Komarik |  Grabenberg |  3:00:00,14Jun |  4:30:30,14Jun |     1.51 |  blablacar |
|   1 |    780 | San-Komarik |  Grabenberg | 18:00:00,14Jun | 20:20:20,14Jun |     2.34 |  blablacar |
|   1 |    780 | San-Komarik |  Grabenberg | 11:10:10,14Jun | 13:30:30,14Jun |     2.34 |  blablacar |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
0.456,75 I,[TicketSetOpt] Round:2
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
| Sta |  cost  |     dep     |    Arvl     |      dep       |      Arvl      | Duration |   seller   |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+
|   2 |   3210 |  Grabenberg | Los-Paganos | 21:00:00,14Jun |  5:55:55,15Jun |     8.93 |  blablacar |
|   2 |   3636 |  Grabenberg | Los-Paganos | 21:00:00,14Jun |  5:55:55,15Jun |     8.93 |    unitiki |
|   2 |   3273 |  Grabenberg | Los-Paganos | 20:30:30,14Jun |  5:20:20,15Jun |     8.83 |    unitiki |
+-----+--------+-------------+-------------+----------------+----------------+----------+------------+

Программа строит массив всех возможных пар билетов

+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+
| N  |    depTime     |   depTown   |   depMidTime   | depMidTown  |    ArvlTime    |  ArvlTown   | waitH | costR  |
+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+
|  0 |  3:00:00,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos | 16.49 |   4660 |
|  1 |  3:00:00,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos | 16.49 |   5086 |
|  2 |  3:00:00,14Jun | San-Komarik | 20:30:30,14Jun |  Grabenberg |  5:20:20,15Jun | Los-Paganos | 16.00 |   4723 |
|  3 | 18:00:00,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos |  0.66 |   3990 |
|  4 | 18:00:00,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos |  0.66 |   4416 |
|  5 | 18:00:00,14Jun | San-Komarik | 20:30:30,14Jun |  Grabenberg |  5:20:20,15Jun | Los-Paganos |  0.17 |   4053 |
|  6 | 11:10:10,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos |  7.49 |   3990 |
|  7 | 11:10:10,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos |  7.49 |   4416 |
|  8 | 11:10:10,14Jun | San-Komarik | 20:30:30,14Jun |  Grabenberg |  5:20:20,15Jun | Los-Paganos |  7.00 |   4053 |
+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+

Среди всех рейсов надо удалить те, которые пересекаются по времени. Затем надо отсортировать по цене и отсортировать по времени ожидания пересадки. Важно использовать именно стабильную сортировку.

+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+
| N  |    depTime     |   depTown   |   depMidTime   | depMidTown  |    ArvlTime    |  ArvlTown   | waitH | costR  |
+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+
|  0 | 18:00:00,14Jun | San-Komarik | 20:30:30,14Jun |  Grabenberg |  5:20:20,15Jun | Los-Paganos |  0.17 |   4053 |
|  1 | 18:00:00,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos |  0.66 |   3990 |
|  2 | 18:00:00,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos |  0.66 |   4416 |
|  3 | 11:10:10,14Jun | San-Komarik | 20:30:30,14Jun |  Grabenberg |  5:20:20,15Jun | Los-Paganos |  7.00 |   4053 |
|  4 | 11:10:10,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos |  7.49 |   3990 |
|  5 | 11:10:10,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos |  7.49 |   4416 |
|  6 |  3:00:00,14Jun | San-Komarik | 20:30:30,14Jun |  Grabenberg |  5:20:20,15Jun | Los-Paganos | 16.00 |   4723 |
|  7 |  3:00:00,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos | 16.49 |   4660 |
|  8 |  3:00:00,14Jun | San-Komarik | 21:00:00,14Jun |  Grabenberg |  5:55:55,15Jun | Los-Paganos | 16.49 |   5086 |
+----+----------------+-------------+----------------+-------------+----------------+-------------+-------+--------+

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

0.797,91 W,[TicketSetOpt] Tickets:
0.799,92 I,[TicketSetOpt] phase:1,
0.802,93 I,[TicketSetOpt] Cost :780 RUR,
0.806,94 I,[TicketSetOpt] From :18:00:00,14Jun,San-Komarik
0.809,95 I,[TicketSetOpt] To   :20:20:20,14Jun,Grabenberg
0.813,96 I,[TicketSetOpt] Shop :blablacar
0.816,97 I,[TicketSetOpt] phase:2,
0.819,98 I,[TicketSetOpt] Cost :3273 RUR,
0.822,99 I,[TicketSetOpt] From :20:30:30,14Jun,Grabenberg
0.826,100 I,[TicketSetOpt] To   :5:20:20,15Jun,Los-Paganos
0.830,101 I,[TicketSetOpt] Shop :unitiki
0.833,102 I,[TicketSetOpt] total_cost:4053
0.836,103 I,[TicketSetOpt] waiting between routes:0.16944444 h

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

Итоги

Удалось написать консольную утилиту для выбора оптимального комплекта из двух билетов.

Ссылки

№	Название	URL
1	Algorithms and Data Structures Cheatsheet	https://algs4.cs.princeton.edu/cheatsheet/
2	Дистрибутив утилиты ticket_set_opter	https://github.com/aabzel/Artifacts/tree/main/ticket_set_opter

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Вам приходилось выбирать и покупать билеты с пересадкой?

50% да4

50% нет4

Проголосовали 8 пользователей. Воздержался 1 пользователь.

Хабы:

Задача о Выборе Билетов

Пролог

Постановка задачи

Терминология

Теоретическая часть

Практическая часть

Публикации

Ближайшие события