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

您只能朝一个方向（从左到右）前进，而我要编写的是一种算法，可以计算出两点之间的所有可能组合，即

如果我想从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

首先，考虑如何表示单个“跃点”：每个节点都需要一个其相邻节点的列表。首先构建这些节点。

您还需要一种从节点池中查找节点的方法（按其名称？）。也许将它们放在地图中？

蛮力算法将从请求的节点开始并递归地跟踪所有跃点，观察循环，直到到达请求的末端，传递一个列表——将其用作下推堆栈，以记录路径。每次到达请求端时，将列表的内容保存到 Path 集合中。如果你遇到了死胡同（没有链接到请求的一端），请备份你的递归并继续前进。

根据您对速度的需求，您可以扩展您的数据结构以保存一些预先计算的路径。

尝试用伪代码和 Java 来解决这个问题。

于 2012-11-01T14:35:33.410 回答
2

您的问题最好表述为：“对于给定的有向图，列出可以从某个节点到另一个节点的所有可能路径。 ”请参阅Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

你可以用递归解决它：

Paths(NodeSequence start, Node finish, ListOfNodeSequences result)将节点序列的空白列表作为第三个参数，并且对于Node n可以通过从start添加start+n到resultif nis 的一跳到达的每个节点序列finish，否则调用Pathswithstart + 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]

我认为这会做到这一点。

一个示例逻辑如下：

 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 回答