ضرب زنجیره‌ای ماتریس‌ها
بهترین پرانتزگذاری برای ضرب چند ماتریس را با برنامه‌ریزی پویا پیدا می‌کند؛ ترتیب ضرب‌ها تعداد ضرب‌های عددی را تا چند برابر عوض می‌کند.
ضرب ماتریس p×q در q×r به p·q·r ضرب عددی نیاز دارد. ضرب ماتریسی شرکت‌پذیر است، پس A1·A2·…·An را با هر پرانتزگذاری می‌شود حساب کرد؛ ولی هزینه‌ها خیلی فرق می‌کنند.
- زمان:
O(n³) - حافظه:
O(n²) - CLRS، بخش ۱۴.۲
شش ماتریس با ابعاد ۳۰، ۳۵، ۱۵، ۵، ۱۰، ۲۰، ۲۵؛ کمترین هزینه ۱۵۱۲۵ با ((A1(A2A3))((A4A5)A6)).
INF = float("inf")def matrix_chain(p):# Matrix k (1-based) is p[k-1] × p[k]. "-" marks a cell not computed yet.n = len(p) - 1if n < 1:return Nonem = [["-"] * n for _ in range(n)]s = [["-"] * n for _ in range(n)]for i in range(n):m[i][i] = 0for length in range(2, n + 1):for i in range(n - length + 1):j = i + length - 1best = INFfor k in range(i, j):cost = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]if cost < best:best = costs[i][j] = k + 1m[i][j] = bestorder = parens(s, 0, n - 1)return m[0][n - 1], orderdef parens(s, i, j):if i == j:return "A" + str(i + 1)k = s[i][j]return "(" + parens(s, i, k - 1) + parens(s, k, j) + ")"
شروع اجرا
m
جدول هنوز خالی است.
s
جدول هنوز خالی است.
درخت فراخوانی‌های بازگشتی
نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده
متغیرهای محلی
نارنجی = در همین گام عوض شد
p list
Call stack
- matrix_chain()خط 4
توضیح
ایده
ضرب ماتریس p×q در q×r به p·q·r ضرب عددی نیاز دارد. ضرب ماتریسی شرکت‌پذیر است، پس A1·A2·…·An را با هر پرانتزگذاری می‌شود حساب کرد؛ ولی هزینه‌ها خیلی فرق می‌کنند.
برنامه‌ریزی پویا
m[i][j] کمترین هزینه‌ی ضرب Ai … Aj است. آخرین ضرب در جایی مثل k زنجیره را دو تکه می‌کند:
m[i][j] = min ( m[i][k] + m[k+1][j] + p[i−1]·p[k]·p[j] ) برای i ≤ k < j
زنجیره‌ها را به ترتیب طول پر می‌کنیم تا تکه‌های کوتاه‌تر آماده باشند. s[i][j] بهترین k را نگه می‌دارد و از روی آن پرانتزگذاری ساخته می‌شود.
هزینه
O(n²) خانه، هر کدام O(n) انتخاب: O(n³)؛ در برابر تعداد نمایی پرانتزگذاری‌ها (عدد کاتالان).
در trace به چه چیزی نگاه کنی
- جدول
mقطر به قطر پر می‌شود وsجای بهترین شکست را نشان می‌دهد. شماره‌ها در جدول از ۰ شروع می‌شوند و در برچسب‌ها از ۱.