所有可能的路径算法

Question

我对数学算法不太满意，我需要在我正在做的项目中使用一个算法。我已经找到了A点到B点的答案，但没有一个答案与我所寻找的完全一致。我正在寻找最有效的算法来完成这个任务：

作为投入：

Points {
    In
    Out
}

[Bridge]Points = {
    "AB-1" = {"A", "B"}
    "AB-2" = {"A", "B"}
    "BA-1" = {"B", "A"}
    "BA-2" = {"B", "A"}
    "AC-1" = {"A", "C"}
    "AC-2" = {"A", "C"}
    "CA-1" = {"C", "A"}
    "CA-2" = {"C", "A"}
    "BC-1" = {"B", "C"}
    "BC-2" = {"B", "C"}
    "CB-1" = {"C", "B"}
    "CB-2" = {"C", "B"}
}

每个“桥”代表两个“点”：第一个值是" in“，第二个值是"out”。

每个路径只能使用每一个唯一的桥一次。不同的桥可以有相同的输入/输出(如"BC-1“、"BC-2”、.)，每个唯一的桥必须有不同的输入和输出("AA-1“= {"A"，"A"}是不可能的)。

目标是获得给定起点和终点的所有可能的路径，这些路径可以是相同的点(A->A，B->B，.)。

对于A到A预期产出：

AB-1 -> BA-1
AB-1 -> BA-2
AB-2 -> BA-1
AC-1 -> CA-2
AB-1 -> BA-1 -> AB-2 -> BA-2
AB-1 -> BA-2 -> AC-1 -> CB-2 -> BA-1
AC-2 -> CA-1 -> AB-1 -> BA-2
AC-1 -> CA-1 -> AB-2 -> BC-1 -> CA-2
...

此外，定义最大路径长度(以避免算法中的后续处理)的可能性是可选的，但非常有趣。感谢您的时间，我将非常感谢您的意见。

Answer 1

可以使用这样的递归(伪代码)：

findPath(from, to, path_to_from) {
  if from == to { output path_to_from }
  for all bridges going out from 'from' that were not already used in path_to_from {
    findPath(bridge.out, to, path_to_from + bridge)
  }
}

然后用findPath(A, B, empty_path)调用它输出从A到B的所有路径。