2013-11-10 43 views
0

我需要python中的一些幫助。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 - [....] 

我嘗試了很多代碼,在變量比較和商店,但不工作。

我希望你們明白。

+3

格拉夫出來。谷歌「深度優先搜索」和/或「廣度優先搜索」。 – roippi

回答

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]] 
+0

謝謝,作品完美。 – user2975606

1

我不使用python 3道歉,因爲我沒有它安裝。請將print聲明轉換爲函數,它應該可以工作。

概述

根據您的問題聲明,我繪製你的路線如下:

enter image description here

通過看這個圖,我想出了幾點意見:

  • 如果我從967開始,我將結束以下節點(或站,或車站):973,454419,433,437412。我在代碼中調用那些節點leaf_nodesend_points
  • 你在問題陳述中稱爲「路線」只是完整路線的一部分。
  • 因此,「路線」數量是真正的節點在end_points
  • 對於這個解決方案的數量,我利用Python模塊networkx的。如果您的系統中沒有它,則需要安裝它。安裝超出了本次討論的範圍,但您可以先搜索python pip
  • 主力在networks.all_simple_paths()功能。該函數查看圖形,起點和終點,並返回連接起點和終點的所有路徑。

我的做法

  1. 定義數據。我如何表示輸入,最好是在文本文件中。
  2. 閱讀文本文件,建立圖
  3. 創建目標節點(又名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 
+0

謝謝,作品完美而快速。我印象深刻的是車輛有多少可能的路線選擇。再次感謝。 – user2975606