Hướng dẫn Tối ưu Hóa Đồ thị với Python NetworkX

Với hướng dẫn này, bạn sẽ giải một bài toán kinh điển trong lý thuyết đồ thị gọi là Bài toán Người đưa thư Trung Quốc. Một số thành phần của thuật toán tuy đơn giản về mặt khái niệm nhưng lại đòi hỏi tính toán khắt khe. Tuy nhiên, trong bài này, bạn chỉ cần biết trước một chút về Python: không cần nền tảng toán học, khoa học máy tính hay lý thuyết đồ thị chuyên sâu.

Trước tiên, hướng dẫn sẽ điểm lại các khối xây dựng cơ bản của đồ thị (nút, cạnh, đường đi, v.v.) và giải bài toán trên một đồ thị thực (mạng đường mòn của một công viên bang) bằng thư viện NetworkX trong Python. Bạn sẽ tập trung vào các khái niệm cốt lõi và cách triển khai. Với bạn đọc quan tâm, có phần đọc thêm về cơ chế tối ưu hóa ở bên trong.

Tạo động lực cho Tối ưu hóa Đồ thị

Bài toán

Chắc hẳn bạn đã nghe về Bài toán Người bán hàng Lưu động yêu cầu tìm lộ trình ngắn nhất (ví dụ, các con đường) nối một tập các nút (ví dụ, các thành phố). Ít nổi tiếng hơn nhưng khá tương tự là Bài toán Người đưa thư Trung Quốc (CPP), còn gọi là Bài toán Kiểm tra Lộ trình hoặc Định tuyến Cung. Mục tiêu của CPP là tìm đường đi ngắn nhất bao phủ tất cả các liên kết (đường) trên một đồ thị ít nhất một lần. Nếu có thể làm điều này mà không phải quay lại trên cùng một con đường hai lần thì quá tuyệt; đó là kịch bản lý tưởng và bài toán khá đơn giản. Tuy nhiên, nếu một số con đường buộc phải đi qua hơn một lần, bạn cần chút toán học để tìm lộ trình ngắn nhất đi qua mọi con đường ít nhất một lần với tổng số dặm nhỏ nhất.

Động lực cá nhân

(Phần sau là ghi chú cá nhân: sến, tinh nghịch và 100% không cần thiết để học tối ưu hóa đồ thị trong Python)

Tôi có một ứng dụng đời thực cho bài toán này: chinh phục danh hiệu Giantmaster Marathoner.

Giantmaster là gì? Một Giantmaster là người (chó hoặc người) đã đi hết mọi đường mòn của Sleeping Giant State Park ở Hamden CT (kề quê nhà tôi là Wallingford)... trong suốt cuộc đời họ. Giantmaster Marathoner là người đã đi hết các đường mòn đó trong một ngày.

Nhờ việc lưu trữ hồ sơ tỉ mỉ của Hội Sleeping Giant Park, danh sách đầy đủ các Giantmaster và cấp độ của họ có tại đây. Tôi phải thừa nhận điều này đã tiếp thêm động lực lớn để khởi động dự án nhỏ này và lao ra đường mòn. Dù bản thân tôi đã đạt trạng thái Giantmaster vào mùa đông năm 2006 khi còn là một tình nguyện viên trẻ của Sleeping Giant Trail Crew (mà tôi vui khi thấy được ghi lại trong lưu trữ SG), thì những thử thách mới đã xuất hiện sau đó. Dù các hạng mục Giantmaster 12 tháng và 4 mùa rất ấn tượng và hấp dẫn, chúng cũng đòi hỏi tôi phải đi lại nhiều hơn giữa nơi ở hiện tại (DC) và nơi trưởng thành (CT) so với khả năng... và chúng cũng không thú vị bằng cho tối ưu hóa đồ thị, nên chọn Giantmaster Marathon vậy!

Để tham khảo thêm, bản đồ đường mòn Sleeping Giant ở bên dưới:

Giới thiệu về Đồ thị

Điểm hay ở đồ thị là khái niệm và thuật ngữ thường trực quan. Dẫu vậy, dưới đây là vài thuật ngữ cơ bản:

Đồ thị là cấu trúc biểu diễn các quan hệ giữa các đối tượng. Các đối tượng được gọi là nút và các kết nối giữa chúng là cạnh trong hướng dẫn này. Lưu ý cạnh và nút thường có nhiều tên gọi khác nhau nhưng nhìn chung đồng nghĩa:

node == vertex == point
edge == arc == link
Được hỗ trợ bởi

Đồ thị ban đầu là vô hướng. Tức là các cạnh không có hướng: chúng hai chiều. Ví dụ: A<--->B == B<--->A.
Trái lại, đồ thị bạn có thể tạo để chỉ ra đường ngắn nhất đi hết mọi đường mòn có thể là đồ thị có hướng, nơi thứ tự và hướng của cạnh quan trọng. Ví dụ: A--->B != B--->A.

Đồ thị này cũng là đồ thị có trọng số cạnh trong đó khoảng cách (tính bằng dặm) giữa mỗi cặp nút kề nhau biểu diễn trọng số của một cạnh. Điều này được xử lý như một thuộc tính cạnh tên là "distance".

Bậc chỉ số lượng cạnh kề (chạm vào) một nút. Nút được gọi là bậc lẻ khi con số này là lẻ và bậc chẵn khi là chẵn.

Lời giải cho CPP này sẽ là một chu trình Euler: một đồ thị trong đó tồn tại một chu trình đi qua mỗi cạnh chính xác một lần, xuất phát từ một nút và quay lại chính nó (không đi lùi). Chu trình Euler còn có vài tên khác:

Eulerian tour == Eulerian circuit == Eulerian cycle
Được hỗ trợ bởi

Matching là một tập con các cạnh trong đó không có nút nào xuất hiện quá một lần. Matching trọng số tối thiểu tìm matching có tổng trọng số cạnh nhỏ nhất có thể.

NetworkX: Thao tác và Phân tích Đồ thị

NetworkX là gói Python phổ biến nhất để thao tác và phân tích đồ thị. Một số gói khác cung cấp mức thao tác cơ bản tương tự, đáng chú ý có igraph cũng có binding cho R và C++. Tuy nhiên, tôi thấy NetworkX có các thuật toán đồ thị mạnh nhất mà tôi cần để giải CPP.

Cài đặt Gói

Nếu bạn đã từng phân tích dữ liệu bằng Python hoặc dùng bản phân phối Anaconda, nhiều khả năng bạn đã có pandas và matplotlib. Tuy nhiên, bạn có thể chưa có networkx. Đây sẽ là các phụ thuộc duy nhất ngoài Python Standard Library mà bạn cần để chạy qua hướng dẫn này. Chúng rất dễ cài bằng pip:

pip install pandas
pip install networkx
pip install matplotlib
Được hỗ trợ bởi

Chừng đó là đủ cho lúc này. imageio và numpy được import ở cuối để tạo ảnh GIF minh họa lời giải CPP. Ảnh động đã được nhúng trong bài, vì vậy các gói này là tùy chọn.

import itertools
import copy
import networkx as nx
import pandas as pd
import matplotlib.pyplot as pltĐược hỗ trợ bởi

Nạp Dữ liệu

Danh sách Cạnh

Danh sách cạnh là cấu trúc dữ liệu đơn giản bạn sẽ dùng để tạo đồ thị. Mỗi hàng biểu diễn một cạnh của đồ thị với một số thuộc tính cạnh.

node1 & node2: tên các nút được kết nối.
trail: thuộc tính cạnh cho biết tên viết tắt của đường mòn ứng với mỗi cạnh. Ví dụ: rs = red square
distance: thuộc tính cạnh cho biết độ dài đường mòn theo dặm.
color: màu đường mòn dùng để vẽ.
estimate: thuộc tính cạnh cho biết khoảng cách cạnh được ước lượng từ việc ước chừng trên bản đồ đường mòn (1=có, 0=không) vì một số khoảng cách không được cung cấp. Đây chỉ để tham khảo; không dùng cho phân tích.

# Grab edge list data hosted on Gist
edgelist = pd.read_csv('https://gist.githubusercontent.com/brooksandrew/e570c38bcc72a8d102422f2af836513b/raw/89c76b2563dbc0e88384719a35cba0dfc04cd522/edgelist_sleeping_giant.csv')
Được hỗ trợ bởi

