問題タブ [shortest-path]

これが問題です：

私はn個のポイント（p1、p2、p3、.. pn）を持っており、それぞれが決定されたコストxで他のポイントに接続できます。

各ポイントは、一連のポイントタイプの1つに属します（たとえば、「A」、「B」、「C」、「D」...）。

メソッドの入力は、「ABCADB」のように、私がたどりたいパスです。

出力は、入力で指定したタイプのポイントを接続する最短パスです。たとえば、「p1-p4-p32-p83-p43-p12」（p1はAタイプ、p4はBタイプ、p32はC-）です。タイプ、p83はAタイプ、p43はDタイプ、p12はBタイプです。

「簡単な」ソリューションは、可能なすべてのパスを計算することで構成されますが、計算コストは​​非常に高くなります。

誰かがより良いアルゴリズムを見つけることができますか？

タイトルで言ったように、それが存在するかどうかはわかりません！

アップデート：

ダイクストラや他の同様のアルゴリズムを使用できない重要な点は、タイプに応じてポイントをリンクする必要があることです。

入力として、型の配列があり、その順序でリンクする必要があります。

これは、初期の状況を説明するケントフレデリック（ありがとうございました）の画像です（赤い許可されたリンクで）！

実際の例：

男性は、午前中に教会を訪れ、レストランに行き、最終的に午後に美術館を訪れたいと考えています。

マップには、6つの教会、30のレストラン、4つの美術館があります。

彼は、教会-休憩-博物館の距離が可能な限り最小であることを望んでいます。

私は、フロイド・ウォーシャルの有用性を視覚的に示すためのいくつかのアイデアを求めています。これまでのところ、ランダムグラフを生成して、ユーザーが開始/終了を選択し、最短パスを強調表示できるようにすることしか考えられません。パスファインディングの有用性を示す、もっと楽しくて簡単なデモンストレーションは何ですか？

sとtの頂点を持つグラフがあり、その間の最短経路を見つける必要があります。グラフには、私が利用したい多くの特別なプロパティがあります。

• グラフはDAG（有向非巡回グラフ）です。
• 従来のO（| V + E |）よりも速く、O（| V |）時間でトポロジカルソートを作成できます。
• トポロジカルソート内で、sはリストの最初の項目であり、tは最後の項目です。

トポロジカルソートの頂点を取得すると、ダイクストラの均一コストの現在の標準よりも速く最短経路を見つけることができると言われましたが、そのアルゴリズムを見つけることができないようです。

擬似コードをいただければ幸いです。

編集：sからtまでのすべてのパスは同じ数のエッジを持っています。エッジには重みがあります。最低コストのパスを探しています。

データ構造プロジェクトの場合、一度に1文字だけ変更して、 2つの単語（"cat"となど）の間の最短経路を見つける必要があります。"dog"パスを見つけるために使用するスクラブルの単語リストが提供されます。例えば：

幅優先探索を使用して問題を解決しましたが、より良いものを探しています（辞書をトライで表現しました）。

より効率的な方法（速度とメモリの観点から）についていくつかアイデアを教えてください。ばかげているおよび/または挑戦的な何かが好ましい。

私は友人の一人（彼は後輩です）に尋ねました、そして彼はこの問題に対する効率的な解決策はないと言いました。彼は、私がアルゴリズムのコースを受講したときに、その理由を学ぶと言いました。それについて何かコメントはありますか？

私たちは言葉から言葉へと移動しなければなりません。行くことはできませんcat -> dat -> dag -> dog。トラバーサルも印刷する必要があります。

重み付けされていないグラフで、あるノードから別のノードへの最短経路を返すメソッドを作成しようとしています。ダイクストラ法の使用を検討しましたが、ペアが1つしかないので、これは少しやり過ぎのようです。代わりに幅優先探索を実装しましたが、問題は、返されるリストに不要なノードが含まれていることです。目標を達成するためにコードを変更するにはどうすればよいですか？

追加されたノードの数が最も少ないグラフで最短経路を見つける必要があります。開始ノードと終了ノードは重要ではありません。指定された n ノード間のグラフにパスがない場合、いくつかのノードを追加して最短のツリーを完成させることができますが、新しいノードはできるだけ少なくしたいと考えています。

この問題を解決するには、どのアルゴリズムを使用できますか?

相互接続されたエッジ ( E) のリストがあります。ある頂点から別の頂点に接続する最短パスを見つけるにはどうすればよいですか?

最低共通祖先の使用を考えていますが、エッジには明確に定義されたルートがないため、解決策はうまくいかないと思います。

最短パスは、通過する頂点の最小数によって定義されます。

注: 2 つの頂点を接続するマルチパスが存在する可能性があるため、明らかに幅優先検索は機能しません。

次の問題を解決したい：

実行する必要がある都市とそれらの間のジョブを含む DAG があります。仕事は、定義された制限を積載できるトラック用です。トラックの積載量が多いほど、ツアーはより良いものになります。何かをロードするためのジョブもあれば、定義されたものをロードするためのジョブもあります。都市 a から都市 b までは、たとえ仕事がなくても、いつでも車で行くことができます。最後の制限は、トラックのホームがあるため、常に都市 a で開始して a に戻る必要があることです:)

最初に考えたのは、ダイクストラの最短経路アルゴリズムです。それを最長パスの計算に簡単に変えることができました。私の問題は、これらのアルゴリズムはすべて、頂点 a から b への最短または最長のパスを計算するためのものですが、a から a に戻る必要があることです。

私の心にいくつかのキックがありますか？

ご意見ありがとうございます！

マルコ

"Floyd-Warshall アルゴリズム"と"Dijkstra's Algorithm"の違いは何ですか? また、グラフ内の最短経路を見つけるのに最適なのはどれですか?

次のように、ネット内のすべてのペア間の最短経路を計算し、結果を配列に保存する必要があります。