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

Question

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

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

Leaving_Stations Arriving_Stations

Leaving_Dates Returning_Dates

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

possible_routes = (leaving_stations x arriving_stations) x leaving_dates

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

UPDATE ::

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

возможных_русах = ((leaving_stations x прибывающих_статий) x выезжающих дат) x (выезжающих дат x возвращаемых_ дат)

Answer 1

Ну, ответ не совсем понятен из имен ваших массивов.

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

• Даты выхода
• Даты возврата
• Станции покидания
• Станции прибытия

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

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

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

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

Answer 2

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

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)

'leaving_dates x (return_dates, которые позже, чем даты отъезда + время маршрута)' - странная вещь, поэтому может быть проще накапливать высокие оценки - число, которое в любом случае должно быть не меньше возможных_2way_routes. самый высокий счет будет, когда все returning_dates позже, чем leaving_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}

все еще существует проблема "времени маршрута", хотя ...

Answer 3

Я не уверен, правильно ли я понимаю, но это похоже на типичную проблему теории graph-routing . Вы можете посмотреть алгоритмы Minimum Path или A *.