# Preview edgelist
edgelist.head(10)
Được hỗ trợ bởi

	node1	node2	trail	distance	color
0	rs_end_north	v_rs	rs	0.30	red
1	v_rs	b_rs	rs	0.21	red
2	b_rs	g_rs	rs	0.11	red
3	g_rs	w_rs	rs	0.18	red
4	w_rs	o_rs	rs	0.21	red
5	o_rs	y_rs	rs	0.12	red
6	y_rs	rs_end_south	rs	0.39	red
7	rc_end_north	v_rc	rc	0.70	red
8	v_rc	b_rc	rc	0.04	red
9	b_rc	g_rc	rc	0.15	red

Danh sách Nút

Danh sách nút thường là tùy chọn trong networkx và các thư viện đồ thị khác khi đã có danh sách cạnh, vì tên nút đã có ở hai cột đầu. Tuy nhiên, trong trường hợp này, có một số thuộc tính nút muốn bổ sung: tọa độ X, Y của các nút (giao điểm đường mòn) để bạn có thể vẽ đồ thị với bố cục giống bản đồ đường mòn.

Tôi đã dành một buổi chiều để gắn nhãn thủ công bằng cách vẽ đè lên ảnh với GIMP:

id: tên của nút tương ứng với node1 và node2 trong danh sách cạnh.
X: vị trí/tọa độ ngang của nút tương đối so với góc trên bên trái.
Y vị trí/tọa độ dọc của nút tương đối so với góc trên bên trái.

Lưu ý về việc tạo danh sách Nút & Cạnh

Việc tạo tên nút cũng cần chút công sức thủ công. Mỗi nút biểu diễn một giao điểm của từ hai đường mòn trở lên. Khi có thể, nút được đặt tên theo dạng trail1_trail2 trong đó trail1 đứng trước trail2 theo thứ tự bảng chữ cái.

Mọi thứ khó hơn khi cùng một cặp đường mòn giao nhau nhiều hơn một lần. Ví dụ, đường mòn Cam và Trắng. Trong các trường hợp đó, tôi thêm hậu tố _2 hoặc _3 vào tên nút. Ví dụ, bạn có hai tên nút riêng cho hai giao điểm khác nhau giữa Cam và Trắng: o_w và o_w_2.

Việc này cần nhiều thử-sai và so sánh các biểu đồ tạo bằng tọa độ X,Y với bản đồ đường mòn thực.

# Grab node list data hosted on Gist
nodelist = pd.read_csv('https://gist.githubusercontent.com/brooksandrew/f989e10af17fb4c85b11409fea47895b/raw/a3a8da0fa5b094f1ca9d82e1642b384889ae16e8/nodelist_sleeping_giant.csv')
Được hỗ trợ bởi

# Preview nodelist
nodelist.head(5)
Được hỗ trợ bởi

	id	X	Y
0	b_bv	1486	732
1	b_bw	716	1357
2	b_end_east	3164	1111
3	b_end_west	141	1938
4	b_g	1725	771

Tạo Đồ thị

Bây giờ bạn dùng danh sách cạnh và danh sách nút để tạo một đối tượng đồ thị trong networkx.

# Create empty graph
g = nx.Graph()
Được hỗ trợ bởi

Lặp qua các hàng của danh sách cạnh và thêm mỗi cạnh cùng các thuộc tính tương ứng vào đồ thị g.

# Add edges and edge attributes
for i, elrow in edgelist.iterrows():
    g.add_edge(elrow[0], elrow[1], attr_dict=elrow[2:].to_dict())
Được hỗ trợ bởi

Để minh họa điều đang xảy ra, hãy in các giá trị từ hàng cuối cùng trong danh sách cạnh vừa được thêm vào đồ thị g:

# Edge list example
print(elrow[0]) # node1
print(elrow[1]) # node2
print(elrow[2:].to_dict()) # edge attribute dict
Được hỗ trợ bởi

o_gy2
y_gy2
{'color': 'yellowgreen', 'estimate': 0, 'trail': 'gy2', 'distance': 0.12}
Được hỗ trợ bởi

Tương tự, bạn lặp qua các hàng trong danh sách nút và thêm các thuộc tính nút này.

# Add node attributes
for i, nlrow in nodelist.iterrows():
    g.node[nlrow['id']] = nlrow[1:].to_dict()
Được hỗ trợ bởi

Ví dụ từ hàng cuối của danh sách nút:

# Node list example
print(nlrow)
Được hỗ trợ bởi

id    y_rt
X      977
Y     1666
Name: 76, dtype: objectĐược hỗ trợ bởi

Khám sát Đồ thị

Các cạnh

Các cạnh của bạn được biểu diễn bởi một danh sách các bộ 3 phần tử. Hai phần tử đầu là tên các nút được cạnh liên kết. Phần thứ ba là từ điển thuộc tính cạnh.

# Preview first 5 edges
g.edges(data=True)[0:5]
Được hỗ trợ bởi

[('rs_end_south',
  'y_rs',
  {'color': 'red', 'distance': 0.39, 'estimate': 0, 'trail': 'rs'}),
 ('w_gy2',
  'park_east',
  {'color': 'gray', 'distance': 0.12, 'estimate': 0, 'trail': 'w'}),
 ('w_gy2',
  'g_gy2',
  {'color': 'yellowgreen', 'distance': 0.05, 'estimate': 0, 'trail': 'gy2'}),
 ('w_gy2',
  'b_w',
  {'color': 'gray', 'distance': 0.42, 'estimate': 0, 'trail': 'w'}),
 ('w_gy2',
  'b_gy2',
  {'color': 'yellowgreen', 'distance': 0.03, 'estimate': 1, 'trail': 'gy2'})]
Được hỗ trợ bởi

Các nút

Tương tự, các nút được biểu diễn bởi một danh sách các bộ 2 phần tử. Phần tử đầu là ID nút, tiếp theo là từ điển thuộc tính nút.

# Preview first 10 nodes
g.nodes(data=True)[0:10]
Được hỗ trợ bởi

[('rs_end_south', {'X': 1865, 'Y': 1598}),
 ('w_gy2', {'X': 2000, 'Y': 954}),
 ('rd_end_south_dupe', {'X': 273, 'Y': 1869}),
 ('w_gy1', {'X': 1184, 'Y': 1445}),
 ('g_rt', {'X': 908, 'Y': 1378}),
 ('v_rd', {'X': 258, 'Y': 1684}),
 ('g_rs', {'X': 1676, 'Y': 775}),
 ('rc_end_north', {'X': 867, 'Y': 618}),
 ('v_end_east', {'X': 2131, 'Y': 921}),
 ('rh_end_south', {'X': 721, 'Y': 1925})]
Được hỗ trợ bởi

Thống kê tóm tắt

In ra vài thống kê tóm tắt trước khi trực quan hóa đồ thị.

print('# of edges: {}'.format(g.number_of_edges()))
print('# of nodes: {}'.format(g.number_of_nodes()))
Được hỗ trợ bởi

# of edges: 123
# of nodes: 77Được hỗ trợ bởi

Trực quan hóa Đồ thị

Xử lý màu sắc và bố cục

Vị trí: Trước hết bạn cần chuyển vị trí các nút từ đồ thị vào một từ điển. Điều này cho phép bạn tái tạo đồ thị với bố cục trùng với bản đồ đường mòn thực. Y được đổi dấu để chuyển gốc trục tung từ góc trên trái sang dưới trái.

# Define node positions data structure (dict) for plotting
node_positions = {node[0]: (node[1]['X'], -node[1]['Y']) for node in g.nodes(data=True)}

# Preview of node_positions with a bit of hack (there is no head/slice method for dictionaries).
dict(list(node_positions.items())[0:5])
Được hỗ trợ bởi

{'b_rd': (268, -1744),
 'g_rt': (908, -1378),
 'o_gy1': (1130, -1297),
 'rh_end_tt_2': (550, -1608),
 'rs_end_south': (1865, -1598)}
Được hỗ trợ bởi

Màu sắc: Giờ bạn chuyển màu cạnh từ đồ thị vào một danh sách đơn giản để trực quan hóa đường mòn theo màu của chúng.

# Define data structure (list) of edge colors for plotting
edge_colors = [e[2]['color'] for e in g.edges(data=True)]

# Preview first 10
edge_colors[0:10]
Được hỗ trợ bởi

