您如何从代表火车路线的列表集合中找到最短路径？

debugcn 发表于 Dev

勤奋的人

因此，我有四个“火车线”以列表的形式表示：

line1 = ["a", "b", "f", "d", "e"]
line2 = ["c", "e", "j", "g", "i"]
line3 = ["c", "j", "k", "l", "m"]
line4 = ["h", "b", "e", "a", "n"]

本质上，每个字母都充当一个“站”。如果一个站出现在多条线路上，则可以从一条线路切换到另一条线路，这与许多地下城市公交系统类似。例如，从“ a”到“ h”的最短路径将是[“ a”，“ b”，“ h”]，因为您可以在第1行中从“ a”到“ b”，然后转移到第4行，然后从“ b”移到“ h”。

我希望找到一种简单的方法来找到给定起点和终点的最短路径。我当前的解决方案是通过找到一个站点的相邻站点并将它们与该站点配对来将线转换为图形。

stations = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n"]
allLines = [line1, line2, line3, line4]
nodeGraph = {}
def getList(letter):
  neighbors = []
  for i in allLines:
     if letter in i:
        pos = i.index(letter)
        if pos == 0:
            neighbors.append(i[pos+1])
        elif pos == len(i) - 1:
            neighbors.append(i[pos-1])
        elif pos > 0 and pos < len(i) - 1:
            neighbors.append(i[pos-1])
            neighbors.append(i[pos+1])
  return neighbors

for station in stations:
   nodeGraph[station] = getList(station)

然后，我在此网站上找到了最短路径功能，该功能从图形输入中输出最短路径。

def SP(graph, start, end, path=[]):
  path = path + [start]
  if start == end:
      return path
  shortest = None
  for node in graph[start]:
      if node not in path:
          newpath = SP(graph, node, end, path)
          if newpath:
              if not shortest or len(newpath) < len(shortest):
                  shortest = newpath
  return shortest

我要避免完全创建图形的步骤，而仅从四个列表中得出最短路径。有人可以帮我吗？

Yang Yushi

我实现了一种启发式且残酷的算法来解决纯Python函数的问题。

from itertools import combinations, permutations

stations = [
    "a", "b", "c", "d", "e",
    "f", "g", "h", "i", "j",
    "k", "l", "m", "n"
]

line1 = ["a", "b", "f", "d", "e"]
line2 = ["c", "e", "j", "g", "i"]
line3 = ["c", "j", "k", "l", "m"]
line4 = ["h", "b", "e", "a", "n"]
lines = [line1, line2, line3, line4]


def validate_step(x, y, lines):
    """
    check if we can change fron x to y in a single line
    """
    for i, line in enumerate(lines):
        if (x in line) and (y in line):
            if abs(line.index(x) - line.index(y)) == 1:
                return True, (i, (line.index(x), line.index(y)))
    else:
        return False, None


def find_shortest(x, y, lines, max_step=12):
    # check if x and y are in the same line
    valid = validate_step(x, y, lines)
    if valid[0]:
        return 0, [valid[1]]
    # iterating over all the possibilities
    possible_inter = [s for s in stations if s not in (x, y)]
    for im_step in range(1, max_step):  # intermediate step
        inter_steps = combinations(possible_inter, im_step)
        for i_step in inter_steps:
            for steps in permutations(i_step):
                solution = []
                is_path_valid = True
                full_path = [x] + list(steps) + [y]
                
                for p1, p2 in zip(full_path[:-1], full_path[1:]):
                    valid = validate_step(p1, p2, lines)
                    is_path_valid *= valid[0]
                    solution.append(valid[1])

                if is_path_valid:
                    return im_step, solution
    print("Did not find a solution")
    return None, None


x = "d"
y = "n"

result = find_shortest(x, y, lines)

print(f"with {result[0]} changes, the path from '{x}' to '{y}' is find")
for step in result[1]:
    s1 = lines[step[0]][step[1][0]]
    s2 = lines[step[0]][step[1][1]]
    print(f"- Taking line {step[0]+1}, go from '{s1}' to '{s2}'")

一旦问题的复杂性增加，图算法肯定会受到青睐。

PS我的结果与@Alain T的结果相同。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。