반환 여행 경로를위한 가능한 조합 수

StackOverflow https://stackoverflow.com/questions/872471

  •  22-08-2019
  •  | 
  •  

문제

내 수학은 나쁘고 정말 나쁘다. 너무 나쁘다. 나는이 질문을 표현하기 위해 고군분투하고 있지만 여기에 간다.

상황은 기차 여행이며 4 개의 배열이 있습니다.

Leave_stations 도착 _stations

Leave_dates returning_dates

따라서 한 방향 노선에만 관심이 있고 경로의 조합이 얼마나 많은지 알아 내야한다고 가정 해 봅시다. 그게 될거야 (나는 생각한다)

possible_routes = (leaving_stations x arriving_stations) x leaving_dates

그러나 돌아 오는 여행을 원한다면 얼마나 많은 조합이 있는지 알아내는 방법은 무엇입니까?

업데이트::

아니면이 일이 작동할까요?

will_routes = ((Leave_Stations x arriving_stations) x Leave_Dates) x (Leave_Dates x returning_dates)

도움이 되었습니까?

해결책

글쎄, 대답은 배열 이름에서 완전히 명확하지 않다는 것입니다.

4 개의 배열이 있다고 가정합니다.

  • 떠나는 날짜
  • 반환 날짜
  • 방송국을 떠나
  • 도착하는 방송국

그러면 우리는 여기서 약간의 설명을 할 수 있습니다. | x | 배열 [x]의 카디널리티 (요소 수)를 나타내려면 | 떠나는 날짜 | 당신이 떠날 수있는 총 날짜 수입니다.

그런 다음 | 떠나는 날짜 | * | 방송국 | * | 도착 스테이션 | 번역하고, 떠날 날짜를 선택한 다음, 방송국에서 떠날 역을 선택한 다음, 역을 선택하여 도착한 다음 가능한 모든 방법으로 그렇게 할 것입니다. 그래서 이것은 당신이 편도 여행을 요구하는 것 같습니다.

이제 실제로, 나는 이것이 실제 문제라고 가정 할 것입니다. 그래서 우리는 6 월 20 일에 사우 샘프 턴에서 요크셔로 떠나기로 선택했다고 가정 해 봅시다.이 시점에서 우리가 선택할 수있는 모든 것이 반환 날짜 (집으로 돌아 가고 싶다고 가정합니다).

따라서 왕복을 계획 할 수있는 총 방법은 먼저 위와 같이 일방 통행을 계획 한 다음 반환 날짜를 선택하는 것입니다. 이는 | 떠나는 날짜 | * | 방송국 | * | 도착 스테이션 | * | 반품 날짜 |. 처음 3 항은 위와 같이 일방 통행 여행을 선택하고 마지막 용어는 가능한 모든 날짜에서 반환 날짜를 선택합니다. 물론, 우리가 떠난 다른 스테이션 이외의 다른 스테이션으로 돌아갈 수있는 옵션이 있다면, 방정식은 (| 떠나는 날짜 | * | 방송국 | * | 도착 스테이션 | (| 반환 날짜 | * | 방송국 |), 또는 우리가 처음 도착한 것과 다른 도착 스테이션에서 떠날 수 있다면 (| | 떠나는 날짜 | * | 스테이션을 떠나는 스테이션 | * | 도착 스테이션 |) * (| 반환 날짜 | * | 도착 스테이션 | * | 방송국 |).

다른 팁

내가 올바르게 이해하는지 확실하지 않지만 이것은 전형적인 것 같습니다. 그래프 라우팅 이론 문제. 당신은 볼 수 있습니다 최소 경로 또는 ㅏ* 알고리즘.

첫째, AA 경로는 잘못된 것입니다.

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

교차로 작동은 두 배열 모두에 속하는 요소입니다

둘째, 2 웨이 경로를 원할 때 조합은 다음과 같습니다.

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)

'Leave_Dates X (날짜+경로 시간을 떠나는 것보다 나중에 return_dates)'는 이상한 일이므로, 가능한 _2way_routes보다 숫자가 더 쉬울 수 있습니다. 가장 높은 수는 모든 Return_dates가 Leave_Dates보다 늦게 나올 때입니다.

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

오, 나는 '날짜+경로 시간을 떠나는 것보다 나중에'return_dates '를 계산하는 방법을 기억했습니다. 그것의:

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

그래도 여전히 '경로 시간'의 문제가 있습니다 ...

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top