['red',
 'gray',
 'yellowgreen',
 'gray',
 'yellowgreen',
 'blue',
 'black',
 'yellowgreen',
 'gray',
 'gray']
Được hỗ trợ bởi

Vẽ biểu đồ

Bây giờ bạn có thể vẽ một hình đẹp khớp khá sát với bản đồ đường mòn Sleeping Giant:

plt.figure(figsize=(8, 6))
nx.draw(g, pos=node_positions, edge_color=edge_colors, node_size=10, node_color='black')
plt.title('Graph Representation of Sleeping Giant Trail Map', size=15)
plt.show()
Được hỗ trợ bởi

Biểu diễn đồ thị này dĩ nhiên không thể hiện mọi khúc cua ngoằn ngoèo của đường mòn, nhưng đừng lo: những điều đó được nắm bắt chính xác trong thuộc tính distance của cạnh để dùng cho tính toán. Hình vẽ có thể hiện khoảng cách giữa các nút (giao điểm đường mòn) theo đường chim bay, và có vẻ là một xấp xỉ chấp nhận được.

Tổng quan Thuật toán CPP

OK, giờ khi bạn đã định nghĩa thuật ngữ và tạo đồ thị, làm sao tìm đường ngắn nhất xuyên suốt nó?

Giải Bài toán Người đưa thư Trung Quốc khá đơn giản về mặt khái niệm:

Tìm tất cả các nút có bậc lẻ (rất dễ).
(Tìm mọi giao điểm đường mòn nơi số đường mòn chạm vào giao điểm đó là số lẻ)
Thêm các cạnh vào đồ thị sao cho mọi nút bậc lẻ trở thành bậc chẵn. Các cạnh thêm vào phải là bản sao từ đồ thị gốc (chúng ta giả định không đi tắt xuyên rừng trong bài này). Tập cạnh thêm vào nên có tổng khoảng cách nhỏ nhất có thể (khó... chính xác là np-hard).
(Nói đơn giản, tối thiểu hóa lượng quay lại trên một lộ trình đi qua mọi đường mòn)
Cho một điểm xuất phát, tìm chu trình Euler trên tập dữ liệu đã được bổ sung (khá dễ).
(Khi đã biết các đường mòn sẽ phải đi lại, thực sự tính lộ trình từ đầu đến cuối)

Giả định và Đơn giản hóa

Dù có thể tạo lộ trình ngắn hơn và chính xác hơn bằng cách nới lỏng các giả định dưới đây, điều đó sẽ làm tăng độ phức tạp vượt ngoài phạm vi hướng dẫn này, vốn tập trung vào CPP.

Giả định 1: Chỉ tính các đường mòn bắt buộc

Như bạn thấy trên bản đồ đường mòn bên trên, có các con đường dọc biên công viên có thể dùng để nối các đường mòn, đặc biệt là đường mòn đỏ. Cũng có một số đường mòn (Horseshoe và các vạch không đánh dấu) không bắt buộc theo sổ log Giantmaster, nhưng có thể hữu ích để tránh quay lại dài. Việc đưa các đường mòn tùy chọn vào thực ra là một biến thể có sẵn của CPP gọi là Bài toán Người đưa thư Nông thôn. Trong hướng dẫn này chúng ta bỏ qua đường mòn tùy chọn và chỉ tập trung vào đường mòn bắt buộc.

Giả định 2: Lên dốc == xuống dốc

CPP giả định chi phí đi một đường mòn tương đương với khoảng cách của nó, bất kể đi theo hướng nào. Tuy nhiên, một số đường mòn khá dốc và sẽ tốn nhiều năng lượng hơn khi đi lên so với đi xuống. Một thước đo kết hợp cả khoảng cách và thay đổi độ cao trên đồ thị có hướng có thể được đưa vào phần mở rộng của CPP gọi là Bài toán Người đưa thư Gió.

Giả định 3: Không có cạnh (đường mòn) song song

Dù khả thi, việc đưa cạnh song song (nhiều đường mòn nối cùng hai nút) làm tăng phức tạp tính toán. May mắn là ở đây chỉ xảy ra hai lần (Blue <=> Red Diamond và Blue <=> Tower Trail). Điều này được xử lý bằng một mẹo nhỏ với danh sách cạnh: thêm các nút trùng với hậu tố _dupe để ghi nhận mọi đường mòn đồng thời vẫn đảm bảo cạnh là duy nhất. Triển khai CPP trong gói postman_problems tôi viết có xử lý vững chắc cạnh song song theo cách tao nhã hơn, nếu bạn muốn tự giải CPP trên đồ thị của mình với nhiều cạnh song song.

Bước CPP 1: Tìm các nút bậc lẻ

Đây là phép đếm khá trực diện. Bạn thấy 36 trong số 76 nút có bậc lẻ. Chủ yếu là các đường mòn cụt (bậc 1) và giao điểm của 3 đường mòn. Có một vài nút bậc 5.

# Calculate list of nodes with odd degree
nodes_odd_degree = [v for v, d in g.degree_iter() if d % 2 == 1]

# Preview
nodes_odd_degree[0:5]
Được hỗ trợ bởi

['rs_end_south', 'rc_end_north', 'v_end_east', 'rh_end_south', 'b_end_east']
Được hỗ trợ bởi

# Counts
print('Number of nodes of odd degree: {}'.format(len(nodes_odd_degree)))
print('Number of total nodes: {}'.format(len(g.nodes())))
Được hỗ trợ bởi

Number of nodes of odd degree: 36
Number of total nodes: 77
Được hỗ trợ bởi

Bước CPP 2: Tìm các cặp có khoảng cách nhỏ nhất

Đây mới là phần cốt lõi của bài toán. Bạn sẽ chia thành 5 phần:

Tính mọi cặp có thể của các nút bậc lẻ.
Tính đường đi ngắn nhất giữa mỗi cặp nút ở 1.
Tạo một đồ thị đầy đủ nối mọi cặp nút ở 1. với thuộc tính khoảng cách đường đi ngắn nhất tính ở 2.
Tính matching trọng số tối thiểu của đồ thị ở 3.
(Cốt lõi là xác định cách ghép cặp các nút lẻ sao cho tổng khoảng cách giữa các cặp là nhỏ nhất).
Bổ sung đồ thị gốc bằng các đường đi ngắn nhất giữa các cặp nút tính ở 4.

Bước 2.1: Tính các cặp nút

Bạn dùng hàm itertools combination để tính mọi cặp có thể của các nút bậc lẻ. Đồ thị của bạn là vô hướng, nên không quan tâm thứ tự: Ví dụ, (a,b) == (b,a).

# Compute all pairs of odd nodes. in a list of tuples
odd_node_pairs = list(itertools.combinations(nodes_odd_degree, 2))

# Preview pairs of odd degree nodes
odd_node_pairs[0:10]
Được hỗ trợ bởi

[('rs_end_south', 'rc_end_north'),
 ('rs_end_south', 'v_end_east'),
 ('rs_end_south', 'rh_end_south'),
 ('rs_end_south', 'b_end_east'),
 ('rs_end_south', 'b_bv'),
 ('rs_end_south', 'rt_end_south'),
 ('rs_end_south', 'o_rt'),
 ('rs_end_south', 'y_rt'),
 ('rs_end_south', 'g_gy2'),
 ('rs_end_south', 'b_tt_3')]
Được hỗ trợ bởi

# Counts
print('Number of pairs: {}'.format(len(odd_node_pairs)))
Được hỗ trợ bởi

Number of pairs: 630
Được hỗ trợ bởi

Hãy xác nhận con số các cặp này đúng bằng tổ hợp dưới đây. May mắn là bạn chỉ có 630 cặp cần quan tâm. Thời gian tính toán để giải ví dụ CPP này là rất nhỏ (vài giây).

Tuy nhiên, nếu có 3.600 cặp nút lẻ, bạn sẽ có khoảng 6,5 triệu cặp để tối ưu. Đó là mức tăng ~10.000 lần đầu ra với đầu vào tăng 100 lần.

\begin{equation*} \#\;of\;pairs = n\;choose\;r = {n \choose r} = \frac{n!}{r!(n-r)!} = \frac{36!}{2! (36-2)!} = 630 \end{equation*}

Bước 2.2: Tính các đường đi ngắn nhất giữa các cặp nút

