0

難しい論理の質問があり、それを解決するためのアルゴリズムを作成しようとしていますが、頭を悩ませています。

このデータを検討してください。

A to B
A to C
A to D
A to E
B to C
B to D
B to E
C to D
C to E
D to E

ご覧のとおり、これにより次のようなモデルが効果的に生成されます。A - B - C - D - E

あなたは一方向（左から右）にしか行くことができません、そして私が書きたいのは2点の間のすべての可能な組み合わせを解決することができるアルゴリズムです、すなわち

私がに行きたいと思ったらA、Eすべての可能な組み合わせは次のようになります：

A - E 
A - D - E
A - C - E
A - B - E
A - C - D - E
A - B - D - E
A - B - C - E
A - B - C - D - E

それだけだと思います。

誰かが私がこの問題を解決するのを助けるための論理を手伝ってくれるでしょうか？

4

3 に答える 3

3

まず、単一の「ホップ」をどのように表現するかを考えてください。各ノードには、隣接するノードのリストが必要です。これらのノードを構築することから始めます。

また、ノードのプールからノードを検索する方法も必要になります (その名前で?)。おそらくそれらをマップに入れますか？

ブルート フォース アルゴリズムは、要求されたノードから開始し、すべてのホップを再帰的にたどり、要求された端に到達するまでループを監視し、List を渡します。これをプッシュダウン スタックとして使用して、パスを記録します。要求された末尾に到達するたびに、リストの内容を Path コレクションに保存します。行き止まりになった場合 (要求された端に行くリンクがない場合)、再帰に戻って先に進みます。

速度の必要性に応じて、事前に計算されたパスを保持するようにデータ構造を拡張できます。

それを疑似コードで解決してから、Java で解決してみてください。

于 2012-11-01T14:35:33.410 に答える
2

問題は次のように適切に表現されます。「特定の有向グラフについて、特定のノードから別のノードにたどることができるすべての可能なパスをリストします。 」 2つの任意の頂点間のすべての接続を見つけるためのグラフアルゴリズムを参照してください。

あなたは再帰でそれを解決することができます：

Paths(NodeSequence start, Node finish, ListOfNodeSequences result)Node n3番目の引数としてノードシーケンスの空白のリストを取り、 1ホップを介して到達できるノードシーケンスごとに+をstart追加してifがそうである場合は、それ以外の場合は最初のパラメータとしてを呼び出します。startnresultnfinishPathsstart + n

再帰は必ずしもこの問題を解決するための最もリソース効率の良い方法ではないかもしれませんが、コーディングするのはそれほど多くの作業ではありません。上記の結果は、空の結果変数を初期化することを前提としています。これは、返されるのではなく再帰関数によって変更されるため、少し奇妙ですが、私が提供したバージョンは最小限の労力で済みます。

不完全なソリューション（無関係な実装の詳細を省略）：

public class Node {
    public String name;

    public boolean Equals(Node other) {
        throw new NotImplementedException();
    }
};

public class NodeSequence {
    private ArrayList<Node> nodes;

    public NodeSequence() {
        nodes = new ArrayList<Node>();
    }

    public NodeSequence Plus(Node n) {
        // Returns this NodeSequence with n appended to the end
        throw new NotImplementedException();
    }

    public Node Last() {
        throw new NotImplementedException();
    }
}

public void paths(NodeSequence start, Node finish, ArrayList<NodeSequence> results) {
    Node startNode = NodeSequence.Last();

    ArrayList<Node> nextStops;
    // Populate nextStops with every node that is directly after startNode

    // Recursive block
    for (Node n : nextStops) {
        if (n.Equals(finish)) 
            results.Add(start.Plus(n));
        else 
            Paths(start.Plus(n), finish, results);
    }
}

ArrayList<NodeSequence> findAllPaths(Node start, Node finish) {
    ArrayList<NodeSequence> allPaths = new ArrayList<NodeSequence>();

    // This line will take a while
    paths(start, finish, allPaths);

    return allPaths;
}

findAllPaths結果が出ます。

于 2012-11-01T14:46:19.550 に答える
1

ロジックは次のようになると思います。

  1. 文字のリスト/配列を維持する

      char[] chars = {'A','B', 'C', 'D','E'};
  2. 3 つのインデックス変数を作成します。begin = 0、end = chars.length-1、index = 0;

  3. 範囲出力ごとに 2 つのネストされた for ループを実装し、 

      for begin =0 to end
      collect chars[beign]
      for indx end -begin to end
          collect chars[indx]

これならいけると思います。

1 つのサンプル ロジックは次のようになります。

 char[] chars = {'A','B', 'C', 'D','E'};
 List<Character> charList = new ArrayList<Character>();
 for (int begin=0; begin <chars.length; begin++){
   for (int index=begin; index <chars.length; index++){
     charList.add(chars[begin]);
     for (int indx1=chars.length-index; indx1 <chars.length-begin; indx1++){
        charList.add(chars[indx1+begin]);
     }
     System.out.println(charList);
     charList.clear();
   }
 }

結果を次のように出力する必要があります。

[A]
[A, E]
[A, D, E]
[A, C, D, E]
[A, B, C, D, E]
[B]
[B, E]
[B, D, E]
[B, C, D, E]
[C]
[C, E]
[C, D, E]
[D]
[D, E]
[E]
于 2012-11-01T14:29:26.433 に答える