10

これが問題です：

私は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つの美術館があります。

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

4

8 に答える 8

7

Floyd–Warshall アルゴリズムを使用できます。ウィキペディアが提供する疑似コードは次のとおりです。

/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to 
   (infinity if there is none).
   Also assume that n is the number of vertices and edgeCost(i,i)=0
*/

int path[][];

/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
   from i to j using intermediate vertices (1..k-1).  Each path[i][j] is initialized to
   edgeCost(i,j) or infinity if there is no edge between i and j.
*/

procedure FloydWarshall ()
    for k: = 1 to n
        for each (i,j) in {1,..,n}2
            path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

この同じ問題について、アルゴリズム コースのプログラムを作成する必要がありました。このアルゴリズムは魅力的に機能しました! 幸運を。

于 2009-07-17T12:51:34.987 に答える
4

考えられるすべてのパスを計算するよりもうまくいくアルゴリズムはたくさんあります。 幅優先探索は、私が念頭に置いているアルゴリズムファミリーの基本的な出発点です。頂点コストが定義されているため、最良優先探索が適切です。問題空間に関する詳細情報を取得できる場合は、次を使用できる可能性があります。A*またはダイクストラのアルゴリズム。（いずれの場合も、許可された開始ノードのセットからパスを検索します。）

編集をやり直してください。パスの制約（満たす必要のあるノードタイプの配列）によって、これらのアルゴリズムの使用が妨げられることはありません。まったく逆に、それはそれらすべてがより良く機能するのを助けます。パス制約を組み込むことができるようにそれらを実装する必要があります。検索の各ステップで使用可能な頂点を、制約が与えられた場合に有効な頂点に制限します。

于 2009-07-17T12:40:24.063 に答える
4

Jan が述べたように、必要なのは通常の退屈な最短経路アルゴリズム (ダイクストラやフロイドのアルゴリズムなど) だけです。ただし、出力パスがパス制約を尊重するように、入力グラフを変換する必要があります。

A - B - A のパス制約があるとします。

新しいグラフGを作成し、すべての頂点をa_01 などの新しいラベルでAに挿入します。G次に、からすべての頂点を挿入し、頂点を頂点Bに接続Gします (エッジは新しく挿入されたノードに向ける必要があります)。元のグラフからコストをコピーします。次に、新しく挿入された頂点を の頂点に接続して (およびその他のパス コンポーネント)、この手順を繰り返します。したがって、存在するパスのみがパス制約を満たすグラフを作成します。その後、通常の最短パス アルゴリズムを使用できます。ABAB

重要な洞察は、クラスを再訪するとき、実際には別個のノードのセットを訪問しており、隣接するノードのクラスを接続するエッジのみが必要であるということです。

于 2009-07-17T12:58:32.807 に答える
4

代替テキスト

これが私が現在あなたの問題を解釈する方法です。

赤い矢印は、指定された順序制約に準拠するパスを手動でトレースしています。

コストは示されていませんが、すべてのリンクにコストがかかると想定されており、リンクのコストは異なります。

これがあなたが解決しようとしているシナリオを正確に説明している場合は、他の人が質問により適切に答えることができるように、そのように言ってください。

于 2009-07-17T13:15:18.640 に答える
2

動的計画法ソリューションを使用した擬似コードは次のとおりです。

n - length of desired path
m - number of vertices
types[n] // desired type of ith node
vertice_types[m]
d[n][m] // our DP tab initially filled with infinities

d[0][0..m] = 0
for length from 1 to n 
  for b from 0 to m
    if types[length] == vertice_types[b]
      for a from 0 to m
        if types[length-1] == vertice_types[a]
          d[length][b] = min(d[length][b], d[length-1][a] + cost(a,b))

最小コストパスはmin（d [n] [0..m]）です

dテーブルのサイズを2行に減らすことはできますが、ソリューションがわかりにくくなります。

于 2009-07-17T14:01:19.410 に答える
2

あなたの質問の改訂では、文字ごとに1つのノードを要求しているようです-その場合、それは単純な動的プログラミングソリューションです.ノードの各ペア間で、シーケンスの開始を満たす長さ1の最短パスをすべて計算します. 次に、すべてのノード ペアに対してすべてのそのようなパスを k に対して持つと、k+1 に対して構築するのは簡単です。

于 2009-07-17T12:54:07.250 に答える
1

私があなたの質問を理解している限り、有向グラフの最短経路が必要です。http://en.wikipedia.org/wiki/Dijkstra%27s_algorithmはあなたにアイデアを与えるはずです。

よろしく、1月

于 2009-07-17T12:40:25.610 に答える
1
  1. 各等価ブロック内の最短経路のすべてのペアを計算します。
  2. ここで、クラス間のエッジを持たないが、クラス間のエッジがそのクラス内の最短経路と一致し、別のクラスの特定のノードにつながるグラフを作成します。

これが明確であることを願っています。

このソリューションは特に効率的ではありませんが、明らかに多項式です。

于 2009-07-17T12:44:59.213 に答える