Đây là bước đầu tiên liên quan đến tính toán thực sự. May mắn là networkx có triển khai tiện lợi thuật toán Dijkstra để tính đường đi ngắn nhất giữa hai nút. Bạn áp dụng hàm này cho mọi cặp (cả 630) đã tính trong odd_node_pairs.

def get_shortest_paths_distances(graph, pairs, edge_weight_name):
    """Compute shortest distance between each pair of nodes in a graph.  Return a dictionary keyed on node pairs (tuples)."""
    distances = {}
    for pair in pairs:
        distances[pair] = nx.dijkstra_path_length(graph, pair[0], pair[1], weight=edge_weight_name)
    return distances
Được hỗ trợ bởi

# Compute shortest paths.  Return a dictionary with node pairs keys and a single value equal to shortest path distance.
odd_node_pairs_shortest_paths = get_shortest_paths_distances(g, odd_node_pairs, 'distance')

# Preview with a bit of hack (there is no head/slice method for dictionaries).
dict(list(odd_node_pairs_shortest_paths.items())[0:10])
Được hỗ trợ bởi

{('b_bv', 'y_gy1'): 1.22,
 ('b_bw', 'rc_end_south'): 1.35,
 ('b_end_east', 'b_bw'): 3.0400000000000005,
 ('b_end_east', 'rd_end_north'): 3.83,
 ('g_gy1', 'nature_end_west'): 0.9900000000000001,
 ('o_rt', 'y_gy1'): 0.53,
 ('rc_end_north', 'rd_end_south'): 2.21,
 ('rc_end_north', 'rs_end_north'): 1.79,
 ('rs_end_north', 'o_tt'): 2.0999999999999996,
 ('w_bw', 'rd_end_north'): 1.02}
Được hỗ trợ bởi

Bước 2.3: Tạo Đồ thị Đầy đủ

Một đồ thị đầy đủ đơn giản là đồ thị nơi mọi nút được nối với mọi nút khác bằng một cạnh duy nhất.

Đây là ví dụ cơ bản từ Wikipedia về đồ thị đầy đủ 7 nút với 21 cạnh (7 chọn 2):

Đồ thị bạn tạo dưới đây có 36 nút và 630 cạnh với trọng số cạnh (khoảng cách) tương ứng.

create_complete_graph được định nghĩa để tính toán nó. Tham số flip_weights dùng để chuyển distance thành thuộc tính weight sao cho số nhỏ phản ánh khoảng cách lớn và số lớn phản ánh khoảng cách ngắn. Nghe hơi ngược đời, nhưng cần thiết cho Bước 2.4 nơi bạn tính matching trọng số tối thiểu trên đồ thị đầy đủ.

Lý tưởng nhất bạn sẽ tính trực tiếp matching trọng số tối thiểu, nhưng NetworkX chỉ triển khai hàm max_weight_matching để tối đa hóa, thay vì tối thiểu hóa trọng số cạnh. Ta lách một chút bằng cách đổi dấu (nhân -1) thuộc tính distance để được weight. Cách này giữ nguyên thứ tự và tỉ lệ theo khoảng cách, nhưng đảo ngược.

def create_complete_graph(pair_weights, flip_weights=True):
    """
    Create a completely connected graph using a list of vertex pairs and the shortest path distances between them
    Parameters:
        pair_weights: list[tuple] from the output of get_shortest_paths_distances
        flip_weights: Boolean. Should we negate the edge attribute in pair_weights?
    """
    g = nx.Graph()
    for k, v in pair_weights.items():
        wt_i = - v if flip_weights else v
        g.add_edge(k[0], k[1], attr_dict={'distance': v, 'weight': wt_i})
    return g
Được hỗ trợ bởi

# Generate the complete graph
g_odd_complete = create_complete_graph(odd_node_pairs_shortest_paths, flip_weights=True)

# Counts
print('Number of nodes: {}'.format(len(g_odd_complete.nodes())))
print('Number of edges: {}'.format(len(g_odd_complete.edges())))
Được hỗ trợ bởi

Number of nodes: 36
Number of edges: 630
Được hỗ trợ bởi

Để hỗ trợ hình dung, đồ thị đầy đủ của các cặp nút bậc lẻ được vẽ bên dưới. Lưu ý bạn giữ nguyên tọa độ X, Y của mỗi nút, nhưng các cạnh không nhất thiết đại diện cho đường mòn thực. Ví dụ, hai nút có thể kết nối bởi một cạnh trong đồ thị này, nhưng đường đi ngắn nhất giữa chúng có thể gồm 5 bước qua các nút bậc chẵn (không hiển thị ở đây).

# Plot the complete graph of odd-degree nodes
plt.figure(figsize=(8, 6))
pos_random = nx.random_layout(g_odd_complete)
nx.draw_networkx_nodes(g_odd_complete, node_positions, node_size=20, node_color="red")
nx.draw_networkx_edges(g_odd_complete, node_positions, alpha=0.1)
plt.axis('off')
plt.title('Complete Graph of Odd-degree Nodes')
plt.show()
Được hỗ trợ bởi

Bước 2.4: Tính Matching Trọng số Tối thiểu

Đây là bước phức tạp nhất trong CPP. Bạn cần tìm các cặp nút bậc lẻ sao cho tổng (khoảng cách giữa chúng) là nhỏ nhất. Với bài toán của bạn, điều này quy về chọn 18 cạnh tối ưu (36 nút bậc lẻ / 2) từ mớ cạnh trong đồ thị sinh ra ở 2.3.

Cả việc triển khai lẫn trực giác của tối ưu hóa này đều vượt ngoài phạm vi hướng dẫn... như là hơn 800 dòng mã và cả một kho tài liệu học thuật.

Tuy nhiên, đôi lời cho bạn đọc quan tâm:

Xin cảm ơn Joris van Rantwijk vì đã viết triển khai gốc trên blog của anh từ tận năm 2008. Tôi tình cờ gặp bài toán theo cách tương tự và cùng ý định như Joris. Từ bài đăng 2008 của Joris:

Vì tôi không tìm thấy bất kỳ triển khai Perl nào cho maximum weighted matching, tôi đã nhẹ nhàng quyết định tự viết chút mã. Hóa ra tôi đã đánh giá thấp bài toán, nhưng đến lúc nhận ra sai lầm thì tôi đã ám ảnh đến mức từ chối bỏ cuộc.

Tuy nhiên, tôi đã bỏ cuộc. May mắn là Joris thì không.

Thuật toán Maximum Weight Matching này sau đó đã được đưa vào và duy trì trong gói NetworkX. Xin gửi lời cảm ơn lớn đến hơn 10 cộng tác viên trên GitHub đã duy trì mã nguồn đồ sộ này.

Đây là phép tính khó và nặng. Bước đột phá đầu tiên vào năm 1965 chứng minh Bài toán Matching Tối đa có thể giải trong thời gian đa thức. Bài báo của Jack Edmonds có lẽ mang một trong những tiêu đề đẹp nhất: "Paths, trees, and flowers" [1]. Từ đó, đã có một kho tài liệu xây dựng trên công trình này, cải tiến quy trình tối ưu. Mã trong hàm max_weight_matching của NetworkX dựa trên Galil, Zvi (1986) [2] sử dụng thuật toán thời gian O(n³).

# Compute min weight matching.
# Note: max_weight_matching uses the 'weight' attribute by default as the attribute to maximize.
odd_matching_dupes = nx.algorithms.max_weight_matching(g_odd_complete, True)

print('Number of edges in matching: {}'.format(len(odd_matching_dupes)))
Được hỗ trợ bởi

Number of edges in matching: 36
Được hỗ trợ bởi

Kết quả matching (odd_matching_dupes) là một từ điển. Dù có 36 cạnh trong matching này, bạn chỉ muốn 18. Mỗi cặp cạnh xuất hiện hai lần (một lần với nút 1 là khóa và lần nữa với nút 2 là khóa của từ điển).

# Preview of matching with dupes
odd_matching_dupes
Được hỗ trợ bởi

