3 つのシャトル ルートのコスト (各駅間の距離) を含む有向グラフを作成済みです。どのシャトル路線でも駅から駅までの運賃は同じなので、乗り換えを最小限に抑えるしかありません。
私はそれがこのように機能することを望みます。駅 A -> C から行きたいと思います。簡単のため、最初に駅間の距離を 1 と仮定します。
ルート 1: A -> D -> B -> C -> A ルート 2: A -> C -> E -> F -> A ルート 3: A -> X -> Y -> Z -> A
ルート 1 とルート 2 の両方に A -> C のパスがあるため、コストが最も低いルート 2 を選択します。これは既に実行済みです。
しかし、駅 C -> Y から行きたい場合、C -> Y からの直接ルートはありません。したがって、1 または 2 から行き、A で降りて、A -> Y から行く必要があります。基本的には、シャトルの乗り換えと移動距離を最小限に抑えたい。
これには一般的なアルゴリズムがありますか?
これは、ダイクストラのアルゴリズムで解決できます。
次のようにグラフを設定します。
シャトルルートの各駅にはノードがあります。2 つのシャトルが同じ駅に行く場合、その駅はルートごとに 1 つのノードを取得します。したがって、あなたの例ではノードA1、D1、B1、C1、A2、C2、E2、F2 -> A2などがあります。また、各駅のノードを作成しますが、A、Bなどのルートから独立させます。 Ｃ等
シャトルが 2 つのステーション間を直接移動する場合 (たとえば、この例では A1 と D1 の間であり、A1 と B1 の間ではなく)、これら 2 つのノード間に有向エッジを作成します。そのエッジの重みは、2 つのステーション間のコスト (距離) である必要があります。したがって、たとえば、エッジ (A1, D1) と (D1, C1) があります。
2 つのシャトルが同じステーションに停車する場合、2 つのルート上のステーションのノード間に 2 つの有向エッジを作成します。たとえば、エッジ (A1, A2) と (A2, A1) を作成します。エッジの重みは、転送のコストにする必要があります。
各ルート固有のステーション ノードとステーションから独立したステーション ノードの間に 2 つのエッジを作成します。たとえば、エッジ (A, A1)、(A1, A)、(A, A2)、(A2, A) を作成します。これらのノードのそれぞれに、前のエッジのコストよりもはるかに小さいコストを与えます (たとえば、.01 * 最小コスト)。
2 つのステーション間を移動する場合は、ダイクストラのアルゴリズムを使用して、2 つの非ルート固有ノード間の最小コスト パスを見つけます。
あなたの例では、F から X に移動するには、ノード F と X の間の最小コスト パスを見つけます。返されるパスは、F -> F2 -> A2 -> A3 -> X3 -> X で、F から始まることを意味します。シャトル 2 に乗り、A に移動し、ルート 3 に乗り換え、駅 X で下車します。
特定のシナリオ、制約などに対する非常に多くの最適化。
ダイクストラのを試してみてください。これは通常、最短パス アルゴリズムの基礎 (つまり、多くの人がそのトピックについて学び始める場所) ですが、効率的に実装する方法を本当に理解するには、おそらく関連するデータ構造 (大量の異なる説明などはwikiを参照してください）
そのようなもののための多くのアルゴリズム:
これは、輸送計画で日常的に扱われるものです。
ネットワークを表すグラフを次のように拡張します。
これで、2 つのステーション間の最小パスにコストがかかります。
いずれの場合も、パスは乗車と乗り換え、およびリンクの数に関して最小になります。
ゼロ コストのサブパスが許可されている場合、一部のパス検索アルゴリズムは無期限にループするため、すべてのリンクには (シンボリックであっても) コストが必要であることに注意してください。
これは TSP よりも少し複雑だと思います。距離と使用するシャトルの両方を最小限に抑える必要があります。
それぞれの重さをどうするか。シャトルの乗り換えを最小限に抑えたい場合は、セットを使用してください
各ルートはセットです。セットに別のセットにも属するアイテム (ステーションまたは特定の文字) がある場合、あるセットから別のセットに (またはシャトルから別のセットに) 転送できます。
これは巡回セールスマン問題の構成要素です。実際、「簡単な」解決策はありません。しかし、「十分な」ソリューションを提供するアルゴリズムがいくつかあります。