در این فصل چه یاد میگیری#
فصلِ قبل با یک جملهٔ آرام تمام شد: «پیمایشِ گراف تقریباً همیشه ارزان است». این فصل دربارهٔ سؤالهایی است که ارزان نیستند.
نقطهٔ شروع یک درخواستِ بیگناه است: «همهٔ مسیرها را بده». روی یک گرافِ کاملِ یازدهگرهای جوابش 986,410 مسیر است و ستونِ نسبتش 7.00، 8.00، 9.00 — نسبتی که خودش با n بزرگ میشود. بعد جدولی میسازیم از بزرگترین nی که هر مرتبهٔ رشد در یک بودجهٔ مشخص جا میکند: با هزار برابر کردنِ بودجه، آن n برای O(n!) فقط از 12 به 14 میرود.

آخر این فصل میتوانی:
- بگویی «همهٔ مسیرها» چرا تقریباً همیشه صورتِ مسئلهٔ غلط است
- مرزِ عملیِ
nرا برای هر مرتبهٔ رشد حساب کنی، نه حدس بزنی - یک جوابِ تقریبی بسازی و خطایش را روی اندازههایی که جوابِ دقیق داری اندازه بگیری
قبل از شروع#
از ترمِ ۱ فصلِ ۶: شش خانوادهٔ رشد و جدولِ «اگر n هزار برابر شود». این فصل همان جدول را برعکس میپرسد: اگر بودجه هزار برابر شود، n چقدر بزرگتر میشود؟
از فصلِ ۶: DFS و مجموعهٔ دیدهشدهها.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | حدودِ نیم دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. کوچکترین نسخهٔ ممکن، با دست#
چهار گره که همه به هم وصلاند. از گرهٔ 0 تا گرهٔ 3 چند مسیرِ ساده هست؟ (مسیرِ ساده یعنی مسیری که از هیچ گرهای دو بار رد نمیشود.) با دست بشمار: مستقیم؛ از راهِ 1؛ از راهِ 2؛ از راهِ 1 و بعد 2؛ از راهِ 2 و بعد 1. پنج تا.
def complete(node_count):
"""گرافی که در آن هر گره به هر گرهِ دیگری وصل است."""
return {node: sorted(x for x in range(node_count) if x != node)
for node in range(node_count)}
def count_paths(graph, node, goal, seen, total):
"""همهٔ مسیرهای ساده — مسیرهایی که از هیچ گرهای دو بار رد نمیشوند."""
if node == goal:
total[0] += 1
return
for nbr in graph[node]:
if nbr not in seen:
seen.add(nbr)
count_paths(graph, nbr, goal, seen, total)
seen.discard(nbr)
def all_paths(node_count):
total = [0]
count_paths(complete(node_count), 0, node_count - 1, {0}, total)
return total[0]
tiny = complete(4)
print("گرافِ کاملِ ۴ گره:", tiny)
print("مسیرهای سادهٔ ۰ تا ۳:", all_paths(4))
گرافِ کاملِ ۴ گره: {0: [1, 2, 3], 1: [0, 2, 3], 2: [0, 1, 3], 3: [0, 1, 2]}
مسیرهای سادهٔ ۰ تا ۳: 5
خطِ seen.discard(nbr) همان یک خطی است که این کد را از DFS فصلِ قبل جدا میکند. در پیمایش، گرهای که دیدی برای همیشه دیدهشده میماند؛ اینجا فقط در طولِ همین مسیر دیدهشده است و بعد از برگشتن آزاد میشود. همین آزادسازی است که همهچیز را منفجر میکند.
🌱 ریشهاش کجاست: پنج مسیرِ بالا از یک شمارشِ ساده درآمد: یا مستقیم برو، یا یکی از دو گرهِ میانی را انتخاب کن، یا هر دو را به یکی از دو ترتیبِ ممکن. اصلِ ضرب و جایگشت — همان چیزی که ریشه ترمِ ۶ فصل ۱ میسازد: وقتی برای هر گام چند انتخاب داری، تعدادِ کلِ راهها ضربِ انتخابهاست، نه جمعشان. و ضرب است که منفجر میشود.
۲. حالا بزرگش کن#
🤔 اول حدس بزن: به گرافِ کامل یک گره اضافه میکنیم — فقط یکی. تعدادِ مسیرها چند برابر میشود؟ بنویسش، بعد جدول را ببین.
table([(n, all_paths(n)) for n in (8, 9, 10, 11)], "مسیرِ ساده", ",d")
n مسیرِ ساده نسبت به سطر قبل
8 1,957 —
9 13,700 7.00
10 109,601 8.00
11 986,410 9.00
این تنها جدولِ این دوره است که نردبانش دوبرابری نیست، و دلیلش خودِ موضوعِ فصل است: اگر n را از ۸ به ۱۶ میبردیم، سطرِ دوم هرگز تمام نمیشد.
و ستونِ نسبت را ببین: 7.00، 8.00، 9.00. این ستون ثابت نیست؛ خودش دارد بزرگ میشود و دقیقاً برابرِ n - 2 سطرِ قبل است. در O(n²) نسبت همیشه 4 میماند هرچقدر n بزرگ شود؛ اینجا نمیماند. هر ستونِ نسبتی که خودش رشد کند، یعنی مرتبه از هر توانی بدتر است.
حالا امضای دوره: اگر نسبت n - 2 است، برای n = 12 باید ده برابرِ سطرِ قبل باشد.
predicted = 10 * 986_410
measured = all_paths(12)
print(f"پیشبینی برای n = 12: {predicted:,}")
print(f"اندازهگیری : {measured:,}")
print(f"خطای پیشبینی : {measured - predicted}")
print(f"با همین قاعده برای n = 13: {11 * measured + 1:,} مسیر")
پیشبینی برای n = 12: 9,864,100
اندازهگیری : 9,864,101
خطای پیشبینی : 1
با همین قاعده برای n = 13: 108,505,112 مسیر
خطا: یکی. آن یکی هم بیدلیل نیست — قاعدهٔ دقیق (n - 2) برابرِ سطرِ قبل بهعلاوهٔ یک است، و آن «یک» همان مسیرِ مستقیم است که هیچ گرهِ میانی ندارد.
⚠️ مواظب باش: سطرِ
n = 12چند ثانیه طول کشید و همینجا ایستادیم. سطرِ بعدی108,505,112مسیر دارد و حدودِ یازده برابرِ آن وقت میخواهد؛ سطرِ بعدترش بیش از صد برابر. اگرall_paths(14)را در Colab صدا بزنی، سلولت تمام نمیشود. انتخابِ بزرگترین اندازهٔ یک جدولِ انفجاری بخشی از طراحیِ آزمایش است، نه چیزی که وسطِ اجرا کشفش کنی.
۳. مرزِ عملیِ n، برای هر مرتبه#
سؤالِ واقعیِ مهندسی این نیست که «این مرتبه چقدر بد است»؛ این است که «با این مرتبه، تا چه nی میتوانم جلو بروم؟»
فرض کن ماشینت در یک واحدِ زمان یک میلیارد گامِ ساده برمیدارد. این عدد فقط برای مقایسهٔ مرتبههاست، نه یک مشخصهٔ سختافزاری — چیزی که اهمیت دارد ستونِ دوم در برابرِ ستونِ سوم است.
import math
BUDGET = 10 ** 9
def largest_n(steps, budget):
"""بزرگترین n که کارش هنوز زیرِ budget میماند."""
high = 1
while steps(high) <= budget:
high *= 2
low = 1
while low < high:
middle = (low + high + 1) // 2
if steps(middle) <= budget:
low = middle
else:
high = middle - 1
return low
ORDERS = [
("O(n)", lambda n: n),
("O(n log n)", lambda n: n * math.log2(n + 1)),
("O(n^2)", lambda n: n * n),
("O(n^3)", lambda n: n * n * n),
("O(2^n)", lambda n: 2 ** n),
("O(n!)", lambda n: math.factorial(n)),
]
print(f"{'مرتبه':>12}{'n در یک میلیارد گام':>24}{'n در هزار برابرِ آن':>24}")
for name, fn in ORDERS:
print(f"{name:>12}{largest_n(fn, BUDGET):>24,}{largest_n(fn, 1_000 * BUDGET):>24,}")
مرتبه n در یک میلیارد گام n در هزار برابرِ آن
O(n) 1,000,000,000 1,000,000,000,000
O(n log n) 39,620,077 28,781,593,877
O(n^2) 31,622 1,000,000
O(n^3) 1,000 10,000
O(2^n) 29 39
O(n!) 12 14
این جدول را حفظ نکن؛ نگهش دار. دو ستونِ آخر را با هم بخوان: هزار برابر کردنِ ماشین، برای O(n) هزار برابر n میخرد، برای O(n²) سی و دو برابر، برای O(2^n) ده واحد، و برای O(n!) دو واحد.
برای مرتبههای پایینِ جدول، ماشینِ بهتر جوابِ مسئله نیست. اگر n تو ۲۰ است و الگوریتمت O(n!) است، هیچ سختافزاری نجاتت نمیدهد؛ باید صورتِ مسئله را عوض کنی.
۴. جوابِ تقریبی، و اندازهگیریِ خطایش#
سؤالِ نمونه: بلندترین مسیرِ ساده در یک گراف چند یال دارد؟ جوابِ دقیقش همان انفجارِ بخشِ ۲ را دارد. ولی یک جوابِ تقریبی ارزان هست: از هر گره شروع کن و هر بار سراغِ همسایهای برو که کمترین همسایهٔ دیدهنشده را دارد. و کاری که اکثرِ گزارشها نمیکنند این است: خطای تقریب را روی اندازههایی که جوابِ دقیق هنوز در دسترس است، اندازه میگیریم.
def make_graph(node_count, edge_count, seed=SEED):
rng = random.Random(seed)
edges = set()
while len(edges) < edge_count:
a = rng.randrange(node_count)
b = rng.randrange(node_count)
if a != b:
edges.add((min(a, b), max(a, b)))
graph = {node: [] for node in range(node_count)}
for a, b in sorted(edges):
graph[a].append(b)
graph[b].append(a)
for node in graph:
graph[node].sort()
return graph
def walk_longest(graph, node, seen, length, best, work):
work[0] += 1
if length > best[0]:
best[0] = length
for nbr in graph[node]:
if nbr not in seen:
seen.add(nbr)
walk_longest(graph, nbr, seen, length + 1, best, work)
seen.discard(nbr)
def longest_exact(graph):
"""جوابِ دقیق: هر مسیرِ ممکن از هر گره."""
best, work = [0], [0]
for start in sorted(graph):
walk_longest(graph, start, {start}, 0, best, work)
return best[0], work[0]
def longest_greedy(graph):
"""جوابِ تقریبی: از هر گره، هر بار سراغِ تنگترین همسایه."""
best, work = 0, 0
for start in sorted(graph):
seen = {start}
node = start
length = 0
while True:
options = []
for x in graph[node]:
work += 1
if x not in seen:
options.append(x)
if not options:
break
pick, fewest = options[0], None
for x in options:
free = 0
for y in graph[x]:
work += 1
if y not in seen:
free += 1
if fewest is None or free < fewest:
pick, fewest = x, free
node = pick
seen.add(node)
length += 1
best = max(best, length)
return best, work
print(f"{'V':>6}{'دقیق':>8}{'کارِ دقیق':>16}{'تقریبی':>10}{'کارِ تقریبی':>16}")
for v in (12, 16, 20, 24, 28, 32):
graph = make_graph(v, 3 * v // 2)
exact, exact_work = longest_exact(graph)
guess, guess_work = longest_greedy(graph)
print(f"{v:>6}{exact:>8}{exact_work:>16,}{guess:>10}{guess_work:>16,}")
V دقیق کارِ دقیق تقریبی کارِ تقریبی
12 10 3,788 10 795
16 13 18,484 9 821
20 16 125,606 13 1,693
24 20 593,642 17 2,414
28 20 930,334 13 2,115
32 26 9,982,418 21 3,084
ستونِ «کارِ دقیق» از 3,788 به 9,982,418 رفت، در حالی که V فقط از ۱۲ به ۳۲ رسید. ستونِ «کارِ تقریبی» در همان بازه از 795 به 3,084 رفت.
و ستونِ خطا صادقانه بد است: در V = 12 تقریب دقیقاً درست بود، در V = 16 جوابِ 9 داد بهجای 13، و در V = 28 جوابِ 13 بهجای 20. گاهی نزدیک، گاهی خیلی دور، و بدونِ هیچ الگوی مرتبی.
این را باید گفت، نه پنهان کرد: یک جوابِ تقریبی بدونِ اندازهگیریِ خطایش، یک عددِ بیپشتوانه است.
BIG = [500, 1_000, 2_000, 4_000]
print(f"{'V':>10}{'کار':>18}{'نسبت به سطر قبل':>20}{'بلندترین مسیر':>16}")
previous = None
for v in BIG:
found, work = longest_greedy(make_graph(v, 3 * v // 2))
ratio = "—" if not previous else f"{work / previous:.2f}"
print(f"{v:>10,}{work:>18,}{ratio:>20}{found:>16,}")
previous = work
V کار نسبت به سطر قبل بلندترین مسیر
500 47,955 — 27
1,000 110,612 2.31 50
2,000 241,197 2.18 64
4,000 470,322 1.95 59
ستونِ نسبت 2.31، 2.18، 1.95 — حولِ 2، یعنی جوابِ تقریبی خطی است. روی گرافِ ۴٬۰۰۰ گرهای 470,322 گام خرج کرد؛ جوابِ دقیق روی همان گراف حتی قابلِ شروع کردن نیست.
و ستونِ آخر را با احتیاط بخوان: عددهای 27، 50، 64، 59 حدِ پاییناند، نه جواب. تنها چیزی که میدانیم این است: مسیری به این طول وجود دارد، چون پیدایش کردیم.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ جستوجوی کاملِ همهٔ مسیرها با یک تقریبِ حریصانه، روی گرافِ یکسان و با شمارندهٔ یکسان. در کدام بازهٔ
n؟ گرافِ کاملِ ۸ تا ۱۲ گره برای شمارشِ مسیرها، ۱۲ تا ۳۲ گره برای مقایسهٔ دقیق و تقریبی، و ۵۰۰ تا ۴٬۰۰۰ گره برای خودِ تقریب. با چند تکرار، و کمینه یا میانگین؟ یک اجرا؛ شمارش قطعی است.
✅ چک کن: در
count_pathsخطِseen.discard(nbr)را بردار و بخشِ ۲ را دوباره بگیر. جوابِ هر چهار سطر باید1شود — چون بدونِ آزادسازی، هر گره فقط یک بار در کلِ جستوجو دیده میشود و کد بهDFSمعمولیِ فصلِ ۶ برمیگردد. همان یک خط، تفاوتِO(V+E)و انفجار است.
🔧 اگر کار نکرد: وقتی با این عددها کار میکنی، اولین چیزی که میشکند خودِ حسابِ اعشاری است:
try:
print(math.factorial(200) / 1_000_000_000)
except OverflowError as err:
print(f"{type(err).__name__}: {err}")
print("با تقسیمِ صحیح، بدونِ خطا:", len(str(math.factorial(200) // 1_000_000_000)), "رقم")
OverflowError: integer division result too large for a float
با تقسیمِ صحیح، بدونِ خطا: 366 رقم
عدد آنقدر بزرگ است که در یک float جا نمیشود. پایتون خودش عددِ صحیحش را نگه میدارد — ۳۶۶ رقم — ولی لحظهای که تقسیمِ اعشاری کنی، float کم میآورد. راهِ حل // است، یا کار کردن با تعدادِ رقمها بهجای خودِ عدد. و این خطا خودش یک پیام دارد: وقتی جوابِ یک مسئله در نوعِ عددیِ استاندارد جا نمیشود، آن مسئله را با هیچ ماشینی نمیشود شمرد.
🤖 از دستیارت بپرس: جدولِ بخشِ ۳ را جلویش بگذار: «برنامهام
O(2^n)است وnمن ۵۰ است؛ ماشینِ هزار برابر سریعتر کمکم میکند؟» — جوابِ درست باید بگوید نه و عدد بدهد. بعد: «چه سؤالِ دیگری میتوانم بپرسم که جوابش برایم کافی باشد؟»
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| simple path | سیمپل پث | مسیرِ ساده: مسیری که از هیچ گرهای دو بار رد نمیشود |
| combinatorial explosion | کامبیناتوریال اکسپلوژن | انفجارِ ترکیبیاتی: رشدی که از هر توانی تندتر است |
| backtracking | بکترکینگ | برگشتن و آزاد کردنِ گره، تا مسیرِ دیگری امتحان شود |
| approximation | اپراکسیمیشن | جوابِ تقریبی: جوابی که ارزان است و درستیِ کاملش تضمین نشده |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
همهچیزِ این ترم روی یک شبکهٔ واقعیشکل جمع میشود: ۴٬۰۰۰ گره، 11,994 یال، و چند گرهِ پرترافیک. و مثلِ همین فصل، محدودیتمان را با عدد اعلام میکنیم: قطرِ دقیقِ آن شبکه 111,952,000 گام میخواهد و ما با 55,976 گام یک حدِ پایین میگیریم — که در یکی از دو اندازهٔ آزمایش، یک واحد کمتر از جوابِ درست درآمد.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.