{'b_bv': 'v_bv',
 'b_bw': 'rh_end_tt_1',
 'b_end_east': 'g_gy2',
 'b_end_west': 'rd_end_south',
 'b_tt_3': 'rt_end_north',
 'b_v': 'v_end_west',
 'g_gy1': 'rc_end_north',
 'g_gy2': 'b_end_east',
 'g_w': 'w_bw',
 'nature_end_west': 'o_y_tt_end_west',
 'o_rt': 'o_w_1',
 'o_tt': 'rh_end_tt_2',
 'o_w_1': 'o_rt',
 'o_y_tt_end_west': 'nature_end_west',
 'rc_end_north': 'g_gy1',
 'rc_end_south': 'y_gy1',
 'rd_end_north': 'rh_end_north',
 'rd_end_south': 'b_end_west',
 'rh_end_north': 'rd_end_north',
 'rh_end_south': 'y_rh',
 'rh_end_tt_1': 'b_bw',
 'rh_end_tt_2': 'o_tt',
 'rh_end_tt_3': 'rh_end_tt_4',
 'rh_end_tt_4': 'rh_end_tt_3',
 'rs_end_north': 'v_end_east',
 'rs_end_south': 'y_gy2',
 'rt_end_north': 'b_tt_3',
 'rt_end_south': 'y_rt',
 'v_bv': 'b_bv',
 'v_end_east': 'rs_end_north',
 'v_end_west': 'b_v',
 'w_bw': 'g_w',
 'y_gy1': 'rc_end_south',
 'y_gy2': 'rs_end_south',
 'y_rh': 'rh_end_south',
 'y_rt': 'rt_end_south'}
Được hỗ trợ bởi

Bạn chuyển từ điển này thành danh sách các bộ vì đồ thị là vô hướng và thứ tự không quan trọng. Loại trùng cho ra 18 cặp cạnh duy nhất có tổng khoảng cách nhỏ nhất có thể.

# Convert matching to list of deduped tuples
odd_matching = list(pd.unique([tuple(sorted([k, v])) for k, v in odd_matching_dupes.items()]))

# Counts
print('Number of edges in matching (deduped): {}'.format(len(odd_matching)))
Được hỗ trợ bởi

Number of edges in matching (deduped): 18
Được hỗ trợ bởi

# Preview of deduped matching
odd_matching
Được hỗ trợ bởi

[('rs_end_south', 'y_gy2'),
 ('b_end_west', 'rd_end_south'),
 ('b_bv', 'v_bv'),
 ('rh_end_tt_3', 'rh_end_tt_4'),
 ('b_bw', 'rh_end_tt_1'),
 ('o_tt', 'rh_end_tt_2'),
 ('g_w', 'w_bw'),
 ('b_end_east', 'g_gy2'),
 ('nature_end_west', 'o_y_tt_end_west'),
 ('g_gy1', 'rc_end_north'),
 ('o_rt', 'o_w_1'),
 ('rs_end_north', 'v_end_east'),
 ('rc_end_south', 'y_gy1'),
 ('rh_end_south', 'y_rh'),
 ('rt_end_south', 'y_rt'),
 ('b_tt_3', 'rt_end_north'),
 ('rd_end_north', 'rh_end_north'),
 ('b_v', 'v_end_west')]
Được hỗ trợ bởi

Hãy trực quan hóa các cặp này trên đồ thị đầy đủ đã vẽ ở bước 2.3. Như trước, vị trí nút phản ánh đồ thị thật (bản đồ đường mòn), còn khoảng cách cạnh hiển thị (đường xanh) là theo đường chim bay. Đường thực tế ngắn nhất giữa hai nút có thể gồm nhiều cạnh uốn lượn với khoảng cách dài hơn đáng kể.

plt.figure(figsize=(8, 6))

# Plot the complete graph of odd-degree nodes
nx.draw(g_odd_complete, pos=node_positions, node_size=20, alpha=0.05)

# Create a new graph to overlay on g_odd_complete with just the edges from the min weight matching
g_odd_complete_min_edges = nx.Graph(odd_matching)
nx.draw(g_odd_complete_min_edges, pos=node_positions, node_size=20, edge_color='blue', node_color='red')

plt.title('Min Weight Matching on Complete Graph')
plt.show()
Được hỗ trợ bởi

Để minh họa điều này ăn khớp với đồ thị gốc ra sao, bạn vẽ lại các cặp trọng số tối thiểu (đường xanh), nhưng đè lên bản đồ đường mòn (mờ) thay vì đồ thị đầy đủ. Lưu ý lần nữa, các đường xanh là lối đi xuyên rừng (các cạnh theo đường chim bay, không phải đường mòn thực). Bạn vẫn còn chút việc để tìm các cạnh cấu thành đường đi ngắn nhất giữa mỗi cặp ở Bước 3.

plt.figure(figsize=(8, 6))

# Plot the original trail map graph
nx.draw(g, pos=node_positions, node_size=20, alpha=0.1, node_color='black')

# Plot graph to overlay with just the edges from the min weight matching
nx.draw(g_odd_complete_min_edges, pos=node_positions, node_size=20, alpha=1, node_color='red', edge_color='blue')

plt.title('Min Weight Matching on Orginal Graph')
plt.show()
Được hỗ trợ bởi

Bước 2.5: Bổ sung Đồ thị Gốc

Giờ bạn bổ sung đồ thị gốc bằng các cạnh từ matching tính ở 2.4. Hàm đơn giản dưới đây làm việc này và cũng ghi chú rằng các cạnh mới đến từ đồ thị bổ sung. Bạn sẽ cần biết điều này ở 3. khi thực sự tạo chu trình Euler xuyên đồ thị.

def add_augmenting_path_to_graph(graph, min_weight_pairs):
    """
    Add the min weight matching edges to the original graph
    Parameters:
        graph: NetworkX graph (original graph from trailmap)
        min_weight_pairs: list[tuples] of node pairs from min weight matching
    Returns:
        augmented NetworkX graph
    """

    # We need to make the augmented graph a MultiGraph so we can add parallel edges
    graph_aug = nx.MultiGraph(graph.copy())
    for pair in min_weight_pairs:
        graph_aug.add_edge(pair[0],
                           pair[1],
                           attr_dict={'distance': nx.dijkstra_path_length(graph, pair[0], pair[1]),
                                      'trail': 'augmented'}
                          )
    return graph_aug
Được hỗ trợ bởi

Hãy xác nhận rằng đồ thị bổ sung của bạn thêm đúng số cạnh (18):

# Create augmented graph: add the min weight matching edges to g
g_aug = add_augmenting_path_to_graph(g, odd_matching)

# Counts
print('Number of edges in original graph: {}'.format(len(g.edges())))
print('Number of edges in augmented graph: {}'.format(len(g_aug.edges())))
Được hỗ trợ bởi

Number of edges in original graph: 123
Number of edges in augmented graph: 141
Được hỗ trợ bởi

Đồng thời xác nhận rằng mọi nút giờ đều có bậc chẵn:

pd.value_counts(g_aug.degree())
Được hỗ trợ bởi

4    54
2    18
6     5
dtype: int64
Được hỗ trợ bởi

Bước CPP 3: Tính Chu trình Euler

Khi bạn đã có đồ thị với các bậc chẵn thì phần tối ưu khó đã xong. Như Euler đã nêu từ năm 1736 với bài toán Bảy cây cầu ở Königsberg, tồn tại đường đi ghé thăm mỗi cạnh đúng một lần nếu tất cả các nút đều có bậc chẵn. Carl Hierholzer sau đó đã chứng minh chính thức kết quả này vào thập niên 1870.

Có nhiều chu trình Euler với cùng khoảng cách có thể xây dựng. Bạn có thể đi được 90% chặng đường bằng hàm eulerian_circuit của NetworkX. Tuy nhiên có vài hạn chế.

Hạn chế bạn sẽ khắc phục:

Đồ thị bổ sung có thể (và nhiều khả năng) chứa các cạnh không tồn tại trên đồ thị gốc. Để có chu trình (không đi tắt xuyên rừng), bạn phải phân rã các cạnh bổ sung này thành đường đi ngắn nhất qua các cạnh thực sự tồn tại.
eulerian_circuit chỉ trả về thứ tự ta đi qua mỗi nút. Nó không trả về các thuộc tính cạnh cần thiết để hoàn tất chu trình. Điều này cần thiết vì bạn phải theo dõi cạnh nào đã đi qua khi có nhiều cạnh giữa hai nút.

Hạn chế bạn sẽ không khắc phục:

