Возможное количество комбинаций для обратных маршрутов

Question

У меня плохая математика, очень плохая.Так плохо, что я изо всех сил пытаюсь сформулировать этот вопрос, но вот.

Ситуация — поездка на поезде, и у вас есть четыре массива для работы.

Оставление_stations atfure_stations

Оставить_dates returning_dates

Допустим, вас интересуют только односторонние маршруты, и вам нужно выяснить, сколько существует комбинаций маршрутов.Это было бы (я думаю)

possible_routes = (leaving_stations x arriving_stations) x leaving_dates

Но как мне узнать, сколько комбинаций существует, если я хочу вернуться обратно?

ОБНОВЛЯТЬ::

или это сработает?

возможные_маршруты = ((станции_выезда x станции_прибытия) x даты_выезда) x (даты_выезда x даты_возвращения)

Answer 1

Что ж, ответ в том, что это не совсем ясно из названий ваших массивов.

Предположим, у нас есть 4 массива:

• Даты выезда
• Даты возвращения
• Покидая станции
• Станции прибытия

Тогда мы можем немного объяснить здесь.Давайте использовать нотацию | x | представлять кардинальность (количество элементов) массива [x], так что даты ухода | это общее количество дат, на которые вы можете уйти.

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

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

Таким образом, общее количество способов, которыми мы можем спланировать поездку туда и сначала спланировать одностороннее путешествие, как указано выше, а затем выбрать дату возвращения, которая будет | Уходящими датами | * | Уходящие станции | * | Прибывшие станции | * | Дата возвращения |.Первые три условия выбирают поездку в один конец, как указано выше, а последний термин выбирает дату возвращения из всех возможных дат.Конечно, если бы у нас была возможность вернуться на другую станцию, отличную от той, с которой мы уехали, тогда уравнение было бы таким (|Даты отправления| * |Станции отправления| * |Станции прибытия|) * (|Дата возвращения| * |Станции отправления|), или если бы мы могли даже выйти с другой станции прибытия, отличной от той, на которую мы прибыли впервые, это стало бы (|Даты отправления| * |Станции отправления| * |Станции прибытия|) * (|Дата возвращения| * |Станции прибытия| * |Станции отправления|).

Answer 2

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

Answer 3

во-первых, маршруты А-А — это неправильные вещи, поэтому:

possible_routes = 
(
  leaving_stations x arriving_stations - 
  (leaving_stations [intersection] arrivig_stations) 
) x leaving_dates

операция пересечения — это элементы, принадлежащие обоим массивам

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

possible_2way_routes = 
(
    leaving_stations x arriving_stations - 
    (leaving_stations [intersection] arrivig_stations) 
) x 
leaving_dates x 
(return_dates that later than leaving dates+route time)

«Даты_отъезда x (даты_возврата, которые позже дат отъезда+время маршрута)» - странная вещь, поэтому может быть проще вычислить высокую оценку - число, которое в любом случае не меньше, чем возможные_2путевые_маршруты.наибольшее количество будет, когда все return_dates позже, чем Leave_dates, поэтому:

possible_2way_routes <= 
(
    leaving_stations x arriving_stations - 
    (leaving_stations [intersection] arrivig_stations) 
) x leaving_dates x return_dates

о, я вспомнил, как рассчитать «даты возврата, которые позже дат отъезда + время маршрута».его:

for each element of leaving_dates {
sum=sum+return_dates that later than ith leaving date+route time}

однако все еще существует проблема «времени маршрута»...