動態規劃和貪婪演算法是解決最佳化問題的利器，但應用場景和解題思路各有不同。貪婪演算法追求區域性最優解，適用於像活動選擇這類別可以逐步分解的問題。而動態規劃則著眼於全域性最優，透過記錄子問題的解避免重複計算，適合處理旅行商問題這類別需要遍歷所有可能性的情況。理解兩者差異並選擇合適的演算法對於提升程式效率至關重要，也影響著最終解的品質。
動態規劃與貪婪演算法的高階應用
在解決複雜問題時，動態規劃和貪婪演算法是兩種強大的工具。本文將探討這兩種演算法的高階技巧和實際應用，並透過具體的程式碼範例來說明其原理和實作方法。
貪婪演算法的原理與應用
貪婪演算法透過在每個步驟中選擇當下最佳的解決方案來解決問題。它的優勢在於簡單高效，但在某些情況下可能無法得到全域性最優解。
活動選擇問題
考慮一個活動選擇問題，我們需要從一組活動中選擇最多的不重疊活動。貪婪演算法的解決方案如下：
def activity_selection(activities):
activities.sort(key=lambda x: x[1]) # 按照結束時間排序
selected = [activities[0]]
last_finish = activities[0][1]
for activity in activities[1:]:
if activity[0] >= last_finish:
selected.append(activity)
last_finish = activity[1]
return len(selected)
# 示例用法
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
print(activity_selection(activities))
內容解密：
- 首先對活動按照結束時間進行排序，確保每次選擇的活動盡可能早結束。
- 初始化
selected列表，將第一個活動加入其中，並記錄其結束時間last_finish。 - 遍歷剩餘的活動，如果某個活動的開始時間晚於
last_finish，則將其加入selected並更新last_finish。 - 最終傳回選擇的活動數量。
動態規劃的高階技巧
動態規劃透過將問題分解為子問題並儲存子問題的解來避免重複計算。以下是一些動態規劃的高階技巧：
狀態空間縮減
透過減少需要考慮的狀態數量，可以顯著提高動態規劃的效率。一個典型的例子是使用位元遮罩來表示狀態。
def tsp(graph):
n = len(graph)
all_visited = (1 << n) - 1
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0 # 從城市0開始
for mask in range(1, 1 << n):
for u in range(n):
if mask & (1 << u):
for v in range(n):
if mask & (1 << v) == 0:
dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + graph[u][v])
return min(dp[all_visited][i] + graph[i][0] for i in range(1, n))
# 示例用法
graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
print(tsp(graph))
內容解密：
- 使用位元遮罩
mask來表示已存取的城市集合，減少狀態空間。 - 初始化
dp陣列，dp[mask][u]表示在mask狀態下，最後存取城市u的最小路徑長度。 - 遍歷所有可能的
mask和城市u，更新dp陣列。 - 最終傳回存取所有城市並傳回起點的最小路徑長度。
實際應用
動態規劃在許多領域有廣泛的應用，如金融、生物資訊學和電腦圖形學。
金融領域：Black-Scholes模型
import math
def black_scholes(S, K, T, r, sigma):
d1 = (math.log(S/K) + (r + 0.5 * sigma**2) * T) / (sigma * math.sqrt(T))
d2 = d1 - sigma * math.sqrt(T)
call = S * norm_cdf(d1) - K * math.exp(-r * T) * norm_cdf(d2)
put = K * math.exp(-r * T) * norm_cdf(-d2) - S * norm_cdf(-d1)
return call, put
def norm_cdf(x):
return (1.0 + math.erf(x / math.sqrt(2.0))) / 2.0
# 示例用法
S = 100
K = 100
T = 1
r = 0.05
sigma = 0.2
call, put = black_scholes(S, K, T, r, sigma)
print(f"Call option price: {call}, Put option price: {put}")
內容解密：
- 計算
d1和d2，用於後續的期權價格計算。 - 使用
norm_cdf函式計算標準正態分佈的累積分佈函式值。 - 根據 Black-Scholes 公式計算看漲期權和看跌期權的價格。
動態規劃在產業中的應用
動態規劃在各個產業中都有廣泛的應用，能夠為資源分配、機器學習和生物資訊學等領域提供高效的解決方案。這些領域通常需要處理最佳化問題，需要在多個因素之間取得平衡，並根據大量資料做出決策。
資源分配中的動態規劃
在資源分配中，動態規劃可以幫助組織最佳化有限資源在不同任務或專案之間的分配。這在製造業、物流業和專案管理等領域尤其有用。其中一個常見的應用是工作排程問題，需要將任務分配給機器或作業員，以最小化完成時間或最大化效率。
工作排程範例程式碼
def job_scheduling(jobs, deadlines, profits):
n = len(jobs)
jobs = sorted(zip(jobs, deadlines, profits), key=lambda x: x[2], reverse=True)
result = [0] * n
slot = [False] * n
for i in range(n):
for j in range(min(n, deadlines[i]) - 1, -1, -1):
if not slot[j]:
result[j] = i
slot[j] = True
break
return [jobs[i][0] for i in result if i != 0]
# 使用範例
jobs = ['a', 'b', 'c', 'd', 'e']
deadlines = [2, 1, 2, 1, 3]
profits = [100, 19, 27, 25, 15]
print(job_scheduling(jobs, deadlines, profits))
內容解密：
此程式碼實作了一個簡化版的工作排程問題。我們首先根據利潤從高到低對工作進行排序。然後，我們遍歷每個工作，並嘗試將其安排在截止日期前的最近可用時間槽中。這種貪婪策略與動態規劃的結合，有助於最佳化工作排程。
機器學習中的動態規劃
在機器學習中，動態規劃在各種演算法和最佳化技術中扮演著至關重要的角色。其中一個值得注意的應用是強化學習，特別是在解決馬可夫決策過程（MDP）時。價值迭代演算法是動態規劃在強化學習中的經典範例。
價值迭代演算法程式碼
import numpy as np
def value_iteration(P, R, gamma=0.99, epsilon=1e-8):
n_states, n_actions, _ = P.shape
V = np.zeros(n_states)
while True:
V_prev = V.copy()
for s in range(n_states):
Q_sa = [sum([P[s, a, s1] * (R[s, a, s1] + gamma * V_prev[s1]) for s1 in range(n_states)]) for a in range(n_actions)]
V[s] = max(Q_sa)
if np.max(np.abs(V - V_prev)) < epsilon:
break
policy = np.zeros(n_states, dtype=int)
for s in range(n_states):
Q_sa = [sum([P[s, a, s1] * (R[s, a, s1] + gamma * V[s1]) for s1 in range(n_states)]) for a in range(n_actions)]
policy[s] = np.argmax(Q_sa)
return V, policy
內容解密：
此程式碼實作了價值迭代演算法，用於計算馬可夫決策過程的最佳價值函式和策略。該演算法透過迭代更新狀態價值函式，直到收斂到最優解。然後，它根據最終的價值函式匯出最佳策略。這展示了動態規劃如何用於解決複雜的決策問題。
生物資訊學中的動態規劃
在生物資訊學中，動態規劃被廣泛應用於序列比對、RNA 結構預測和基因發現等領域。Smith-Waterman 演算法用於區域序列比對，是動態規劃在生物資訊學中的典型範例。
Smith-Waterman 演算法程式碼
def smith_waterman(seq1, seq2, match_score=2, mismatch_score=-1, gap_penalty=-1):
m, n = len(seq1), len(seq2)
score_matrix = [[0] * (n + 1) for _ in range(m + 1)]
max_score = 0
max_pos = (0, 0)
for i in range(1, m + 1):
for j in range(1, n + 1):
match = score_matrix[i-1][j-1] + (match_score if seq1[i-1] == seq2[j-1] else mismatch_score)
delete = score_matrix[i-1][j] + gap_penalty
insert = score_matrix[i][j-1] + gap_penalty
score_matrix[i][j] = max(0, match, delete, insert)
if score_matrix[i][j] > max_score:
max_score = score_matrix[i][j]
max_pos = (i, j)
return max_score, max_pos, score_matrix
def traceback(score_matrix, seq1, seq2, max_pos, match_score=2, mismatch_score=-1, gap_penalty=-1):
i, j = max_pos
aligned1, aligned2 = [], []
while score_matrix[i][j] > 0:
score = score_matrix[i][j]
diag = score_matrix[i-1][j-1]
up = score_matrix[i-1][j]
left = score_matrix[i][j-1]
if score == diag + (match_score if seq1[i-1] == seq2[j-1] else mismatch_score):
aligned1.append(seq1[i-1])
aligned2.append(seq2[j-1])
i -= 1
j -= 1
elif score == up + gap_penalty:
aligned1.append(seq1[i-1])
aligned2.append('-')
i -= 1
elif score == left + gap_penalty:
aligned1.append('-')
aligned2.append(seq2[j-1])
j -= 1
return ''.join(reversed(aligned1)), ''.join(reversed(aligned2))
# 使用範例
seq1 = "ACGTACGT"
seq2 = "AGTACGCA"
max_score, max_pos, score_matrix = smith_waterman(seq1, seq2)
aligned1, aligned2 = traceback(score_matrix, seq1, seq2, max_pos)
print(f"比對分數: {max_score}")
print(f"比對序列1: {aligned1}")
print(f"比對序列2: {aligned2}")
內容解密：
此程式碼實作了Smith-Waterman演算法，用於區域序列比對。首先，它構建了一個評分矩陣，然後透過回溯找到最佳的區域性比對序列。這個實作展示了動態規劃如何高效地解決複雜的生物序列分析問題。
K-近鄰演算法：機器學習中的基本工具
什麼是K-近鄰演算法？
K-近鄰演算法（KNN）是機器學習中的一種基礎演算法，特別適用於分類別和迴歸任務。它根據相似的資料點傾向於彼此接近的原理。該演算法透過找到給定查詢點的K個最近鄰資料點，並根據它們的屬性進行預測。
KNN的核心是一種非引數方法，這意味著它不會對底層資料分佈做出假設。這種靈活性使它能夠模擬複雜的決策邊界，使其對廣泛的問題有效。該演算法的簡單性和可解釋性使其成為許多機器學習任務的優秀起點。
KNN的基本原理
KNN的概念圍繞著相似性的理念。對於資料集中的每個資料點，演算法計算它與查詢點之間的距離。最常用的距離度量是歐幾裡得距離，儘管根據資料的性質也可以使用曼哈頓距離或漢明距離等其他度量。
一旦計算出距離，演算法就會選擇K個最近鄰。K的值是一個至關重要的超引數，它顯著影響演算法的效能。較小的K值使模型對資料中的噪聲更敏感，而較大的K值可能導致過於平滑的決策邊界。
分類別和迴歸任務中的KNN
在分類別任務中，KNN透過對其K個最近鄰進行多數投票來預測查詢點的類別。在迴歸任務中，它預測K個最近鄰的平均值。這種投票機制使KNN本質上成為多類別的，能夠處理具有兩個以上類別的問題而無需修改。
KNN在機器學習中的重要性
KNN的重要性在於它是一種基準演算法，許多更複雜的模型都與它進行比較。它的簡單性使其成為理解資料底層結構的優秀工具。此外，KNN在決策邊界不規則的場景中非常有效，優於更僵化的演算法。
KNN的優缺點
KNN的一個關鍵優勢是它缺乏訓練階段。該演算法只是儲存訓練資料，並在預測時進行計算。這種懶惰學習方法使KNN能夠快速實施並適應新資料。然而，這也意味著預測期間的計算成本可能很高，特別是對於大型資料集。
KNN的效能可能會受到高維資料的影響，這種現象稱為維度災難。隨著特徵數量的增加，距離的概念變得不那麼有意義，演算法的有效性降低。
另一個需要考慮的是演算法對特徵尺度的敏感性。如果一個特徵的尺度遠大於其他特徵，它將主導距離計算。為瞭解決這個問題，通常的做法是在應用KNN之前對特徵進行標準化或歸一化。
Python實作KNN
讓我們實作一個基本的KNN版本來說明其工作原理：
import numpy as np
from collections import Counter
class KNN:
def __init__(self, k=3):
self.k = k
def fit(self, X, y):
self.X_train = X
self.y_train = y
def predict(self, X):
predictions = [self._predict(x) for x in X]
return np.array(predictions)
def _predict(self, x):
# 計算查詢點與所有訓練點之間的歐幾裡得距離
distances = [np.sqrt(np.sum((x - x_train)**2)) for x_train in self.X_train]
# 選擇K個最近鄰
k_indices = np.argsort(distances)[:self.k]
k_nearest_labels = [self.y_train[i] for i in k_indices]
# 傳回K個最近鄰中最常見的類別
most_common = Counter(k_nearest_labels).most_common(1)
return most_common[0][0]
# 使用範例
X_train = np.array([[1,2], [1.5,1.8], [5,8], [8,8], [1,0.6], [9,11]])
y_train = np.array([0,0,1,1,0,1])
knn = KNN(k=3)
knn.fit(X_train, y_train)
X_test = np.array([[1,1], [7,7]])
predictions = knn.predict(X_test)
print(predictions) # 輸出：[0 1]
內容解密：
- 類別初始化：
__init__方法初始化KNN類別，設定最近鄰數量k，預設為3。 - 模型擬合：
fit方法儲存訓練資料X_train和對應的標籤y_train，供後續預測使用。 - 預測方法：
predict方法對輸入資料X進行預測，呼叫_predict方法計算每個樣本的預測結果。 - 單一樣本預測：
_predict方法計算查詢點x與所有訓練樣本的歐幾裡得距離，選取k個最近鄰，並根據其標籤進行多數投票決定預測類別。 - 距離計算：使用歐幾裡得距離公式計算查詢點與訓練樣本之間的距離。
- K個最近鄰選擇：根據計算出的距離，選取
k個最近的訓練樣本。 - 類別預測：統計
k個最近鄰的標籤，傳回出現次數最多的標籤作為預測結果。
KNN的實際應用
KNN在多個領域都有實際應用。在推薦系統中，它可以根據相似使用者的偏好推薦專案。在影像識別中，它可以根據已知示例的相似性對影像進行分類別。在金融領域，它可以透過比較貸款申請人和已知可靠或不可靠的借款人進行信用評分。
