私は最近、この (編集: 問題 A)興味深い問題に出くわしました。これは、今年初めに Spotify のハッカー チャレンジで発生したもので、列車を出発点に戻すための列車トラックのジャンクションでの切り替えを決定することを含みます。列車は出発したときと同じ方向を向いて到着しなければならず、線路上で逆走することはできません。
私が理解しているように、問題は、特定の頂点から最短のサイクルを見つけるか、そのようなサイクルが存在しないことを検出する必要がある無向 (?) グラフとしてモデル化できます。ただし、興味深い点は、頂点 v の場合、v に隣接する頂点は v までのパスに依存するため、ある意味ではグラフは有向と見なすことができますが、この方向はパスに依存します。
私が最初に考えたのは、各ノードを A、B、C の 3 つの個別の頂点 (A <-> B および A <-> C) としてモデル化し、幅優先検索を使用して元のノードが見つかるまで検索ツリーを構築することでした。頂点ですが、これは上記の警告によって複雑になります。つまり、特定の頂点の隣接関係は、以前に訪れた頂点に依存するということです。これは、BFS ツリーでは、ノードが複数の親を持つことができることを意味します。
この問題を解決するには、明らかに単純な BFS 検索では不十分です。グラフ内のサイクルを検出するアルゴリズムが存在することは知っています。1 つのアプローチとして、すべてのサイクルを検出し、各サイクルについて、パスが有効かどうかを検出することが考えられます。(つまり、方向を反転しません)
この問題を解決するためのアプローチについて、他の誰かが洞察を持っていますか?
更新： コメントで@Karussellが提案したアプローチに従いました。
秘訣は、従来の頂点ベースのグラフではなく、エッジベースのグラフを使用して状況をモデル化することでした。コンテストで提供される入力ファイルは、既にエッジに関して便利に指定されているため、このファイルを使用してエッジベースのグラフを簡単に作成できます。
このプログラムは、Road と Solver という 2 つの重要なクラスを使用します。Road には、j1 と j2 の 2 つの整数フィールドがあります。j1 はソース ジャンクションを表し、j2 はターゲット ジャンクションを表します。各道路は一方通行です。つまり、j1 から j2 にしか移動できません。各 Road には、隣接する Road の LinkedList と親 Road も含まれます。Road クラスには、入力ファイルで使用される文字列と、各ジャンクションの A、B、および C ポイントを表す整数インデックスとの間で変換するための静的メソッドも含まれています。
入力ファイルのエントリごとに、HashMap に 2 つの Road を追加します。2 つのジャンクション間の各方向に 1 つの Road です。これで、ジャンクション間を走るすべての道路のリストができました。A、B、C スイッチを介してジャンクションで道路を接続するだけです。道路が Junction.A で終わる場合、Junction.B と Junction.C で始まる道路を検索し、これらの道路を隣接として追加します。buildGraph() 関数は、ターゲット ジャンクション (j2) が "1A" == インデックス 0 である道路を返します。
この時点で、グラフが作成されます。最短経路を見つけるために、単純に BFS を使用してグラフをトラバースしました。ルートにはマークを付けずに、ルートの隣接関係をキューに入れることから始めます。ターゲット ジャンクションが「1A」(インデックス 0) である道路が見つかった場合、開始点を通る最短のサイクルが見つかりました。各 Road の親プロパティを使用してパスを再構築したら、問題の必要に応じてスイッチを適切に設定するのは簡単なことです。
このアプローチを提案してくれた Karussell に感謝します。短い説明付きの回答フォームにコメントを入れたい場合は、それを受け入れます. @Originにも感謝します。私はあなたの答えの論理に完全に従わなかったことを認めなければなりませんが、それが正しくないと言っているわけではありません. 誰かがあなたのソリューションを使用してこの問題を解決した場合、私はそれを見ることに非常に興味があります.