復路のルートの組み合わせ可能数

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

  •  22-08-2019
  •  | 
  •  

質問

私の数学はダメ、本当にダメです。とても残念で、この質問を言葉で表現することすら困難ですが、これで終わります。

状況は電車での移動で、操作する配列が 4 つあります。

reaver_stations relainiving_stations

leaves_dates returning_dates

たとえば、片道ルートのみに興味があり、ルートの組み合わせが何通りあるかを把握する必要があるとします。そうなるだろう（と思う）

possible_routes = (leaving_stations x arriving_stations) x leaving_dates

しかし、往復の旅行が必要な場合は、どのように組み合わせがあるかを調べればよいでしょうか?

アップデート：：

それともこれはうまくいきますか？

possible_routes = ((出発駅 x 到着駅) x 出発日) x (出発日 x 戻り日)

役に立ちましたか？

解決

答えは、配列名からは完全には明らかではないということです。

4 つの配列があると仮定します。

  • 出発日
  • 返却日
  • 駅を出る
  • 到着駅

それでは、ここで少し説明させていただきます。表記| x |を使用しましょうアレイ[x]のカーディナリティ（要素の数）を表すために、そのため|残す日付|あなたが残すことができる日付の総数です。

次に|日付を残す| * |ステーションを離れる| * |到着ステーション|翻訳して、出発する日付を選び、駅を選んで出発してから、駅を選んで到着し、あらゆる方法でそれを行います。したがって、これは片道旅行の場合に求めているものと思われます。

さて、実際に、これが現実世界の問題であると仮定します。つまり、6 月 20 日にサウサンプトンからヨークシャーへ出発することを選択したとします。復路では、この時点で選択できるのは、帰国日（つまり、あなたは家に帰りたいと想定しています）。

したがって、往復を計画できる方法の総数は、上記の一方向の旅行を最初に計画してから、返品日を選択します。 * |ステーションを離れる| * |到着ステーション| * |返品日|。最初の 3 学期は上記のように片道旅行を選択し、最後の学期はすべての可能な日付から帰国日を選択します。もちろん、出発した駅以外の別の駅に戻るオプションがある場合、方程式は (|出発日| * |出発駅| * |到着駅|) * (|帰国日| * |出発駅|)、または最初に到着した駅とは別の到着駅から出発することもできる場合は、(|出発日| * |出発駅| * |到着駅|) * (|帰国日|) になります。 * |到着駅| * |出発駅|)。

他のヒント

私は私が正しく理解すればわからないんだけど、これは典型的なグラフルーティングのように思えますの理論の問題。 //en.wikipedia：あなたは、最小経路のか<のhref = "HTTP noreferrer"> A * のアルゴリズム。

まず、A-Aルートは間違ったことはそう、あります：

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)
いずれの場合possible_2way_routes以上のことを、数 - 高い評価をcumputeする方が簡単かもしれので、

「leaving_dates×（後の日付+ルートの時間を残すよりも、return_dates）」は、奇妙なことです。最高のカウントはそう、ときにすべてのreturning_dates後でleaving_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