第五章 图论和网格优化
最短路径
最短路径算法是一类用于找到图或网络中两个节点之间最短路径的算法。在图论中，最短路径指的是两个节点之间经过的边权重之和最小的路径。
最短路径算法有许多著名的算法实现，接下来会一一讲述。
G = np.array([[0, 1, 12, float('inf'), float('inf'), float('inf')],
[float('inf'), 0, 9, 3, float('inf'), float('inf')],
[float('inf'), float('inf'), 0,
float('inf'), 5, float('inf')],
[float('inf'), float('inf'), 4, 0, 13, 15],
[float('inf'), float('inf'), float(
'inf'), float('inf'), 0, 4],
[float('inf'), float('inf'), float('inf'), float('inf'), float('inf'), 0]])
有向图无负权示例图
Dijkstra算法
迪杰斯特拉算法主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。迪杰斯特拉算法采用的是贪心策略，将Graph中的节点集分为最短路径计算完成的节点集S和未计算完成的节点集T，每次将从T中挑选V0->Vt最小的节点Vt加入S，并更新V0经由Vt到T中剩余节点的更短距离，直到T中的节点全部加入S中，迪杰斯特拉算法只支持非负权图，它计算的是单源最短路径，即单个源点到剩余节点的最短路径。
def Dijkstra(G, v0):
"""使用Dijkstra算法，给定一个有权图G和起点v0，求v0到图G中任意点的最短路径
Parameters
----------
G : np.array
有权图G
v0 : int
起点v0
"""
T = list(range(len(G))) # T为未求出最短路径的顶点集合
S = [] # S为已求出最短路径的顶点集合
T.remove(v0) # 从T中移除起点v0
S.append(v0) # 将起点v0加入S
D = G[v0] # D[i]表示v0到i的最短路径长度
P = [v0] * len(G) # P[i]表示v0到i的最短路径上i的前一个顶点
while len(T) != 0:
min = np.inf
for i in T:
if D[i] < min:
min = D[i]
u = i
T.remove(u)
S.append(u)
for i in T:
if D[u] + G[u][i] < D[i]:
D[i] = D[u] + G[u][i]
P[i] = u
return D, P
Floyd算法
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。
def Floyd(graph, n, start, end):
"""使用Floyd算法，给定一个有权图G，求图G中任意两点之间的最短路径
Parameters
----------
G : np.array
有权图G
v0 : int
起点v0
return
------
dis : np.array
D[i][j]表示i到j的最短路径长度
path : np.array
P[i][j]表示i到j的最短路径
"""
graph_ = graph.copy()
path_ = np.array([[None for i in range(n)] for j in range(n)])
for i in range(n):
for j in range(n):
if graph_[i][j] == float('inf'):
path_[i][j] = None
else:
path_[i][j] = i
for k in range(n):
for i in range(n):
for j in range(n):
if graph_[i][j] > graph_[i][k] + graph_[k][j]:
graph_[i][j] = graph_[i][k] + graph_[k][j]
path_[i][j] = path_[k][j]
dis = graph_[start][end]
path = []
while start != end:
path.append(end)
end = path_[start][end]
path.append(start)
path.reverse()
return dis, path
Bellman-Ford算法
BellmanFord算法功能：给定一个加权连通图，选取一个顶点，称为起点，求取起点到其它所有顶点之间的最短距离，其显著特点是可以求取含负权图的单源最短路径，可以来判断该图中是否有负权回路或者存在最短路径的点。
def Bellman_Ford(G, start, end):
"""Bellman-Ford算法, 用于计算单源最短路径, 适用于有向图, 可以处理负权边, 但不能处理负权环。
Parameters
----------
G : np.array
图的邻接矩阵, G[i][j]表示从i到j的权值, 无边用np.inf表示，可以为负数。
start : int
源点。
end : int
终点。
return
------
dis : np.array
源点到终点的最短距离。
path : np.array
源点到终点的最短路径。
"""
# 初始化
dis = np.array([np.inf] * len(G))
dis[start] = 0
path_ = np.array([start] * len(G))
# 迭代
for i in range(len(G) - 1):
for j in range(len(G)):
for k in range(len(G)):
if dis[j] > dis[k] + G[k][j]:
dis[j] = dis[k] + G[k][j]
path_[j] = k
# 检测负权环
for i in range(len(G)):
for j in range(len(G)):
if dis[j] > dis[i] + G[i][j]:
print('存在负权环')
return
path = []
path.append(end)
while path_[end] != start:
path.append(path_[end])
end = path_[end]
path.append(start)
path.reverse()
return dis[end], path
G = np.array([[0, 1, 12, np.inf, np.inf, np.inf],
[np.inf, 0, 9, -3, np.inf, np.inf],
[np.inf, np.inf, 0, np.inf, 5, np.inf],
[np.inf, np.inf, 4, 0, 13, -15],
[np.inf, np.inf, np.inf, np.inf, 0, -4],
[np.inf, np.inf, np.inf, np.inf, np.inf, 0]])
带负权的有向图
G = np.array([[0, 1, np.inf, np.inf, np.inf, np.inf],
[np.inf, 0, 9, -3, np.inf, np.inf],
[-12, np.inf, 0, np.inf, 5, np.inf],
[np.inf, np.inf, 4, 0, 13, -15],
[np.inf, np.inf, np.inf, np.inf, 0, -4],
[np.inf, np.inf, np.inf, np.inf, np.inf, 0]])
含有负权环
网络的最大流问题
什么是最大流
如图是一个有向图，其中s为起点，t为终点，每条边代表的数字是最大流量。也就是说把一条条边比作运水的管道，标注为4的就是这个管道的最大流量为4.而求解最大流问题，就是要求解从s到t的最大流量。
我们将实际流量用红色进行标注，很容易判断出当前网络中的流量为5。
阻塞流是一种特殊情况，它能将图中的管道都堵住，但却不是最大流。例如右图的情况。你不能再添加更多流量从起点到终点。最大流也是一种阻塞流。
以下是寻找阻塞流的简单算法：
- 首先生成一个全为空闲流量的图，此时空闲流量等于一开始的容量。
- 一直循环，直到没有从起点到终点的简单路径：
- 找到一条从起点到终点简单路径；
- 找到该路径中空闲量最小的哪一条边，空闲量记为x；
- 把简单路径中的所有边减去这个x，意味着这条路径的空闲量因为流过了x的水减少了；
- 最后将容量减去空闲量，就能得出现在网络中阻塞流的流量了。
请注意，这种算法只能找出阻塞流，不一定能够找出最大流。
Ford-Fulkerson算法
L.R.Ford and D.R.Fulkerson. Maximal flow through a network. Canadian Journal ofMathematics, 8:399-404,1956.
该算法能够求解出最大流。
该算法与之前的算法类似，只不过添加了一步：
- 首先生成一个全为空闲流量的图，此时空闲流量等于一开始的容量。
- 一直循环，直到没有从起点到终点的简单路径：
- 找到一条从起点到终点简单路径；
- 找到该路径中空闲量最小的哪一条边，空闲量记为x；
- 把简单路径中的所有边减去这个x，意味着这条路径的空闲量因为流过了x的水减少了；
- 生成一条路径与该简单路径相反的路径，每条边的权重是x；
- 将我们生成的所有反向路径删掉。
- 最后将容量减去空闲量，就能得出现在网络中阻塞流的流量了。
import numpy as np
# 最大流算法
def BFS(C, F, s, t):
"""广度优先搜索，寻找简单路径
Parameters
----------
C : list
邻接矩阵
F : list
流量矩阵
s : int
起点
t : int
终点
Returns
-------
list
简单路径
"""
queue = [s]
paths = {s: []}
if s == t:
return paths[s]
while queue:
u = queue.pop(0)
for v in range(len(C)):
if (C[u][v] - F[u][v] > 0) and v not in paths:
paths[v] = paths[u] + [(u, v)]
if v == t:
return paths[v]
queue.append(v)
return None
def FordFulkerson(C, s, t):
"""Ford-Fulkerson算法，寻找最大流。
Parameters
----------
C : list
邻接矩阵
s : int
起点
t : int
终点
Returns
-------
int
最大流
"""
n = len(C) # C是邻接矩阵
F = [[0] * n for i in range(n)] # F是流量矩阵
path = BFS(C, F, s, t)
while path is not None:
flow = min(C[u][v] - F[u][v] for u, v in path)
for u, v in path:
F[u][v] += flow # 正向流量增加
F[v][u] -= flow # 反向流量增加
path = BFS(C, F, s, t)
return sum(F[s][i] for i in range(n))
# 例子
if __name__ == '__main__':
C = [[0, 4, 2, 0, 0, 0],
[0, 0, 1, 2, 4, 0],
[0, 0, 0, 0, 2, 0],
[0, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 0, 0]]
print(FordFulkerson(C, 0, 5)) # 5
Dinic算法
13-4: Dinic’s Algorithm 寻找网络最大流_哔哩哔哩_bilibili
Yefim Dinitz. Algorithm for solution of a problem of maximum flow in a network with power estimation. Proceedings of the USSR Academy of Sciences, 11:1277-1280,1970.
该算法比Ford-Fulkerson算法更快。
最小费用最大流
最小费用流
假设我们给定的图中，每一条管道（边）不仅有容量，还有途径该管道的费用（权值）。现在我们想要找到一条路径连接起点和终点，应该如何寻找使得总花费最小？
很容易想到的一种方法是，我们使用最短路径算法找到连接起点和终点的最短路径。这里我们使用Bellman-Ford算法，因为该算法能够处理负权边，找到的最短路径就是我们要找的最短费用流。
最小费用最大流
如果我们想要找到花费最小的最大流，需要结合之前学习的最短路径算法和最大流算法，具体做法就是在最大流算法寻找简单路径时，将简单路径替换成最短路径。这样我们最终寻找的是最小费用最大流。注意，增加反向道路时，反向道路的权值为正向道路花费的负数，这样就体现了我们Bellman-Ford算法的好处。
# 定义边结构
class Edge:
"""Edge类的初始化函数，用于初始化Edge类的各个属性。
Parameters
----------
u : int
边的起点
v : int
边的终点
c : int
边的容量
w : int
边的花费
"""
def __init__(self, u, v, c, w):
self.u = u
self.v = v
self.c = c
self.w = w
if __name__ == '__main__':
# 例子
n = 6 # 顶点数
m = 8 # 边数
s = 0 # 源点
t = 5 # 汇点
# 边集
edges = []
edges.append(Edge(0, 1, 4, 3))
edges.append(Edge(0, 2, 2, 6))
edges.append(Edge(1, 2, 1, 10))
edges.append(Edge(1, 3, 2, 7))
edges.append(Edge(1, 4, 4, 2))
edges.append(Edge(2, 4, 2, 8))
edges.append(Edge(3, 5, 3, 7))
edges.append(Edge(4, 5, 3, 6))
黑色为容量，蓝色为花费
最小生成树
在无向图中，生成树代表着的是能够联通所有节点所用的不成环的树。根据树的定义，当图中存在n个顶点的时候，必定存在n-1边组成一棵树。而最小生成树代表着总权值最小的一颗生成树。
class Edge:
"""生成一条边，包含起点，终点，权重，用于构建图。
Parameters
----------
start : int
起点
end : int
终点
weight : int
权重
"""
def __init__(self, start, end, weight):
self.start = start
self.end = end
self.weight = weight
if __name__ == "__main__":
edges = []
edges.append(Edge(0, 1, 4))
edges.append(Edge(0, 7, 8))
edges.append(Edge(1, 2, 8))
edges.append(Edge(1, 7, 11))
edges.append(Edge(2, 3, 7))
edges.append(Edge(2, 8, 2))
edges.append(Edge(2, 5, 4))
edges.append(Edge(3, 4, 9))
edges.append(Edge(3, 5, 14))
edges.append(Edge(4, 5, 10))
edges.append(Edge(5, 6, 2))
edges.append(Edge(6, 7, 1))
edges.append(Edge(6, 8, 6))
edges.append(Edge(7, 8, 7))
示例图
示例图的最小生成树
Kruskal算法
kruskal算法先对每条边的权重进行排列。然后从小到大依次将边加入到去掉所有边的图中。如果加入的这个边连成了环，那么就删除这条边。直到有n-1条边加入了图中。这时候生成的树就是我们所得到的最小生成树。
def kruskal(edges):
"""最小生成树算法，使用kruskal算法。
Parameters
----------
edges : list
边的集合，每个元素是一个Edge对象
Returns
-------
list
最小生成树的边集合
"""
edges.sort(key=lambda x: x.weight)
parent = [i for i in range(len(edges))]
result = []
for edge in edges:
if find(parent, edge.start) != find(parent, edge.end):
union(parent, edge.start, edge.end)
result.append(edge)
return result
def find(parent, index):
"""查找index的根节点
Parameters
----------
parent : list
parent[i]表示节点i的父节点
index : int
要查找的节点
Returns
-------
int
index的根节点
"""
if parent[index] != index:
parent[index] = find(parent, parent[index])
return parent[index]
def union(parent, index1, index2):
"""合并index1和index2所在的集合
Parameters
----------
parent : list
parent[i]表示节点i的父节点
index1 : int
节点1
index2 : int
节点2
"""
parent[find(parent, index1)] = find(parent, index2)
Prim算法
Prim算法与Kruskal算法不同的是，它将主要的操作对象从边移到了顶点。Prim先选中一个顶点加入一个已查找集合，找到与它连接最小权值的边，将对应的边的另一个顶点加入集合，再次寻找这个集合中相邻的最小权值的边，直到将所有顶点加入集合，算法结束。
def prim(edges):
"""Prim算法，返回最小生成树的边集合。
Parameters
----------
edges : list
边集合
Returns
-------
list
最小生成树的边集合
"""
remain = set()
for edge in edges:
remain.add(edge.start)
remain.add(edge.end)
# 用于存储最小生成树的边集合
result = []
# 用于存储已经加入最小生成树的顶点
added = [0]
remain.remove(0)
# 用于存储未加入最小生成树的顶点
while len(remain) > 0:
# 用于存储权重最小的边
min_edge = None
for edge in edges:
if (edge.start in added and edge.end in remain) or (edge.end in added and edge.start in remain):
if min_edge is None:
min_edge = edge
elif min_edge.weight > edge.weight:
min_edge = edge
result.append(min_edge)
if min_edge.start in added:
added.append(min_edge.end)
remain.remove(min_edge.end)
else:
added.append(min_edge.start)
remain.remove(min_edge.start)
return result
旅行商问题（TSP）
旅行商问题通俗而言它是指对于给定的一系列城市和每对城市之间的距离，找到访问每一座城市仅一次并回到起始城市的最短回路。
该问题的求解时间复杂度不是多项式时间，比较复杂。这种类型的题目与最小生成树有异曲同工之妙，但是这里要求的路径必须是一条回路，比最小生成树更加复杂。
旅行商问题可以用动态规划的思想进行求解。下面用一道例题来解释。
动态规划解法
class Edge:
def __init__(self, u, v, w):
"""边类，用于表示两个城市之间的距离，u和v为城市编号，w为距离。
Parameters
----------
u : int
城市编号
v : int
城市编号
w : int
距离
"""
self.u = u
self.v = v
self.w = w
class Graph:
def __init__(self, n):
"""图类，用于表示城市之间的距离。
Parameters
----------
n : int
城市数量
"""
self.n = n
self.edges = []
def add_edge(self, u, v, w):
"""添加边,为无向图，所以添加两次。
Parameters
----------
u : int
城市编号
v : int
城市编号
w : int
距离
"""
self.edges.append(Edge(u, v, w))
self.edges.append(Edge(v, u, w))
def get_edge(self, u, v):
"""获取边长。
Parameters
----------
u : int
城市编号
v : int
城市编号
Returns
-------
Edge
边
"""
for edge in self.edges:
if edge.u == u and edge.v == v:
return edge.w
return float('inf')
if __name__ == '__main__':
g = Graph(5)
g.add_edge(0, 1, 3)
g.add_edge(0, 3, 8)
g.add_edge(0, 4, 9)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 10)
g.add_edge(1, 4, 5)
g.add_edge(2, 3, 4)
g.add_edge(2, 4, 3)
g.add_edge(3, 4, 20)
示例
答案
假设d(i,V)表示总顶点i出发经过V(点集)中的各个顶点，每个顶点只经过一次，最后回到出发点s的最短路径长度。
分类讨论：
-
当V为空，d(i,V)=0，表示不需要出发就直接从原点回到了原点。
-
当V不为空，变成了对子问题的最优求解：
d(i,V)=\min\{C_{ik}+d(k,V-(k))\}
这时我们已经将边界条件和状态转移方程求出来了，下面来分析求解路径。已d(0,\{1,2\})为例：
在V集的所有节点都要从边界条件进行求解，所有求解结果加入到V集中等待下一次求解。
分析数据结构dp表，设dp[i][j]中为d(i,V)中的i，j为d(i,V)中的j，j从空集开始依次打表，知道我们求解出最终结果。
def TSP(Graph, s):
"""旅行商问题，使用动态规划的方法，时间复杂度为O(n^2*2^n)。
Parameters
----------
Graph : Graph
图
s : int
起始城市编号
Returns
-------
int
最短路径长度
"""
n = Graph.n
# dp[i][j]表示从城市i出发，经过集合j中的城市，最后回到起点的最短路径长度
dp = [[float('inf')] * (1 << n) for _ in range(n)]
# 初始化，从城市i出发，经过集合j中的城市，最后回到起点的最短路径长度为从城市i到城市j的距离
for i in range(n):
dp[i][1 << i] = Graph.edges[i].w
# 遍历所有集合
for j in range(1, 1 << n):
# 遍历所有城市
for i in range(n):
# 如果城市i在集合j中
if j & (1 << i):
# 遍历所有城市
for k in range(n):
# 如果城市k在集合j中
if j & (1 << k):
# 更新dp[i][j]
dp[i][j] = min(
dp[i][j], dp[k][j - (1 << i)] + Graph.get_edge(k, i))
# 遍历所有城市，找到最短路径
return dp[s][(1 << n) - 1]
遗传算法
对于多数据的处理，动态规划算法的时间复杂度过高，这时我们可以采用高级算法，例如遗传算法。
https://github.com/Agwave/Artificial-Intelligence-Course-Algorithm/blob/master/cities.txt
这个项目仅需提供不同城市的坐标，根据欧式几何就能求解出TSP问题。
图着色问题
来看下面一个问题：
给定无向连通图G=(V,E)和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。
在这里引出一个定理：四色定理，每个平面地图都可以只用四种颜色来染色，而且没有两个邻接的区域颜色相同。放在无向连通图就是只需四种颜色可以完成边相邻的节点颜色不同。
回溯法
# 图的着色问题，回溯法
def coloring(G, k, vcolor):
"""图的着色问题，回溯法
Parameters
----------
G : list
图的邻接矩阵
k : int
当前处理的节点
vcolor : list
存放当前节点的颜色
Returns
-------
list or bool
返回可行解，如果没有解则返回False
"""
n = len(G)
if k == n:
return vcolor
else:
for color in range(1, m + 1):
if is_ok(G, k, vcolor, color):
vcolor[k] = color
result = coloring(G, k + 1, vcolor)
if result:
return result
else:
vcolor[k] = 0
return False
def is_ok(G, k, vcolor, color):
"""判断当前节点是否可以着色
Parameters
----------
G : list
图的邻接矩阵
k : int
当前处理的节点
vcolor : list
存放当前节点的颜色
color : int
当前节点的颜色
Returns
-------
bool
是否可以着色
"""
for i in range(k):
if G[i][k] == 1 and vcolor[i] == color:
return False
return True
if __name__ == '__main__':
G = [[0, 1, 1, 1, 0, 0],
[1, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 0],
[0, 1, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 0]]
m = 3
vcolor = [0] * len(G)
if coloring(G, 0, vcolor):
print(vcolor)
else:
print('No solution.')
评论区