بنیاد — ساختمان داده و الگوریتم، با اندازه‌گیری واقعی

فصل ۷ از ۸

پیشرفت ترم
۰٪

در این فصل چه یاد می‌گیری#

فصلِ قبل با یک جملهٔ آرام تمام شد: «پیمایشِ گراف تقریباً همیشه ارزان است». این فصل دربارهٔ سؤال‌هایی است که ارزان نیستند.

نقطهٔ شروع یک درخواستِ بی‌گناه است: «همهٔ مسیرها را بده». روی یک گرافِ کاملِ یازده‌گره‌ای جوابش 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 گام یک حدِ پایین می‌گیریم — که در یکی از دو اندازهٔ آزمایش، یک واحد کمتر از جوابِ درست درآمد.

به آخر این فصل رسیدی!

اگر ساختی و جواب داد، این دکمه مال توست.