Постановка проблемы Учитывая источник, пункт назначения, а также время и маршруты прибытия и отправления автобуса, я хочу найти путь с наименьшей стоимостью от источника до пункта назначения. Это может включать в себя поездку на автобусе и такси до места назначения. Автобусы имеют фиксированное время, но такси можно взять в любое время между любыми двумя местами
Пример Например, мой источник - А, мой пункт назначения - Г. Б, C - это соответствующие автобусные станции. 1. Мое время старта 11:00. Автобус отправляется из А в В в 11:15 и прибывает в В в 11:30 (стоимость = 30).
Автобус от А до C отправляется в 11:15 и достигает C в 12:30 (стоимость = 50).
Такси от B до C прибывает в C в 12:00 (стоимость = 100).
Автобус от C до G отправляется в 12:10 и прибывает в 1:00 в G (стоимость = 30).
Такси от C до G стоит 400, а Такси от A до G стоит 600.
Самое дешевое решение - взять автобус от A до B, такси от B до C и автобус от C до G
Мой подход (грубая сила здесь не вариант)
Жадный подход не сработал, потому что оптимальные локальные решения не дают глобального оптимального решения.
Эта проблема немного напоминает проблему планирования взвешенных интервалов (см. здесь ), которую можно решить с помощью Dynami c Программирование, так как время в автобусе и такси можно рассматривать как интервалы. Однако планирование взвешенных интервалов включает в себя максимизацию затрат, и если я попытаюсь минимизировать их, алгоритм будет преждевременно остановлен. Если я попытаюсь использовать отрицательные затраты и попытаться максимизировать, то снова алгоритм преждевременно останавливается после добавления всего 1 интервала.
Следовательно, мы будем благодарны за любые советы по решению этой проблемы.