0

У меня есть задание и файл на вход, которые я прикреплю ниже. Я не совсем понимаю с чего начать... Скажите, пожалуйста, что лучше использовать/ какой подход выбрать для программной реализации. Прошу, пожалуйста, указать как было бы лучше реализовать поиск “лучших” вариантов по цене и времени.

Дано расписание поездов между несколькими станциями в формате “номер поезда;станция отправления;станция прибытия;стоимость;время отправления;время прибытия” (гарантированно, что нет переездов дольше суток) . Необходимо получить “лучшие” варианты (несколько, если это возможно) проезда между всеми станциями так чтобы побывать на каждой станции 1 раз. Запросы на лучшие варианты:

*Лучшие по цене

*Лучшие по времени

Задача состоит в том чтобы найти лучшие маршруты для проезда с пересадками между всеми станциями. Например, есть 6 станций: 1,2,3,4,5,6. Нужно найти маршруты которые будут проходить через каждую станцию по одному разу и посчитать какие из них являются лучшими.

Ниже будет указана небольшая часть списка расписания поездов в формате “номер поезда;станция отправления;станция прибытия;стоимость;время отправления;время прибытия”

907;1909; 1929;1790.87;00:50:00;20:00:00
908;1909;1929;1790.87;00:50:00;20:00:00
909;1929;1909;1790.87;10:01:00;01:00:00
909;1929;1921;199.15;11:10:00;01:00:00
910;1929;1909;1790.87;10:01:00;01:00:00
910;1929;1921;199.15;11:10:00;01:00:00
911;1902;1937;191.87;23:00:00;14:40:00
914;1937;1902;191.89;09:24:00;00:52:00
917;1902;1929;300.18;09:25:00;20:01:00
918;1929;1902;300.20;06:55:00;17:10:00
919;1902;1981;130.60;04:59:00;20:06:00
920;1981;1902;120.55;10:00:00;01:05:00
921;1981;1902;120.55;10:00:00;01:05:00
935;1981;1902;191.48;20:03:00;10:56:00
936;1981;1902;191.48;20:03:00;10:56:00
957;1937;1902;131.36;00:55:00;15:02:00
965;1902;1929;180.27;09:33:00;17:57:00
966;1902;1929;180.27;09:33:00;17:57:00
967;1929;1902;180.28;09:10:00;16:35:00
968;1929;1902;180.28;09:10:00;16:35:00
970;1929;1921;309.19;00:24:00;15:35:00
971;1929;1921;309.19;00:24:00;15:35:00
978;1902;1929;258.53;04:15:00;13:10:00
979;1929;1902;258.55;07:16:00;14:50:00
986;1981;1902;157.45;08:46:00;00:50:00
987;1902;1981;156.90;02:52:00;18:49:00
995;1902;1981;148.73;05:27:00;20:18:00
996;1981;1902;149.23;09:12:00;23:27:00
1002;1929;1921;199.15;05:52:00;20:25:00
1006;1921;1929;142.13;12:07:00;02:06:00
1013;1921;1937;140.51;07:59:00;18:03:00
1025;1921;1902;164.65;07:08:00;22:20:00
1026;1902;1921;164.63;06:46:00;22:23:00
1035;1929;1921;181.05;22:07:00;12:15:00
1050;1981;1902;227.88;18:04:00;08:44:00
1066;1902;1981;152.58;03:47:00;18:37:00
1067;1981;1902;153.10;07:41:00;22:00:00
1068;1921;1929;130.36;06:45:00;21:22:00
7
  • Классическая задача коммивояжера. Почитайте про метод Литтла, один из самых известных для поиска самого самого дешёвого цикла в графе (Ориентированный). В итоге у вас будет 2 матрицы, где вершины будут означать время между станциями и ценой. Останется только найти пути. 16 июн 2022 в 7:24
  • Mister_Jesus, прошу, пожалуйста, объяснить несколько пунктов из вашего комментария, почему будет 2 матрицы? Что имеется ввиду под вершинами и как найти пути в конце действия?
    – nxcht
    16 июн 2022 в 17:25
  • Вам достаточно прочитать про метод Литтла для нахождения пути. Матрицы используются представления графов. А в методе литла как раз используются матрицы. 2 матрицы будут решать разные задачи - одна для поиска лучшего по времени пути, другая для поиска лучшей цены. 16 июн 2022 в 18:43
  • 1
    Вот хорошая статья на хабре habr.com/ru/post/332208 16 июн 2022 в 18:59
  • Mister_Jesus, прежде всего, хочу вас поблагодарить, спасибо вам огромное. Но у меня появился ещё один и надеюсь последний вопрос по этой теме. Скажите, пожалуйста, как можно идентифицировать в данном случае строки и столбцы матриц? Я имею ввиду то что на пересечении идентификаторов должна быть цена/ время (например, 1(является идентификатором строки) срока 2(является идентификатором столбца) столбец цена/ время), но что тогда может выступать этими идентификаторами(если присутствуют разные поезда с одним и тем же маршрутом и иногда разными ценой и временем)?(из выше упомянутых полей информации)
    – nxcht
    17 июн 2022 в 12:42

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Посмотрите другие вопросы с метками или задайте свой вопрос.