Để đỡ vất vả đôi chân, bạn có thể nới giả định của chu trình Euler rằng phải bắt đầu và kết thúc tại cùng một nút. Một đường đi Euler (trường hợp tổng quát của chu trình Euler) cũng tìm được nếu có đúng hai nút bậc lẻ. Điều này sẽ giảm một chút việc đi lại... giả sử bạn có thể đi nhờ xe về đầu kia công viên. Tuy nhiên, tại thời điểm viết, NetworkX không cung cấp thuật toán Euler Path. Mã eulerian_circuit cũng không quá tệ và có thể điều chỉnh cho trường hợp này, nhưng ở đây ta giữ mọi thứ đơn giản.

Chu trình ngây thơ

Dẫu vậy, hãy bắt đầu bằng lời giải đơn giản nhưng chưa hoàn chỉnh:

naive_euler_circuit = list(nx.eulerian_circuit(g_aug, source='b_end_east'))
Được hỗ trợ bởi

Như kỳ vọng, độ dài chu trình Euler ngây thơ bằng số cạnh trong đồ thị đã bổ sung.

print('Length of eulerian circuit: {}'.format(len(naive_euler_circuit)))
Được hỗ trợ bởi

Length of eulerian circuit: 141
Được hỗ trợ bởi

Kết quả chỉ là danh sách các bộ biểu diễn cặp nút. Lưu ý nút đầu của mỗi cặp trùng với nút thứ hai của cặp liền trước đó.

# Preview naive Euler circuit
naive_euler_circuit[0:10]
Được hỗ trợ bởi

[('b_end_east', 'g_gy2'),
 ('g_gy2', 'b_g'),
 ('b_g', 'b_w'),
 ('b_w', 'b_gy2'),
 ('b_gy2', 'w_gy2'),
 ('w_gy2', 'b_w'),
 ('b_w', 'w_rs'),
 ('w_rs', 'g_rs'),
 ('g_rs', 'b_g'),
 ('b_g', 'b_rs')]
Được hỗ trợ bởi

Chu trình đúng

Giờ hãy định nghĩa một hàm sử dụng đồ thị gốc để chỉ cho bạn dùng đường mòn nào để đi từ nút A sang nút B. Dù dài dòng về mã, logic thực ra khá đơn giản. Bạn chỉ cần biến đổi chu trình ngây thơ vốn bao gồm các cạnh không tồn tại trong đồ thị gốc thành một chu trình Euler chỉ dùng các cạnh tồn tại trong đồ thị gốc.

Bạn lặp qua từng cạnh trong chu trình Euler ngây thơ (naive_euler_circuit). Bất cứ nơi nào gặp cạnh không tồn tại trong đồ thị gốc, bạn thay nó bằng chuỗi các cạnh tạo thành đường đi ngắn nhất giữa hai nút đó dùng đồ thị gốc.

def create_eulerian_circuit(graph_augmented, graph_original, starting_node=None):
    """Create the eulerian path using only edges from the original graph."""
    euler_circuit = []
    naive_circuit = list(nx.eulerian_circuit(graph_augmented, source=starting_node))

    for edge in naive_circuit:
        edge_data = graph_augmented.get_edge_data(edge[0], edge[1])    

        if edge_data[0]['trail'] != 'augmented':
            # If `edge` exists in original graph, grab the edge attributes and add to eulerian circuit.
            edge_att = graph_original[edge[0]][edge[1]]
            euler_circuit.append((edge[0], edge[1], edge_att))
        else:
            aug_path = nx.shortest_path(graph_original, edge[0], edge[1], weight='distance')
            aug_path_pairs = list(zip(aug_path[:-1], aug_path[1:]))

            print('Filling in edges for augmented edge: {}'.format(edge))
            print('Augmenting path: {}'.format(' => '.join(aug_path)))
            print('Augmenting path pairs: {}\n'.format(aug_path_pairs))

            # If `edge` does not exist in original graph, find the shortest path between its nodes and
            #  add the edge attributes for each link in the shortest path.
            for edge_aug in aug_path_pairs:
                edge_aug_att = graph_original[edge_aug[0]][edge_aug[1]]
                euler_circuit.append((edge_aug[0], edge_aug[1], edge_aug_att))

    return euler_circuit
Được hỗ trợ bởi

Bạn lách hạn chế 3 một chút bằng cách bắt đầu chu trình Euler ở phía đông xa của công viên trên đường mòn Xanh dương (nút "b_end_east"). Khi chạy thực tế, bạn có thể đơn giản bỏ qua chỉ dẫn cuối cùng là quay lại nó.

Thêm các câu lệnh in chi tiết để diễn giải điều xảy ra khi bạn thay các cạnh không tồn tại từ đồ thị bổ sung bằng đường đi ngắn nhất dùng các cạnh thực sự tồn tại.

# Create the Eulerian circuit
euler_circuit = create_eulerian_circuit(g_aug, g, 'b_end_east')
Được hỗ trợ bởi

Filling in edges for augmented edge: ('b_end_east', 'g_gy2')
Augmenting path: b_end_east => b_y => b_o => b_gy2 => w_gy2 => g_gy2
Augmenting path pairs: [('b_end_east', 'b_y'), ('b_y', 'b_o'), ('b_o', 'b_gy2'), ('b_gy2', 'w_gy2'), ('w_gy2', 'g_gy2')]

Filling in edges for augmented edge: ('b_bw', 'rh_end_tt_1')
Augmenting path: b_bw => b_tt_1 => rh_end_tt_1
Augmenting path pairs: [('b_bw', 'b_tt_1'), ('b_tt_1', 'rh_end_tt_1')]

Filling in edges for augmented edge: ('b_tt_3', 'rt_end_north')
Augmenting path: b_tt_3 => b_tt_2 => tt_rt => v_rt => rt_end_north
Augmenting path pairs: [('b_tt_3', 'b_tt_2'), ('b_tt_2', 'tt_rt'), ('tt_rt', 'v_rt'), ('v_rt', 'rt_end_north')]

Filling in edges for augmented edge: ('rc_end_north', 'g_gy1')
Augmenting path: rc_end_north => v_rc => b_rc => g_rc => g_gy1
Augmenting path pairs: [('rc_end_north', 'v_rc'), ('v_rc', 'b_rc'), ('b_rc', 'g_rc'), ('g_rc', 'g_gy1')]

Filling in edges for augmented edge: ('y_gy1', 'rc_end_south')
Augmenting path: y_gy1 => y_rc => rc_end_south
Augmenting path pairs: [('y_gy1', 'y_rc'), ('y_rc', 'rc_end_south')]

Filling in edges for augmented edge: ('b_end_west', 'rd_end_south')
Augmenting path: b_end_west => b_v => rd_end_south
Augmenting path pairs: [('b_end_west', 'b_v'), ('b_v', 'rd_end_south')]

Filling in edges for augmented edge: ('rh_end_north', 'rd_end_north')
Augmenting path: rh_end_north => v_rh => v_rd => rd_end_north
Augmenting path pairs: [('rh_end_north', 'v_rh'), ('v_rh', 'v_rd'), ('v_rd', 'rd_end_north')]

Filling in edges for augmented edge: ('v_end_east', 'rs_end_north')
Augmenting path: v_end_east => v_rs => rs_end_north
Augmenting path pairs: [('v_end_east', 'v_rs'), ('v_rs', 'rs_end_north')]

Filling in edges for augmented edge: ('y_gy2', 'rs_end_south')
Augmenting path: y_gy2 => y_rs => rs_end_south
Augmenting path pairs: [('y_gy2', 'y_rs'), ('y_rs', 'rs_end_south')]
Được hỗ trợ bởi

Bạn thấy độ dài chu trình Euler dài hơn chu trình ngây thơ, điều này hợp lý.

print('Length of Eulerian circuit: {}'.format(len(euler_circuit)))
Được hỗ trợ bởi

Length of Eulerian circuit: 158
Được hỗ trợ bởi

Tính Lời giải CPP

Văn bản

Dưới đây là bản in lời giải ở dạng văn bản:

# Preview first 20 directions of CPP solution
for i, edge in enumerate(euler_circuit[0:20]):
    print(i, edge)
Được hỗ trợ bởi

