0

我在 python 中需要一些帮助。

我正在使用Aimsun交通模拟器做一些模拟，编程语言是python。

我的问题是：

我需要搜索车辆可以走的所有可能路线。

我得到这些不完整的路线：

 1. Route 1 - [967, 973]  
 2. Route 2 - [967, 970] 
 3. Route 3 - [970, 396]    
 4. Route 4 - [396, 3269] 
 5. Route 5 - [3269, 3275] 
 6. Route 6 - [3275, 3278]
 7. Route 7 - [3278, 404] 
 8. Route 8 - [3278, 408] 
 9. Route 9 - [404, 448]
 10. Route 10 - [408, 410] 
 11. Route 11 - [408, 411] 
 12. Route 12 - [448, 454] 
 13. Route 13 - [410, 419] 
 14. Route 14 - [410, 433] 
 15. Route 15 - [410, 437] 
 16. Route 17 - [411, 412]

起点是 967，所以任何车辆都会从这个点开始。

此列表表示部分的连接，因此如果第二列中的值在第一列中的下一个值中不重复，则该值将表示终点，因此车辆将完成行程。

因此，对于完成第一条路线，我们有：

Route Finish 1 - [967, 973]因为 973 不要在第一列中重复。

在这种情况下很简单，我用这条路线存储一个变量。

现在开始问题：

第二条路线由路线2,3,4,5,6组成，所以，

Route 2 - [967, 970, 396, 3269, 3275, 3278]

但问题是 3278 在第一列中重复了两次：

1. Route 7 - [3278, 404]
2. Route 8 - [3278, 408]

所以我还有两条路线：

1. Route x - [967, 970, 396, 3269, 3275, 3278, 404]
2. Route y - [967, 970, 396, 3269, 3275, 3278, 408]

并且问题增加

1. Route a - [967, 970, 396, 3269, 3275, 3278, 404, 448]
2. Route b - [967, 970, 396, 3269, 3275, 3278, 408, 410]
3. Route c - [967, 970, 396, 3269, 3275, 3278, 408, 411]
4. Route d - [967, 970, 396, 3269, 3275, 3278, 408, 454]

并以同样的方式继续。

如何动态合并此列表，最后我将所有路由都放在变量中，例如：

1. Route Finish 1 - [....] 
2. Route Finish 2 - [....]

我尝试了很多代码，比较并存储在变量中，但不起作用。

我希望你们已经明白了。

4

2 回答 2

1

我很抱歉没有使用 python 3，因为我没有安装它。请将print语句转换为函数，它应该可以工作。

概述

根据您的问题陈述，我将您的路线绘制如下：

在此处输入图像描述

通过查看此图表，我得出了一些观察结果：

  • 如果我从 开始967，我将在以下节点（或车站，或汽车站）结束：973、454、419、433、437和412。我称这些节点leaf_nodes或end_points在代码中。
  • 您在问题陈述中所说的“路线”只是完整路线的一部分。
  • 因此，“路由”的数量实际上是end_points
  • 对于这个解决方案，我使用了 python 模块networkx。如果您的系统中没有它，则需要安装它。安装超出了本次讨论的范围，但您可以从谷歌搜索python pip开始。
  • 主力军正在networks.all_simple_paths()发挥作用。此函数查看图形、起点和终点，并返回连接起点和终点的所有路径。

我的方法

  1. 定义数据。我如何表示输入，最好是在文本文件中。
  2. 读取文本文件，构建图表
  3. 创建目标节点列表（AKA end_points）
  4. 对于 中的每个节点end_points，打印从起始节点 (967) 到该节点的路径

数据文件

我将输入表示为一个文本文件 (routes.txt)，其中每一行包含两个节点：源和目标。

967 973  
967 970 
970 396    
396 3269 
3269 3275 
3275 3278
3278 404 
3278 408 
404 448
408 410 
408 411 
448 454 
410 419 
410 433 
410 437 
411 412

编码

# routes.py
# Make sure you have `networkx` installed
import networkx

def build_routes():
    '''
    Reads a text file, where each line is a pair of nodes, then build
    a graph of all the nodes. Returns the graph and a list of leaf nodes
    '''
    routes = networkx.DiGraph()
    leaf_nodes = set()
    nonleaf_nodes = set()
    with open('routes.txt') as f:
        for line in f:
            # Each line consists of two nodes: a source and a
            # destination.
            source, destination = line.split()
            nonleaf_nodes.add(source)
            leaf_nodes.add(destination)
            routes.add_edge(source, destination)

    leaf_nodes.difference_update(nonleaf_nodes)
    return routes, leaf_nodes

def print_routes(routes, start_point, end_points):
    for end_point in end_points:
        for path in networkx.all_simple_paths(routes, start_point, end_point):
            print ' > '.join(path)

if __name__ == '__main__':
    routes, end_points = build_routes()
    print_routes(routes, '967', end_points)

输出

967 > 973
967 > 970 > 396 > 3269 > 3275 > 3278 > 404 > 448 > 454
967 > 970 > 396 > 3269 > 3275 > 3278 > 408 > 410 > 419
967 > 970 > 396 > 3269 > 3275 > 3278 > 408 > 411 > 412
967 > 970 > 396 > 3269 > 3275 > 3278 > 408 > 410 > 437
967 > 970 > 396 > 3269 > 3275 > 3278 > 408 > 410 > 433
于 2013-11-10T21:04:53.293 回答
0

据我了解，您想找到所有从967开始并且不能扩展的路线。

这里有一些代码可以找出最大路线，从 967 开始。

首先，我们需要输入“不完整路线”列表。可能的路线是这些对的串联。

steps = [
[967, 973],
[967, 970],
[970, 396],
[396, 3269],
[3269, 3275],
[3275, 3278],
[3278, 404],
[3278, 408],
[404, 448],
[408, 410],
[408, 411],
[448, 454],
[410, 419],
[410, 433],
[410, 437],
[411, 412],
]

从967开始，我们延伸路线，保持一切可能性。在这里，我定义了一个函数来增加中间路线的长度。

def add_steps(routes, finished_routes):
    new_routes = []
    for r in routes:
        end = r[-1]
        r_finished = True
        for s in steps:
            if s[0] == end:
                new_routes.append(r + [s[1]])
                r_finished = False
        if r_finished:
            finished_routes.append(r)
    return new_routes, finished_routes

你可以试试

>>> add_steps([[967]], [])

并得到

Out: ([[967, 973], [967, 970]], [])

那么，接下来

>>> add_steps([[967, 973], [967, 970]], [])
([[967, 970, 396]], [[967, 973]])

这意味着“[967, 970, 396]”是中间路由，可以扩展，“[967, 973]”是完成路由，不能再扩展。

重复此功能的应用，直到所有路线都完成。

routes = [[967]]
finished_routes = []
for n in range(20):
    routes, finished_routes = add_steps(routes, finished_routes)
    if not routes:
        print finished_routes
        break

打印出来的结果是

[[967, 973], [967, 970, 396, 3269, 3275, 3278, 404, 448, 454], [967, 970, 396, 3269, 3275, 3278, 408, 410, 419], [967, 970, 396, 3269, 3275, 3278, 408, 410, 433], [967, 970, 396, 3269, 3275, 3278, 408, 410, 437], [967, 970, 396, 3269, 3275, 3278, 408, 411, 412]]
于 2013-11-10T08:58:48.710 回答