巴士路线：从每条路线仅 2 个站点获取多条路线

Question

所以我有一张公共汽车可以乘坐的路线列表以及每条路线的距离：

routes = {'AB':5, 'BC':4, 'CD':8, 'DC':8, 'DE':6, 'AD':5, 'CE':2, 'EB':3, 'AE':7}

或者现在只是一个列表，因为距离现在还不重要：

paths = ['AB', 'BC', 'CD', 'DC', 'DE', 'AD', 'CE', 'EB', 'AE']

现在我正在尝试获取公共汽车在给定起点和终点的情况下可以采用的可能路线列表，然后我想尝试合并最大停靠点数以限制数据输出。目前我有这个功能：

def route_variations(first_stop, last_stop, max_stops):
    possiblepaths = []

    for path in paths:
        x = path[0]     #first letter of each route
        if first_stop == x:
            possiblepaths.append(path)

    for path in paths:
        y = path[-1]    #last letter of each route
        if last_stop == y:
            possiblepaths.append(path)
    return possiblepaths

例如，如果我想在 C 开始和结束

route_variations('C','C', 10)

将 return 以 C 开头并以 C 结尾的路线列表，即。 -> ['CD'、'CE'、'BC'、'DC']

所以现在我也需要连接路由。路线 C-E-B-C 需要我的输出中缺少的 E-B 路线。知道如何开始实施吗？然后加入他们，实现像CDC这样的全路由，而不是CD和DC？

Answer 1

正如对您问题的评论所暗示的那样，图论中有众所周知的算法来寻找路径。

但是，只是为了学习（说真的，只是为了学习，这段代码不太适合这个任务的一般情况），我会尝试提供一个简单的例子，有点结构化喜欢你的代码，这样你就可以看到你在获得这些 "connection routes"

时缺少了什么

基本原则是，当您找到一条正确的路径（通过比较第一个字母）时，您会通过从自身内部（即递归）再次调用该函数（即递归）和第二个路径来查找所有以该路径开头的路径路径的字母。:

paths = ['AB', 'BC', 'CD', 'DC', 'DE', 'AD', 'CE', 'EB', 'AE']


def route_variations(first_stop, last_stop, max_stops):
    possible_routes = []
    if max_stops == 0 or first_stop == last_stop:
        return possible_routes
    for path in paths:
        x,y = path
        if first_stop == x:
            if last_stop == y:
                possible_routes.append([path])
            routes_from_this_stop = route_variations(y, last_stop, max_stops - 1)
            possible_routes.extend([[path] + route for route in routes_from_this_stop])
    return possible_routes


print(route_variations('A', 'C', 10))

输出是：

[['AB', 'BC'], ['AD', 'DC'], ['AD', 'DE', 'EB', 'BC'], ['AE', 'EB', 'BC']]

注意：如果路线中有圆圈，您会得到许多绕圆圈的相似路线（长度受max_stops限制）。

注意 2： 当开始和停止相同时，这将不起作用，您将得到一个空结果，因此您的具体示例在这里不起作用:(

Answer 2

我用 itertools 和排列解决了它。如果您想运行它用于大量公共汽车站，这可能不是最快的方法，但对于 8 个站点的组合，它的工作速度相当快。

作为输出，您会得到一个包含简化版路线和总距离的字典：

import itertools

paths = ['AB', 'BC', 'CD', 'DC', 'DE', 'AD', 'CE', 'EB', 'AE']
routes = {'AB':5, 'BC':4, 'CD':8, 'DC':8, 'DE':6, 'AD':5, 'CE':2, 'EB':3, 'AE':7}

def route_variations(first_stop, last_stop, max_length):
    valid_routes = []
    for n in list(range(2, max_length+1)):
        combinations = itertools.product(paths, repeat=n)
        for combination in combinations:
            print (combination)
            for i in list(range(n)):
                if i == 0:
                    if combination[i][0] != first_stop:
                        break
                elif i != 0 and i != n-1:
                    if combination[i][0] != combination[i-1][1]:
                        break
                elif i == n-1:
                    if combination[i][0] == combination[i-1][1] and combination[i][1] == last_stop:
                        valid_routes.append(combination)
                    else:
                        break
    result = {}
    for route in valid_routes:
        route_simple = ""
        dist = 0
        for j in route:
            dist += routes.get(j)
            if route.index(j) == 0:
                route_simple += str(j)
            else:
                route_simple += str(j[1])
        result[route_simple] = dist

    return result


print(route_variations('A', 'C', 6))

巴士路线：从每条路线仅 2 个站点获取多条路线

Bus Routes: obtaining multiple routes from only 2 stops per route

python

algorithm

optimization

graph-algorithm