0 ('b_end_east', 'b_y', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 1.32})
1 ('b_y', 'b_o', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.08})
2 ('b_o', 'b_gy2', {'color': 'blue', 'estimate': 1, 'trail': 'b', 'distance': 0.05})
3 ('b_gy2', 'w_gy2', {'color': 'yellowgreen', 'estimate': 1, 'trail': 'gy2', 'distance': 0.03})
4 ('w_gy2', 'g_gy2', {'color': 'yellowgreen', 'estimate': 0, 'trail': 'gy2', 'distance': 0.05})
5 ('g_gy2', 'b_g', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.45})
6 ('b_g', 'b_w', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.16})
7 ('b_w', 'b_gy2', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.41})
8 ('b_gy2', 'w_gy2', {'color': 'yellowgreen', 'estimate': 1, 'trail': 'gy2', 'distance': 0.03})
9 ('w_gy2', 'b_w', {'color': 'gray', 'estimate': 0, 'trail': 'w', 'distance': 0.42})
10 ('b_w', 'w_rs', {'color': 'gray', 'estimate': 1, 'trail': 'w', 'distance': 0.06})
11 ('w_rs', 'g_rs', {'color': 'red', 'estimate': 0, 'trail': 'rs', 'distance': 0.18})
12 ('g_rs', 'b_g', {'color': 'green', 'estimate': 1, 'trail': 'g', 'distance': 0.05})
13 ('b_g', 'b_rs', {'color': 'blue', 'estimate': 0, 'trail': 'b', 'distance': 0.07})
14 ('b_rs', 'g_rs', {'color': 'red', 'estimate': 0, 'trail': 'rs', 'distance': 0.11})
15 ('g_rs', 'g_rc', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.45})
16 ('g_rc', 'g_gy1', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.37})
17 ('g_gy1', 'g_rt', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.26})
18 ('g_rt', 'g_w', {'color': 'green', 'estimate': 0, 'trail': 'g', 'distance': 0.31})
19 ('g_w', 'o_w_1', {'color': 'gray', 'estimate': 0, 'trail': 'w', 'distance': 0.18})
Được hỗ trợ bởi

Bạn có thể nhận ra khá nhanh rằng thuật toán không quá "trung thành" với bất kỳ đường mòn cụ thể nào, nhảy từ đường này sang đường khác khá nhanh. Một phần mở rộng có thể tinh chỉnh và đưa khái niệm trung thành đường mòn vào hàm mục tiêu để biến việc chạy lộ trình này ngoài đời thực quản lý được hơn.

Thống kê

Hãy xem qua lời giải để đánh giá mức độ hợp lý.
(Không cần sa đà vào mã dài dòng này, chỉ cần xem kết quả in ra)

# Computing some stats
total_mileage_of_circuit = sum([edge[2]['distance'] for edge in euler_circuit])
total_mileage_on_orig_trail_map = sum(nx.get_edge_attributes(g, 'distance').values())
_vcn = pd.value_counts(pd.value_counts([(e[0]) for e in euler_circuit]), sort=False)
node_visits = pd.DataFrame({'n_visits': _vcn.index, 'n_nodes': _vcn.values})
_vce = pd.value_counts(pd.value_counts([sorted(e)[0] + sorted(e)[1] for e in nx.MultiDiGraph(euler_circuit).edges()]))
edge_visits = pd.DataFrame({'n_visits': _vce.index, 'n_edges': _vce.values})

# Printing stats
print('Mileage of circuit: {0:.2f}'.format(total_mileage_of_circuit))
print('Mileage on original trail map: {0:.2f}'.format(total_mileage_on_orig_trail_map))
print('Mileage retracing edges: {0:.2f}'.format(total_mileage_of_circuit-total_mileage_on_orig_trail_map))
print('Percent of mileage retraced: {0:.2f}%\n'.format((1-total_mileage_of_circuit/total_mileage_on_orig_trail_map)*-100))

print('Number of edges in circuit: {}'.format(len(euler_circuit)))
print('Number of edges in original graph: {}'.format(len(g.edges())))
print('Number of nodes in original graph: {}\n'.format(len(g.nodes())))

print('Number of edges traversed more than once: {}\n'.format(len(euler_circuit)-len(g.edges())))  

print('Number of times visiting each node:')
print(node_visits.to_string(index=False))

print('\nNumber of times visiting each edge:')
print(edge_visits.to_string(index=False))
Được hỗ trợ bởi

Mileage of circuit: 33.59
Mileage on original trail map: 25.76
Mileage retracing edges: 7.83
Percent of mileage retraced: 30.40%

Number of edges in circuit: 158
Number of edges in original graph: 123
Number of nodes in original graph: 77

Number of edges traversed more than once: 35

Number of times visiting each node:
n_nodes  n_visits
     18         1
     38         2
     20         3
      1         4

Number of times visiting each edge:
n_edges  n_visits
     88         1
     35         2
Được hỗ trợ bởi

Trực quan hóa Lời giải CPP

Dù NetworkX cũng cung cấp chức năng để trực quan hóa đồ thị, họ khá khiêm tốn ở mảng này:

NetworkX cung cấp chức năng cơ bản để trực quan hóa đồ thị, nhưng mục tiêu chính là hỗ trợ phân tích đồ thị hơn là trực quan hóa. Trong tương lai, chức năng trực quan hóa có thể bị loại bỏ khỏi NetworkX hoặc chỉ có dưới dạng gói bổ sung.

Trực quan hóa đồ thị một cách bài bản là khó, và chúng tôi khuyến nghị mọi người dùng các công cụ chuyên cho tác vụ đó. Ví dụ tiêu biểu gồm Cytoscape, Gephi, Graphviz và, cho dàn trang LaTeX, PGF/TikZ.

Dù vậy, chức năng vẽ tích hợp của NetworkX với matplotlib đủ mạnh để xem lướt và khám phá trực quan các đồ thị cơ bản, nên trong hướng dẫn này ta vẫn dùng draw của NetworkX.

Tôi dùng graphviz và ngôn ngữ mô tả đồ thị dot để trực quan hóa lời giải trong gói Python postman_problems của mình. Dù cần chút công sức để chuyển cấu trúc đồ thị NetworkX sang đồ thị dot, điều đó mở khóa chất lượng và khả năng kiểm soát trực quan tốt hơn.

Tạo Đồ thị CPP

Bước đầu là chuyển danh sách các cạnh cần đi trong chu trình Euler thành một danh sách cạnh với các thuộc tính thân thiện cho việc vẽ.

create_cpp_edgelist Tạo danh sách cạnh với vài thuộc tính bổ sung mà bạn sẽ dùng khi vẽ:

sequence: ghi lại thứ tự khi ta đi qua mỗi cạnh.
visits: đơn giản là số lần ta đi qua một cạnh cụ thể.

def create_cpp_edgelist(euler_circuit):
    """
    Create the edgelist without parallel edge for the visualization
    Combine duplicate edges and keep track of their sequence and # of walks
    Parameters:
        euler_circuit: list[tuple] from create_eulerian_circuit
    """
    cpp_edgelist = {}

    for i, e in enumerate(euler_circuit):
        edge = frozenset([e[0], e[1]])

        if edge in cpp_edgelist:
            cpp_edgelist[edge][2]['sequence'] += ', ' + str(i)
            cpp_edgelist[edge][2]['visits'] += 1

        else:
            cpp_edgelist[edge] = e
            cpp_edgelist[edge][2]['sequence'] = str(i)
            cpp_edgelist[edge][2]['visits'] = 1

    return list(cpp_edgelist.values())
Được hỗ trợ bởi

Hãy tạo danh sách cạnh CPP:

cpp_edgelist = create_cpp_edgelist(euler_circuit)
Được hỗ trợ bởi

Đúng như kỳ vọng, danh sách cạnh của bạn có số cạnh bằng với đồ thị gốc.

print('Number of edges in CPP edge list: {}'.format(len(cpp_edgelist)))
Được hỗ trợ bởi

Number of edges in CPP edge list: 123
Được hỗ trợ bởi

Danh sách cạnh CPP trông tương tự euler_circuit, chỉ thêm vài thuộc tính.

# Preview CPP plot-friendly edge list
cpp_edgelist[0:3]
Được hỗ trợ bởi

[('rh_end_tt_4',
  'nature_end_west',
  {'color': 'black',
   'distance': 0.2,
   'estimate': 0,
   'sequence': '73',
   'trail': 'tt',
   'visits': 1}),
 ('rd_end_south',
  'b_rd',
  {'color': 'red',
   'distance': 0.13,
   'estimate': 0,
   'sequence': '95',
   'trail': 'rd',
   'visits': 1}),
 ('w_gy1',
  'w_rc',
  {'color': 'gray',
   'distance': 0.33,
   'estimate': 0,
   'sequence': '151',
   'trail': 'w',
   'visits': 1})]
