数学建模-常见算法（3）

1. KMP算法（Knuth-Morris-Pratt算法）

KMP算法是一种用于字符串匹配的算法，它的时间复杂度为O(m+n)。该算法的核心思想是在匹配失败时，利用已经匹配的信息，减少下一次匹配的起始位置。

def kmp(text, pattern): 
n = len(text) 
m = len(pattern) 
lps = [0] * m 
j = 0 
compute_lps(pattern, m, lps) 
i = 0 
while i < n: 
if pattern[j] == text[i]: 
i += 1 
j += 1 
if j == m: 
print("Found pattern at index " + str(i-j)) 
j = lps[j-1] 
elif i < n and pattern[j] != text[i]: 
if j != 0: 
j = lps[j-1] 
else: 
i += 1 def compute_lps(pattern, m, lps): 
length = 0 
lps[0] = 0 
i = 1 
while i < m: 
if pattern[i] == pattern[length]: 
length += 1 
lps[i] = length 
i += 1 
else: 
if length != 0: 
length = lps[length-1] 
else: 
lps[i] = 0 
i += 1

运行示例：

	text = "ABABDABACDABABCABAB"
	pattern = "ABABCABAB"
	kmp(text, pattern) # Found pattern at index 10

1. 动态规划（Dynamic Programming）

动态规划是一种用于解决复杂问题的方法，它将问题分解为更小的子问题，并存储这些子问题的解决方案，以便在需要时可以重复使用。动态规划通常用于最优化问题，如最短路径、最长公共子序列和背包问题等。

def knapsack(weights, values, W): 
n = len(weights) 
dp = [[0 for _ in range(W+1)] for _ in range(n+1)] 
for i in range(1, n+1): 
for w in range(1, W+1): 
if weights[i-1] <= w: 
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1]) 
else: 
dp[i][w] = dp[i-1][w] 
return dp[n][W]

运行示例：

	weights = [2, 3, 4, 5]
	values = [3, 4, 5, 6]
	W = 5
	print(knapsack(weights, values, W)) # Output: 7

3.拓扑排序（Topological Sort）

拓扑排序是一种用于有向无环图（DAG）的排序算法，它按照一定的顺序访问DAG的顶点，使得对于任何一条有向边（u, v），u都出现在v之前。拓扑排序在计算机科学中有许多应用，如任务调度和代码编译等。

from collections import deque def topological_sort(graph): 
in_degree = {u: 0 for u in graph} # 初始化所有顶点的入度为0 
for u in graph: 
for v in graph[u]: 
in_degree[v] += 1 # 计算每个顶点的入度 
queue = deque([u for u in graph if in_degree[u] == 0]) # 将入度为0的顶点加入队列 
result = [] 
while queue: 
u = queue.popleft() # 从队列中取出一个顶点 
result.append(u) 
for v in graph[u]: # 减少v的入度 
in_degree[v] -= 1 
if in_degree[v] == 0: # 将入度为0的顶点加入队列 
queue.append(v) 
if len(result) == len(graph): # 如果所有顶点都已被访问，则返回结果，否则说明图中存在环 
return result 
else: 
return []

运行示例：

	graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['E'], 'D': [], 'E': []}
	print(topological_sort(graph)) # Output: ['A', 'B', 'C', 'D', 'E']

4.最短路径算法（Dijkstra算法）

Dijkstra算法是一种用于解决带权重图的最短路径问题的算法。它能够找到从起点到终点的最短路径，其中路径可以经过多个节点。

def dijkstra(graph, start): 
n = len(graph) 
dist = [float('inf')] * n 
dist[start] = 0 
prev = [None] * n 
visited = [False] * n 
queue = [(0, start)] 
while queue: 
d, u = heapq.heappop(queue) 
if visited[u]: 
continue 
visited[u] = True 
for v, w in graph[u]: 
if not visited[v] and dist[u] + w < dist[v]: 
dist[v] = dist[u] + w 
prev[v] = u 
heapq.heappush(queue, (dist[v], v)) 
return dist, prev

运行示例：

	graph = [([(1, 9), (2, 6)], [(0, 5)]), ([(2, 4), (3, 5), (4, 2)], [(1, 8)]), ([(3, 1), (4, 2)], [(2, 3)]), ([(0, 1), (2, 5)], [(1, 10), (3, 1)])
	start = 0
	print(dijkstra(graph, start)) # Output: ([0, 5, 8, 11], [0, 1, 2, 3])

这些算法都有一定的难度，需要深入理解才能正确实现。在数学建模应用中，这些算法也有广泛的应用场景。