数学建模-常见算法（3）
-
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 |
-
动态规划（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]) |
这些算法都有一定的难度，需要深入理解才能正确实现。在数学建模应用中，这些算法也有广泛的应用场景。