Được hỗ trợ bởi

Giờ hãy tạo đồ thị:

# Create CPP solution graph
g_cpp = nx.Graph(cpp_edgelist)
Được hỗ trợ bởi

Trực quan hóa 1: Đi lại dấu chân

Tại đây bạn minh họa cạnh nào được đi một lần (xám) và hơn một lần (xanh). Đây là phiên bản "đúng" của trực quan hóa ở 2.4 mà đã hiển thị các kết nối ngây thơ (đường chim bay) giữa các cặp nút lẻ (đỏ). Ở đây điều đó được chỉnh lại bằng cách bám theo đường đi ngắn nhất qua các cạnh thực sự tồn tại cho mỗi cặp nút bậc lẻ.

Nếu tối ưu hóa tốt, các đường xanh này phải là khoảng cách ít nhất có thể. Cụ thể, khoảng cách tối thiểu cần để tạo một matching của các nút bậc lẻ.

plt.figure(figsize=(14, 10))

visit_colors = {1:'lightgray', 2:'blue'}
edge_colors = [visit_colors[e[2]['visits']] for e in g_cpp.edges(data=True)]
node_colors = ['red'  if node in nodes_odd_degree else 'lightgray' for node in g_cpp.nodes()]

nx.draw_networkx(g_cpp, pos=node_positions, node_size=20, node_color=node_colors, edge_color=edge_colors, with_labels=False)
plt.axis('off')
plt.show()
Được hỗ trợ bởi

Trực quan hóa 2: Thứ tự Lời giải CPP

Tại đây bạn vẽ đồ thị gốc (bản đồ đường mòn) kèm chú thích số thứ tự mà ta đi các đường mòn theo lời giải CPP. Nhiều số cho biết các đường mòn phải quay lại.

Bạn bắt đầu trên đường mòn xanh dương ở góc dưới bên phải (hướng đi thứ 0 và thứ 157).

plt.figure(figsize=(14, 10))

edge_colors = [e[2]['color'] for e in g_cpp.edges(data=True)]
nx.draw_networkx(g_cpp, pos=node_positions, node_size=10, node_color='black', edge_color=edge_colors, with_labels=False, alpha=0.5)

bbox = {'ec':[1,1,1,0], 'fc':[1,1,1,0]}  # hack to label edges over line (rather than breaking up line)
edge_labels = nx.get_edge_attributes(g_cpp, 'sequence')
nx.draw_networkx_edge_labels(g_cpp, pos=node_positions, edge_labels=edge_labels, bbox=bbox, font_size=6)

plt.axis('off')
plt.show()
Được hỗ trợ bởi

Trực quan hóa 3: Phim

Ảnh động bên dưới lần theo chu trình Euler từ đầu đến cuối. Các cạnh được tô đen ở lần đi đầu tiên và đỏ ở lần đi thứ hai.

Lưu ý ảnh gif này không thể hiện trọn vẹn các cạnh chồng lên nhau hoặc quá nhỏ để hiển thị rõ. Một thư viện trực quan hóa mạnh hơn như graphviz có thể xử lý bằng cách vẽ spline thay vì đường thẳng giữa các nút.

Mã tạo ảnh động được đưa ra dưới đây để tham khảo.

Đầu tiên tạo một ảnh PNG cho mỗi chỉ dẫn (cạnh được đi) từ lời giải CPP.

visit_colors = {1:'black', 2:'red'}
edge_cnter = {}
g_i_edge_colors = []
for i, e in enumerate(euler_circuit, start=1):

    edge = frozenset([e[0], e[1]])
    if edge in edge_cnter:
        edge_cnter[edge] += 1
    else:
        edge_cnter[edge] = 1

    # Full graph (faded in background)
    nx.draw_networkx(g_cpp, pos=node_positions, node_size=6, node_color='gray', with_labels=False, alpha=0.07)

    # Edges walked as of iteration i
    euler_circuit_i = copy.deepcopy(euler_circuit[0:i])
    for i in range(len(euler_circuit_i)):
        edge_i = frozenset([euler_circuit_i[i][0], euler_circuit_i[i][1]])
        euler_circuit_i[i][2]['visits_i'] = edge_cnter[edge_i]
    g_i = nx.Graph(euler_circuit_i)
    g_i_edge_colors = [visit_colors[e[2]['visits_i']] for e in g_i.edges(data=True)]

    nx.draw_networkx_nodes(g_i, pos=node_positions, node_size=6, alpha=0.6, node_color='lightgray', with_labels=False, linewidths=0.1)
    nx.draw_networkx_edges(g_i, pos=node_positions, edge_color=g_i_edge_colors, alpha=0.8)

    plt.axis('off')
    plt.savefig('fig/png/img{}.png'.format(i), dpi=120, bbox_inches='tight')
    plt.close()
Được hỗ trợ bởi

Sau đó ghép các ảnh PNG lại để tạo ảnh gif nhỏ xinh bên trên.

Đầu tiên các PNG được sắp xếp theo thứ tự từ 0 đến 157. Sau đó ghép lại bằng imageio với 3 khung hình mỗi giây để tạo gif.

import glob
import numpy as np
import imageio
import os

def make_circuit_video(image_path, movie_filename, fps=5):
    # sorting filenames in order
    filenames = glob.glob(image_path + 'img*.png')
    filenames_sort_indices = np.argsort([int(os.path.basename(filename).split('.')[0][3:]) for filename in filenames])
    filenames = [filenames[i] for i in filenames_sort_indices]

    # make movie
    with imageio.get_writer(movie_filename, mode='I', fps=fps) as writer:
        for filename in filenames:
            image = imageio.imread(filename)
            writer.append_data(image)

make_circuit_video('fig/png/', 'fig/gif/cpp_route_animation.gif', fps=3)Được hỗ trợ bởi

Các bước tiếp theo

Chúc mừng, bạn đã hoàn thành hướng dẫn giải Bài toán Người đưa thư Trung Quốc trong Python. Bạn đã đi qua khá nhiều nội dung trong hướng dẫn này (chính xác là 33,6 dặm đường mòn). Để đào sâu hơn các nền tảng mạng, bạn có thể quan tâm đến khóa Network Analysis in Python của Datacamp, cung cấp một cách trình bày đầy đủ hơn về các khái niệm cốt lõi.

Đừng ngần ngại xem tài liệu NetworkX để biết thêm về cách tạo, thao tác và duyệt qua các mạng phức tạp này. Tài liệu rất toàn diện với số lượng ví dụ tốt và một loạt hướng dẫn.

Nếu bạn muốn giải CPP trên đồ thị của chính mình, tôi đã đóng gói chức năng trong hướng dẫn này vào gói Python postman_problems trên Github. Bạn cũng có thể ghép các khối mã trong hướng dẫn này với danh sách cạnh và nút khác, nhưng gói postman_problems có lẽ sẽ giúp bạn đến đích nhanh và gọn hơn.

Một ngày nào đó tôi dự định triển khai các phần mở rộng của CPP (Bài toán Người đưa thư Nông thôn và Người đưa thư Gió) ở đây. Tôi cũng ấp ủ viết về các phần mở rộng này và trải nghiệm thử lộ trình trên đường mòn trên blog của mình tại đây. Một ứng dụng khác tôi dự định khám phá và viết về là tích hợp tọa độ vĩ/kinh độ để phát triển (hoặc dùng) cơ chế gửi chỉ dẫn từng chặng tới đồng hồ Garmin của tôi.

Và dĩ nhiên còn một bước tiếp theo nữa: ra ngoài và chạy thử lộ trình!

Nếu bạn muốn học thêm về Mạng trong Python, hãy xem các khóa học của DataCamp sau:

Introduction to Network Analysis in Python

Intermediate Network Analysis in Python

Tài liệu tham khảo

1: Edmonds, Jack (1965). "Paths, trees, and flowers". Canad. J. Math. 17: 449–467.
2: Galil, Z. (1986). "Efficient algorithms for finding maximum matching in graphs". ACM Computing Surveys. Vol. 18, No. 1: 23-38.

Chủ đề

Python Khoa học Dữ liệu Trực quan hóa Dữ liệu